使用2个队列实现堆栈

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;
}

输出：

弹出: 50。弹出: 40。弹出: 30。弹出: 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;
}

输出：

弹出：-1。弹出：-1。弹出：-1。弹出：-1。

预期的输出是第一个，因为它的明显的问题标题。但是，当我在第二个示例中没有将这两个队列封装在一个结构中时，我不理解为什么代码不能工作的血淋淋的细节。

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的更改也会改变调用函数中的值。