栈与队列的“跨界”对话：如何用双队列完美模拟栈的LIFO特性？

Extreme35

发布于 2025-12-24 09:26:18

1370

文章被收录于专栏：DLDL

一、引言

我们今天聚焦于一个经典的算法面试题，即 如何利用两个队列（Queue）来实现栈（Stack）的全部功能。队列遵循 FIFO（First-In, First-Out） 原则，而栈遵循 LIFO (Last-In, First-Out) 原则，这两种线性数据结构在核心操作逻辑上是截然相反的。本题正是检验我们对数据结构抽象性、底层操作及设计哲学理解深度的绝佳案例。

要透彻理解本题，我们首先要清晰地把握队列和栈这两种线性结构在本质特性与操作逻辑上的根本差异。如果您需要快速回顾栈和队列的核心 ADT（抽象数据类型）、行为模式以及典型应用进行了详细的对比分析，建议先阅读此文（栈（Stack）的约束之美、【数据结构】手撕队列（Queue））。本文我们将直接在此认知基础上，挑战它们的“跨界”模拟，完成 FIFO 到 LIFO 的“适配”。

二、问题与挑战

我们实现的具体目标是：使用两个队列实现一个栈 MyStack，并提供以下四个方法：

push(x)：将元素 x 压入栈顶。
pop()：移除并返回栈顶元素。
top()：返回栈顶元素，但不移除。
empty()：判断栈是否为空。

核心挑战：FIFO 模拟 LIFO 的矛盾

双队列实现栈的核心挑战在于：

栈：要求能够高效地访问和移除最新进入的元素（栈顶/LIFO）。
队列：仅允许高效地访问和移除最旧进入的元素（队头/FIFO）。

单个队列只能从队尾入队，从队头出队，无法直接模拟栈顶操作。例如，如果元素按

[1, 2, 3]

的顺序入队，我们只能先取出

，但栈却要求我们先取出

。

这个矛盾点，恰恰是我们在设计任何数据结构时都需要思考的：如何通过已有的、更基础的操作组合，来实现更复杂或不同的行为逻辑。

三、解决方案

“用两个队列实现栈”的核心在于设计一个巧妙的“适配器”机制，让遵循 FIFO 规则的队列集合，能够对外表现出 LIFO 的行为。我们采用的“数据入非空队列，出栈时空队列辅助”策略，是一种牺牲出栈时间复杂度，换取入栈时间复杂度的经典设计权衡。

为了实现

LIFO

，我们必须确保最新进来的元素

能够最先被取出。然而，在队列中，新元素

总是被放在队尾。为了访问队尾的

，我们必须先将它前面的所有

n-1

个元素取出。

我们的双队列策略正是围绕这一需求展开：

操作	目标	队列机制	复杂度
push(x)	高效地将 x x x 存入。	始终将 x x x 放入当前唯一非空的“主队列”的队尾。	O ( 1 ) O(1) O(1)
pop()	访问并移除队尾元素。	利用第二个队列作为“辅助区”，将 n − 1 n-1 n−1 个旧元素转移走，孤立队尾元素 x x x。	O ( n ) O(n) O(n)

存入。始终将

放入当前唯一非空的“主队列”的队尾。

O(1)

pop()访问并移除队尾元素。利用第二个队列作为“辅助区”，将

n-1

个旧元素转移走，孤立队尾元素

。

O(n)

1. 数据结构定义

定义 MyStack 类，它内部包含两个队列，

和

。在任一时刻，所有有效的栈内元素，只会集中在一个队列中（非空队列），另一个队列始终是空的（辅助队列）。

// MyStack 结构体定义
typedef struct {
    Queue q1; // 队列 1
    Queue q2; // 队列 2
} MyStack;

2. 分步算法剖析与代码

2.1. `push(x)` 操作 (入栈)

设计思路： 由于队列的 enqueue（入队）操作天然是

O(1)

的（无论底层是链表还是动态数组），我们直接利用这个

O(1)

的优势。我们只需判断哪个队列当前持有数据（主队列），然后直接将新元素

扔进它的队尾即可。这样设计使得栈在面对频繁入栈操作时，能够保持极高的性能。

/* 入栈操作
 * @param obj: 指向栈的指针
 * @param x: 要入栈的元素值
 * 实现原理：将元素插入到非空队列中
 *          如果两个队列都为空，默认插入q2
 */
void myStackPush(MyStack* obj, int x) 
{
    /* 如果q1为空，则将元素插入q2 */
    if (QueueIsEmpty(&(obj->q1)))
    {
        QueuePush(&(obj->q2), x);
    }
    else  /* 否则将元素插入q1 */
    {
        QueuePush(&(obj->q1), x);
    }
}

2.2. `pop()` 操作 (出栈)

pop 操作是整个算法的灵魂，也是实现 LIFO 逻辑的关键。我们的目标是取出当前非空队列中的最后一个元素（队尾元素），因为它是最晚入队的，对应栈顶元素。

队列只能从队头（最旧元素）出队。要取出队尾元素（最新元素），我们必须先将它前面的所有

n-1

个元素转移走。

策略：
1. 确定主队列：通过判断
q1
和
q2
谁非空，确定当前存储数据的“主队列”（mainQ）和“辅助队列”（auxQ）。
1. 元素转移：将 mainQ 中的前
n-1
个元素（除了最后一个）依次出队，并入队到 auxQ 中。
1. 弹出栈顶：此时 mainQ 中仅剩最后一个元素（原队尾/栈顶元素）。将其从 mainQ 中出队并返回。
2. 角色互换：经过
pop
操作后，原 auxQ 现在包含了所有
n-1
个元素，它成为新的主队列；原 mainQ 变为空队列，它成为新的辅助队列。

元素转移模拟示例（假设

是主队列，内含

[1, 2, 3, 4]

，要弹出

）：

步骤	操作描述	q1 状态	q2 状态
0 (初始)	n = 4 n=4 n=4	[ 1 , 2 , 3 , 4 ] [1, 2, 3, 4] [1,2,3,4]	[ ] [] []
1	q 1 q1 q1 出队 1 1 1，入队 q 2 q2 q2	[ 2 , 3 , 4 ] [2, 3, 4] [2,3,4]	[ 1 ] [1] [1]
2	q 1 q1 q1 出队 2 2 2，入队 q 2 q2 q2	[ 3 , 4 ] [3, 4] [3,4]	[ 1 , 2 ] [1, 2] [1,2]
3	q 1 q1 q1 出队 3 3 3，入队 q 2 q2 q2	[ 4 ] [4] [4]	[ 1 , 2 , 3 ] [1, 2, 3] [1,2,3]
4	q 1 q1 q1 出队 4 4 4 (栈顶/返回)	[ ] [] []	[ 1 , 2 , 3 ] [1, 2, 3] [1,2,3]

n=4

[1, 2, 3, 4]

[]

出队

，入队

[2, 3, 4]

[1]

出队

，入队

[3, 4]

[1, 2]

出队

，入队

[4]

[1, 2, 3]

出队

(栈顶/返回)

[]

[1, 2, 3]

复杂度：pop 操作需要将

n-1

个元素全部出队并重新入队，因此时间复杂度为

O(n)

，其中

是当前栈的大小。

/* 出栈操作
 * @param obj: 指向栈的指针
 * @return: 栈顶元素的值
 * 实现原理：
 * 1. 确定哪个队列为空，哪个队列非空
 * 2. 将非空队列的前n-1个元素转移到空队列
 * 3. 剩下的最后一个元素就是栈顶元素，弹出并返回
 */
int myStackPop(MyStack* obj) 
{
    /* 假设q1为空队列，q2为非空队列 */
    Queue* empty = &(obj->q1);
    Queue* nonempty = &(obj->q2);
    
    /* 检查假设是否正确，如果不正确则交换 */
    if (!QueueIsEmpty(empty))
    {
        empty = &(obj->q2);
        nonempty = &(obj->q1);
    }
    
    /* 关键步骤：将非空队列的前n-1个元素转移到空队列
     * 这样非空队列就只剩下最后一个元素（即栈顶元素） */
    while (QueueSize(nonempty) > 1)
    {
        /* 获取非空队列的队首元素 */
        int frontValue = QueueFront(nonempty);
        /* 将元素压入空队列 */
        QueuePush(empty, frontValue);
        /* 从非空队列中移除该元素 */
        QueuePop(nonempty);
    }
    
    /* 此时nonempty队列只剩下最后一个元素（栈顶元素） */
    int top = QueueFront(nonempty);
    QueuePop(nonempty);  /* 弹出栈顶元素 */
    
    return top;  /* 返回栈顶元素 */
}

复杂度：pop 操作需要进行

n-1

次出队和入队操作，因此时间复杂度为

O(n)

，其中

是当前栈的大小。

2.3. `top()` 操作 (获取栈顶)

top 操作与 pop 操作非常相似，其逻辑是：找到栈顶元素，但不将其移除。

策略：转移

n-1

个元素，获取最后一个元素的值，然后将这个元素也转移到辅助队列中（而不是弹出），最后交换队列角色。

复杂度：

O(n)

。

int myStackTop(MyStack* obj) {
    Queue *mainQ, *auxQ;
    // 1. 确定主/辅助队列 (与 Pop 相同)
    // ...
    
    // 2. 元素转移 (将 n-1 个元素从 mainQ 转移到 auxQ)
    while (queueSize(mainQ) > 1) {
        int temp = queueDequeue(mainQ);
        queueEnqueue(auxQ, temp);
    }
    
    // 3. 获取栈顶值
    int stackTopVal = queueFront(mainQ); 
    
    // 4. 将最后一个元素也转移到 auxQ (重要：确保数据状态统一)
    queueDequeue(mainQ);
    queueEnqueue(auxQ, stackTopVal); 
    
    // 5. 角色互换（隐式完成）
    
    return stackTopVal;
}

2.4. `empty()` 操作 (判断空栈)

这是最简单的操作，只需检查两个底层队列是否都为空即可。

/* 判断栈是否为空
 * @param obj: 指向栈的指针
 * @return: true表示栈为空，false表示栈不为空
 * 实现原理：两个队列都为空时，栈才为空
 */
bool myStackEmpty(MyStack* obj) 
{
    return (QueueIsEmpty(&(obj->q1)) && QueueIsEmpty(&(obj->q2)));
}

四、延伸讨论：方案对比与关联思考

1. 单队列实现方案对比

我们采用的双队列实现方案，牺牲了

pop

和

top

的性能（

O(n)

）来换取

push

的高性能（

O(1)

）。这是算法设计中常见的时间复杂度权衡。如果你的应用场景以

push

为主，那么这个方案就是最优的。

除了双队列法，还有一种经典的单队列实现栈的思路：

策略：在执行 push(x) 时，将

正常入队。但随后，立即将队列中所有在

之前的元素全部出队，并重新入队到

之后。这样，每次入栈的新元素都会被“旋转”到队头。

复杂度：
- push(x)：需要
n
次元素转移，复杂度为
O(n)
。
- pop() / top()：此时栈顶元素（最新入队的）就在队头，可以直接
O(1)
出队或访问。

方法	push 复杂度	pop / top 复杂度	核心思想
双队列法	O ( 1 ) O(1) O(1)	O ( n ) O(n) O(n)	牺牲 p o p pop pop 性能，push 优先
单队列法	O ( n ) O(n) O(n)	O ( 1 ) O(1) O(1)	牺牲 p u s h push push 性能，pop/top 优先

O(1)

O(n)

牺牲

pop

性能，push 优先单队列法

O(n)

O(1)

牺牲

push

性能，pop/top 优先

两种方案各有优劣，体现了算法设计中常见的时间复杂度权衡。选择哪种方案取决于具体业务场景中对

push

和

pop

操作频率的要求。

2. 关联循环队列

而“循环队列”，是一种高效利用数组空间的队列实现，它完美解决了普通数组队列的“假溢出”问题。

对于我们实现栈的算法而言，我们只依赖于底层队列提供的 抽象接口 (enqueue, dequeue, isEmpty)，因此底层采用链表队列、普通数组队列还是循环队列，对本算法的逻辑和渐进时间复杂度（

O(n)

或

O(1)

）没有影响。

如果您对如何设计一个健壮的循环队列感兴趣，可以参考我的这篇实现笔记循环队列。

五、总结

“用队列实现栈”这一问题，本质上是一场关于数据结构抽象的实践课。通过双队列的巧妙协作与元素转移，我们成功地将 FIFO 的底层特性“适配”成了 LIFO 的外部行为。

我们再次总结核心思想：通过

O(1)

的

push

奠定基础，通过

O(n)

的元素转移实现

pop

的 LIFO 逻辑。

希望通过本文对‘用队列实现栈’这一具体问题的深入拆解，结合我之前关于栈、队列基础、实现与设计的系列文章，能帮助你建立起一个关于线性数据结构的、更立体的知识网络。所有相关的基础文章，你都可以在我的【数据结构】专栏中找到。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-11，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度