Реализация стека с использованием 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; 
} 

Выход:

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. Выскочил: -1. Выскочил: -1. Выскочил: -1.

Ожидаемый результат является первым, что очевидно в вопросе заголовка. Однако я не понимаю подробностей о том, почему код не работал, когда я не инкапсулировал 2 очереди в структуре в моем втором примере.

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 также изменять значения в вызывающей функции.