剑指Offer #05 用两个栈实现队列（模拟）

- 日理万妓 2023-07-08 02:52 92阅读 0赞

> 题目来源：牛客网-剑指Offer专题  
> 题目地址：[用两个栈实现队列][Link 1]

### 题目描述 ###

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

### 题目解析 ###

首先，我们需要知道一下基本知识：

> 栈（stack）是一种操作受限制的线性表，限定仅在表尾进行插入和删除操作的线性表，具有有“先进后出”的特性。  
> 队列（queue）也是一种操作受限制的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，具有“先进先出”的特性。

题目就是想让我们用两个“后进先出”的数据结构，来实现一个“先进先出”的数据结构。我们不妨思考考一下，当我们在stack1中按顺序插入了序列\[1, 2, 3\]，我们怎么利用另一个栈将其按“先进先出”顺序弹出呢？  
![1][]  
显然，将类似于小学所学的负负得正，**经过两次逆序操作，同样可以的到顺序**（指“先进先出”）。于是，我们将stack1中的元素按弹出的顺序压入到stack2中，最后再将stack2中的元素按顺序弹出就可以了。  
![2][]  
因为队列的Push和Pop操作的执行都是随机的，如果在某一刻stack2不是空的怎么办呢？（情况如下图所示）  
![3][]  
这个时候，如果执行Push操作，我们可以直接将新元素压入stack1中；如果要执行Pop操作，可以将stack2中的栈顶元素弹出。

总结起来，我们可以得到如下算法：

*  当执行Push操作时，**直接将新元素压入stack1中**。
 *  当执行Pop操作时，**判断stack2是否为空。若为空，则先将stack1的所有元素都放入stack2中；否则直接弹出stack2的栈顶元素**。

import java.util.Stack;
    
    public class Solution { 
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) { 
        	//直接压入stack1中
            stack1.push(node);
        }
        
        public int pop() { 
            if (stack2.isEmpty()) { 
            	//如果stack2空了，就将stack1中的元素全部放入stack2中
                while (!stack1.isEmpty()) { 
                    int node = stack1.pop();
                    stack2.push(node);
                }
            }
            //弹出stack2的栈顶元素
            return stack2.pop();
        }
    }

--------------------

如果本文对你有所帮助，要记得点赞哦~

[Link 1]: https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=13&tqId=11158&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[1]: https://img-blog.csdnimg.cn/20200225170613723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[2]: https://img-blog.csdnimg.cn/20200225171519837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70
[3]: https://img-blog.csdnimg.cn/20200225172654456.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI5MjIyOQ==,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】——用两个栈模拟队列

是我真实遇到的面试原题(当时我并不会2333333，于是下来研究一番) 队列结构 * 队列(Queue)，它是一种运算受限的线性表,先进先出(FIFO Fir...

朱雀/ 2024年04月20日 08:29/ 0 赞/ 68 阅读

相关剑指Offer #05 用两个栈实现队列（模拟）

> 题目来源：牛客网-剑指Offer专题 > 题目地址：[用两个栈实现队列][Link 1] 题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队

- 日理万妓/ 2023年07月08日 02:52/ 0 赞/ 93 阅读

相关【剑指offer】用两个栈实现队列

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。 -------------------- import jav

落日映苍穹つ/ 2022年06月16日 12:18/ 0 赞/ 227 阅读

相关剑指offer——用两个栈实现队列

题目用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。实现及原理栈，具有先进后出的特点；而队列具有先进先出的特点

我会带着你远行/ 2022年05月17日 10:21/ 0 赞/ 244 阅读

相关剑指offer：用两个栈实现队列

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。思路: push操作时,push到stack1栈保存 pop操作时,

浅浅的花香味﹌/ 2022年04月14日 05:12/ 0 赞/ 266 阅读

相关剑指Offer-用两个栈实现队列

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。初步解题思路：使用stack1专门用来输入，stack2专门用来输出。当

客官°小女子只卖身不卖艺/ 2022年03月02日 15:16/ 0 赞/ 288 阅读

相关剑指offer-用两个栈实现队列

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。实现思想栈是后入先出的，队列是先入先出的。基于以上特点，其

忘是亡心i/ 2022年02月20日 04:17/ 0 赞/ 276 阅读

相关【剑指offer】用两个栈实现队列

题目描述：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。解题思路：整体思路是元素先依次进入栈1，当栈2是空的时候就把栈1中的元

以你之姓@/ 2021年11月17日 06:56/ 0 赞/ 319 阅读

相关《剑指offer》用两个栈实现队列

本题来自《剑指offer》 [用两个栈实现队列][Link 1] 题目：　　用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

╰+攻爆jí腚メ/ 2021年10月29日 15:32/ 0 赞/ 348 阅读

相关剑指offer：用两个栈实现队列用两个队列实现栈

试题：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代码：首先显然要有个stack用来push，由于stack的后进后出

曾经终败给现在/ 2021年09月16日 06:30/ 0 赞/ 430 阅读