Cài đặt Queue (hàng đợi) bằng hai Stack trong C++

Stack (LIFO)

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

Queue (FIFO)

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

Ý tưởng: 2 stack s1, s2. Enqueue push vào s1. Dequeue: nếu s2 rỗng, chuyển tất cả từ s1 sang s2 (đảo ngược thứ tự), rồi pop s2.

Ví dụ minh họa

#include <iostream>
#include <cstdlib>
using namespace std;

struct Node { int d; Node *n; };

void push(Node **top, int x) {
    Node *p = (Node*)malloc(sizeof(Node));
    p->d = x; p->n = *top; *top = p;
}
int pop(Node **top) {
    if (!*top) exit(0);
    Node *p = *top; *top = p->n;
    int v = p->d; free(p); return v;
}

struct Queue { Node *s1=NULL, *s2=NULL; };

void enQueue(Queue *q, int x) { push(&q->s1, x); }

int deQueue(Queue *q) {
    if (!q->s1 && !q->s2) { cout << "Queue rong\n"; exit(0); }
    if (!q->s2) while (q->s1) push(&q->s2, pop(&q->s1));
    return pop(&q->s2);
}

int main() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    enQueue(q,7); enQueue(q,6); enQueue(q,2); enQueue(q,3);
    cout << "Dequeue: " << deQueue(q) << endl; // 7
    cout << "Dequeue: " << deQueue(q) << endl; // 6
    cout << "Dequeue: " << deQueue(q) << endl; // 2
    return 0;
}

Kết quả

Dequeue: 7
Dequeue: 6
Dequeue: 2