本文共 2360 字，大约阅读时间需要 7 分钟。

使用两个队列实现后入先出栈

一、功能概述

本文将详细介绍如何使用两个队列来实现一个后入先出（LIFO）的栈。通过合理利用队列的基本操作，我们可以将栈的常用操作（push、top、pop、empty）完整实现。这种方法避免了直接使用栈数据结构，仅仅依靠队列的操作来完成类似栈的行为。

二、实现思路

栈的特点是后入先出，意味着栈顶的元素总是最后被插入的。为了模拟这种行为，我们可以利用两个队列的特性。具体来说：

这种方法利用了队列的先进先出特性，将栈的后入先出行为模拟出来。

三、代码结构

// MyStack 结构体定义
typedef struct {
    QueueNode q1;  // 队列1
    QueueNode q2;  // 队列2
} MyStack;
// 初始化函数
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}
// 推操作
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    } else {
        QueuePush(&obj->q2, x);
    }
}
// 弹操作
int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    while (QueueSize(nonemptyQ) > 1) {
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return top;
}
// 查看顶部元素
int myStackTop(MyStack* obj) {
    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    } else {
        return QueueBack(&obj->q2);
    }
}
// 判断是否为空
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
// 销毁函数
void myStackFree(MyStack* obj) {
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
}

四、核心算法

1. push操作

• 如果队列1不为空，则将元素推入队列1。
• 如果队列1为空，则将元素推入队列2。

2. pop操作

• 判断队列1是否为空：
  • 如果队列1不为空，则将队列2设为空，队列1设为非空。
  • 重复将队列2的元素推入队列1，直到队列2只剩一个元素。
• 最后返回队列1的前元素，并移除它。

3. top操作

• 如果队列1不为空，返回队列1的后元素。
• 否则，返回队列2的后元素。

4. empty操作

• 检查两个队列是否为空，返回布尔值。

五、使用方法

MyStack* stack = myStackCreate();

2. 推元素：

myStackPush(stack, 10);  // stack现在有一个元素
myStackPush(stack, 20);  // stack有两个元素

3. 弹元素：

int popped = myStackPop(stack);  // 弹出栈顶元素20

4. 查看顶部：

int top = myStackTop(stack);  // 查看当前栈顶元素

5. 判断是否为空：

bool isEmpty = myStackEmpty(stack);  // 判断栈是否为空

6. 销毁栈：

myStackFree(stack);

---

六、注意事项

7. 队列操作：所有操作均基于队列的基本操作，包括push到后、peek/pop从前、size和is empty。
8. 语言支持：如果目标语言不支持队列，可以使用列表(list)或双端队列(deque)来模拟队列。
9. 空间复杂度：由于每次push操作都需要额外的空间，栈的空间复杂度为O(n)。
10. 时间复杂度：
    • push：O(1)
    • top：O(1)
    • pop：O(n)（在最坏情况下）
    • empty：O(1)

通过这种方法，我们可以高效地使用两个队列来实现一个后入先出的栈。