个人主页:Marathon_X 个人专栏:专栏名称专栏主题简述《C语言》C语言基础、语法解析与实战应用《数据结构》线性表、树、图等核心数据结构详解《题解思维》算法思路、解题技巧与高效编程实践《排序详解》算法思路、解题技巧与高效编程实践目录一、 引言二、 问题与挑战核心挑战FIFO 模拟 LIFO 的矛盾三、 解决方案1. 数据结构定义2. 分步算法剖析与代码2.1. push(x) 操作 (入栈)2.2. pop() 操作 (出栈)2.3. top() 操作 (获取栈顶)2.4. empty() 操作 (判断空栈)四、 延伸讨论方案对比与关联思考1. 单队列实现方案对比2. 关联循环队列五、 总结一、 引言我们今天聚焦于一个经典的算法面试题即如何利用两个队列Queue来实现栈Stack的全部功能。队列遵循FIFOFirst-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 ] [1, 2, 3][1,2,3]的顺序入队我们只能先取出1 11但栈却要求我们先取出3 33。这个矛盾点恰恰是我们在设计任何数据结构时都需要思考的如何通过已有的、更基础的操作组合来实现更复杂或不同的行为逻辑。三、 解决方案“用两个队列实现栈”的核心在于设计一个巧妙的“适配器”机制让遵循FIFO规则的队列集合能够对外表现出LIFO的行为。我们采用的“数据入非空队列出栈时空队列辅助”策略是一种牺牲出栈时间复杂度换取入栈时间复杂度的经典设计权衡。为了实现L I F O LIFOLIFO我们必须确保最新进来的元素x xx能够最先被取出。然而在队列中新元素x xx总是被放在队尾。为了访问队尾的x xx我们必须先将它前面的所有n − 1 n-1n−1个元素取出。我们的双队列策略正是围绕这一需求展开操作目标队列机制复杂度push(x)高效地将x xx存入。始终将x xx放入当前唯一非空的“主队列”的队尾。O ( 1 ) O(1)O(1)pop()访问并移除队尾元素。利用第二个队列作为“辅助区”将n − 1 n-1n−1个旧元素转移走孤立队尾元素x xx。O ( n ) O(n)O(n)1. 数据结构定义定义MyStack类它内部包含两个队列q 1 q1q1和q 2 q2q2。在任一时刻所有有效的栈内元素只会集中在一个队列中非空队列另一个队列始终是空的辅助队列。// MyStack 结构体定义typedefstruct{Queue q1;// 队列 1Queue q2;// 队列 2}MyStack;2. 分步算法剖析与代码2.1.push(x)操作 (入栈)设计思路由于队列的enqueue入队操作天然是O ( 1 ) O(1)O(1)的无论底层是链表还是动态数组我们直接利用这个O ( 1 ) O(1)O(1)的优势。我们只需判断哪个队列当前持有数据主队列然后直接将新元素x xx扔进它的队尾即可。 这样设计使得栈在面对频繁入栈操作时能够保持极高的性能。/* 入栈操作 * param obj: 指向栈的指针 * param x: 要入栈的元素值 * 实现原理将元素插入到非空队列中 * 如果两个队列都为空默认插入q2 */voidmyStackPush(MyStack*obj,intx){/* 如果q1为空则将元素插入q2 */if(QueueIsEmpty((obj-q1))){QueuePush((obj-q2),x);}else/* 否则将元素插入q1 */{QueuePush((obj-q1),x);}}2.2.pop()操作 (出栈)pop操作是整个算法的灵魂也是实现 LIFO 逻辑的关键。我们的目标是取出当前非空队列中的最后一个元素队尾元素因为它是最晚入队的对应栈顶元素。队列只能从队头最旧元素出队。要取出队尾元素最新元素我们必须先将它前面的所有n − 1 n-1n−1个元素转移走。策略确定主队列通过判断q 1 q1q1和q 2 q2q2谁非空确定当前存储数据的“主队列”mainQ和“辅助队列”auxQ。元素转移将mainQ中的前n − 1 n-1n−1个元素除了最后一个依次出队并入队到auxQ中。弹出栈顶此时mainQ中仅剩最后一个元素原队尾/栈顶元素。将其从mainQ中出队并返回。角色互换经过p o p poppop操作后原auxQ现在包含了所有n − 1 n-1n−1个元素它成为新的主队列原mainQ变为空队列它成为新的辅助队列。元素转移模拟示例假设q 1 q1q1是主队列内含[ 1 , 2 , 3 , 4 ] [1, 2, 3, 4][1,2,3,4]要弹出4 44步骤操作描述q1 状态q2 状态0(初始)n 4 n4n4[ 1 , 2 , 3 , 4 ] [1, 2, 3, 4][1,2,3,4][ ] [][]1q 1 q1q1出队1 11入队q 2 q2q2[ 2 , 3 , 4 ] [2, 3, 4][2,3,4][ 1 ] [1][1]2q 1 q1q1出队2 22入队q 2 q2q2[ 3 , 4 ] [3, 4][3,4][ 1 , 2 ] [1, 2][1,2]3q 1 q1q1出队3 33入队q 2 q2q2[ 4 ] [4][4][ 1 , 2 , 3 ] [1, 2, 3][1,2,3]4q 1 q1q1出队4 44(栈顶/返回)[ ] [][][ 1 , 2 , 3 ] [1, 2, 3][1,2,3]复杂度pop操作需要将n − 1 n-1n−1个元素全部出队并重新入队因此时间复杂度为O ( n ) O(n)O(n)其中n nn是当前栈的大小。/* 出栈操作 * param obj: 指向栈的指针 * return: 栈顶元素的值 * 实现原理 * 1. 确定哪个队列为空哪个队列非空 * 2. 将非空队列的前n-1个元素转移到空队列 * 3. 剩下的最后一个元素就是栈顶元素弹出并返回 */intmyStackPop(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){/* 获取非空队列的队首元素 */intfrontValueQueueFront(nonempty);/* 将元素压入空队列 */QueuePush(empty,frontValue);/* 从非空队列中移除该元素 */QueuePop(nonempty);}/* 此时nonempty队列只剩下最后一个元素栈顶元素 */inttopQueueFront(nonempty);QueuePop(nonempty);/* 弹出栈顶元素 */returntop;/* 返回栈顶元素 */}复杂度pop操作需要进行n − 1 n-1n−1次出队和入队操作因此时间复杂度为O ( n ) O(n)O(n)其中n nn是当前栈的大小。2.3.top()操作 (获取栈顶)top操作与pop操作非常相似其逻辑是找到栈顶元素但不将其移除。策略转移n − 1 n-1n−1个元素获取最后一个元素的值然后将这个元素也转移到辅助队列中而不是弹出最后交换队列角色。复杂度O ( n ) O(n)O(n)。intmyStackTop(MyStack*obj){Queue*mainQ,*auxQ;// 1. 确定主/辅助队列 (与 Pop 相同)// ...// 2. 元素转移 (将 n-1 个元素从 mainQ 转移到 auxQ)while(queueSize(mainQ)1){inttempqueueDequeue(mainQ);queueEnqueue(auxQ,temp);}// 3. 获取栈顶值intstackTopValqueueFront(mainQ);// 4. 将最后一个元素也转移到 auxQ (重要确保数据状态统一)queueDequeue(mainQ);queueEnqueue(auxQ,stackTopVal);// 5. 角色互换隐式完成returnstackTopVal;}2.4.empty()操作 (判断空栈)这是最简单的操作只需检查两个底层队列是否都为空即可。/* 判断栈是否为空 * param obj: 指向栈的指针 * return: true表示栈为空false表示栈不为空 * 实现原理两个队列都为空时栈才为空 */boolmyStackEmpty(MyStack*obj){return(QueueIsEmpty((obj-q1))QueueIsEmpty((obj-q2)));}四、 延伸讨论方案对比与关联思考1. 单队列实现方案对比我们采用的双队列实现方案牺牲了p o p poppop和t o p toptop的性能O ( n ) O(n)O(n)来换取p u s h pushpush的高性能O ( 1 ) O(1)O(1)。这是算法设计中常见的时间复杂度权衡。如果你的应用场景以p u s h pushpush为主那么这个方案就是最优的。除了双队列法还有一种经典的单队列实现栈的思路策略在执行push(x)时将x xx正常入队。但随后立即将队列中所有在x xx之前的元素全部出队并重新入队到x xx之后。这样每次入栈的新元素都会被“旋转”到队头。复杂度push(x)需要n nn次元素转移复杂度为O ( n ) O(n)O(n)。pop()/top()此时栈顶元素最新入队的就在队头可以直接O ( 1 ) O(1)O(1)出队或访问。方法push 复杂度pop / top 复杂度核心思想双队列法O ( 1 ) O(1)O(1)O ( n ) O(n)O(n)牺牲p o p poppop性能push优先单队列法O ( n ) O(n)O(n)O ( 1 ) O(1)O(1)牺牲p u s h pushpush性能pop/top优先两种方案各有优劣体现了算法设计中常见的时间复杂度权衡。选择哪种方案取决于具体业务场景中对p u s h pushpush和p o p poppop操作频率的要求。2. 关联循环队列而“循环队列”是一种高效利用数组空间的队列实现它完美解决了普通数组队列的“假溢出”问题。对于我们实现栈的算法而言我们只依赖于底层队列提供的抽象接口(enqueue,dequeue,isEmpty)因此底层采用链表队列、普通数组队列还是循环队列对本算法的逻辑和渐进时间复杂度O ( n ) O(n)O(n)或O ( 1 ) O(1)O(1)没有影响。如果您对如何设计一个健壮的循环队列感兴趣可以参考我的这篇实现笔记循环队列。五、 总结“用队列实现栈”这一问题本质上是一场关于数据结构抽象的实践课。通过双队列的巧妙协作与元素转移我们成功地将FIFO的底层特性“适配”成了LIFO的外部行为。我们再次总结核心思想通过O ( 1 ) O(1)O(1)的p u s h pushpush奠定基础通过O ( n ) O(n)O(n)的元素转移实现p o p poppop的 LIFO 逻辑。希望通过本文对‘用队列实现栈’这一具体问题的深入拆解结合我之前关于栈、队列基础、实现与设计的系列文章能帮助你建立起一个关于线性数据结构的、更立体的知识网络。所有相关的基础文章你都可以在我的【数据结构】专栏中找到。