使用 2 Queues 实现堆栈

Question

此代码为何有效：

#include <cstdio>
#include <cstdlib>

#define N n *
#define Q q *
#define S s *

typedef struct n
{
    int data;
    struct N nxt;
}n;

typedef struct q
{
    N f;
    N r;
}q;

typedef struct stack
{
    Q q1;
    Q q2;
}s;
Q Createq()
{
    Q qq = (Q)malloc(sizeof(q));
    qq->f = qq->r  = 0;
    return qq;
}

S CreateStk()
{
    S stk = (S)malloc(sizeof(s));
    stk->q1 = Createq();
    stk->q2 = Createq();
    return stk;
}

int Deq(Q qq)
{
    if(qq->f == 0 && qq->r == 0) return -1;
    N nn = qq->r;
    int data = nn->data;
    qq->r = qq->r->nxt;
    free(nn);
    if(!qq->r)
        qq->f = 0;
    return data;
}

void Enq(Q qq, int data)
{
    if(!qq->f)
    {
        N nn = (N)malloc(sizeof(n));
        nn->data = data;
        nn->nxt = 0;
        qq->f = qq->r = nn;
    }
    else
    {
        N nn = (N)malloc(sizeof(n));
        nn->data = data;
        nn->nxt = 0;
        qq->f->nxt = nn;
        qq->f = nn;
    }
}

void Push(S stk, int data)
{
    Enq(stk->q2,data);

    while(stk->q1->f)
    {
        Enq(stk->q2,Deq(stk->q1));
    }

    Q t = stk->q1;
    stk->q1 = stk->q2;
    stk->q2 = t;
}

int Pop(S stk)
{
    return Deq(stk->q1);
}
int main() 
{
    S stk = CreateStk();
    Push(stk,10);
    Push(stk,30);
    Push(stk,40);
    Push(stk,50);
    printf("\nPopped: %d.", Pop(stk));
    printf("\nPopped: %d.", Pop(stk));
    printf("\nPopped: %d.", Pop(stk));
    printf("\nPopped: %d.", Pop(stk));
    return 0;
    return 0;
}

输出：

Popped: 50.
Popped: 40.
Popped: 30.
Popped: 10.

虽然这不是：

#include <cstdio>
#include <cstdlib>

#define N n *
#define Q q *

typedef struct n
{
    int data;
    struct N nxt;
}n;

typedef struct q
{
    N f;
    N r;
}q;

Q Createq()
{
    Q qq = (Q)malloc(sizeof(q));
    qq->f = qq->r  = 0;
    return qq;
}

int Deq(Q qq)
{
    if(qq->f == 0 && qq->r == 0) return -1;
    N nn = qq->r;
    int data = nn->data;
    qq->r = qq->r->nxt;
    free(nn);
    if(!qq->r)
        qq->f = 0;
    return data;
}

void Enq(Q qq, int data)
{
    if(!qq->f)
    {
        N nn = (N)malloc(sizeof(n));
        nn->data = data;
        nn->nxt = 0;
        qq->f = qq->r = nn;
    }
    else
    {
        N nn = (N)malloc(sizeof(n));
        nn->data = data;
        nn->nxt = 0;
        qq->f->nxt = nn;
        qq->f = nn;
    }
}

void Push(Q qq1, Q qq2, int data)
{
    Enq(qq2,data);

    while(qq1->f)
    {
        Enq(qq2,Deq(qq1));
    }

    Q t = qq1;
    qq1 = qq2;
    qq2 = t;
}

int Pop(Q qq1)
{
    return Deq(qq1);
}

int main() {
    // your code goes here
    Q qq1 = Createq();
    Q qq2 = Createq();
    Push(qq1,qq2,10);
    Push(qq1,qq2,30);
    Push(qq1,qq2,40);
    Push(qq1,qq2,50);
    printf("\nPopped: %d.", Pop(qq1));
    printf("\nPopped: %d.", Pop(qq1));
    printf("\nPopped: %d.", Pop(qq1));
    printf("\nPopped: %d.", Pop(qq1));
    return 0;
}

输出：

Popped: -1. Popped: -1. Popped: -1. Popped: -1.

预期输出是第一个，因为问题标题很明显。但是，我不明白为什么在我的第二个示例中没有将 2 queues 封装在结构中时代码不起作用的细节。

PS：我认为问题出在 Push 方法上 - 但不确定哪里出了问题。

Answer 1

除了难以阅读之外，问题在于您的第二个 Push 函数在以下代码行中更改了其参数值。

Q t = qq1;
qq1 = qq2;
qq2 = t;

qq1 和 qq2 是函数的参数，因此新值不会在调用函数 (main) 中更新。

解决此问题的一种方法是使参数通过引用传递：

void Push(Q &qq1, Q &qq2, int data)

这样，对 qq1 和 qq2 的更改也会更改调用函数中的值。

使用 2 Queues 实现堆栈

Implementing Stack using 2 Queues

c

c++

queue

stack