Cài đặt Stack (ngăn xếp) bằng hai Queue trong C++

Stack (LIFO)

Chèn/xóa cùng một đầu (top). Phần tử vào sau ra trước.

• push(data) – Chèn top.
• pop() – Xóa top.

Queue (FIFO)

Chèn rear, xóa front. Phần tử vào trước ra trước.

• Enqueue(data) – Chèn rear.
• Dequeue() – Xóa front.

Ý tưởng: dùng 2 queue q1, q2. push vào q1. pop: chuyển tất cả trừ phần tử cuối từ q1 sang q2, lấy phần tử cuối q1, rồi đổi vai q1/q2.

Ví dụ minh họa

#include <iostream>
using namespace std;

struct Node { int d; Node *n; };
Node *f1=NULL, *r1=NULL, *f2=NULL, *r2=NULL;

void enqueue1(int x) {
    Node *p = new Node{x, NULL};
    if (!f1) f1 = r1 = p;
    else { r1->n = p; r1 = p; }
}
int dequeue1() {
    if (!f1) return -1;
    Node *p = f1; f1 = f1->n;
    int v = p->d; delete p; return v;
}
void enqueue2(int x) {
    Node *p = new Node{x, NULL};
    if (!f2) f2 = r2 = p;
    else { r2->n = p; r2 = p; }
}
int dequeue2() {
    if (!f2) return -1;
    Node *p = f2; f2 = f2->n;
    int v = p->d; delete p; return v;
}

int main() {
    int n, x; cout << "So phan tu: "; cin >> n;
    while (n--) { cout << "Gia tri: "; cin >> x; enqueue1(x); }
    cout << "\nPop tu stack:\n";
    while (f1 || f2) {
        if (!f2) {
            while (f1->n) enqueue2(dequeue1());
            cout << dequeue1() << endl;
        } else {
            while (f2->n) enqueue1(dequeue2());
            cout << dequeue2() << endl;
        }
    }
    return 0;
}

Kết quả

So phan tu: 5
Gia tri: 1
Gia tri: 2
Gia tri: 3
Gia tri: 4
Gia tri: 5
Pop tu stack:
5
4
3
2
1