Completed
Jan 2, 2025
标签
队列
模拟
相关企业
难度
简单
- 题目描述：用两个队列实现栈的push、pop、top和empty功能
- 代码思路：考察对栈和队列的熟练程度。有多种方法实现，本篇介绍双端队列实现、双队列实现和单队列实现
双端队列实现
双端队列实现起来比较容易，Deque可以在随意在队头队尾进行add、poll、peek等操作
双队列实现
使用双队列模拟栈，最核心一点就是在每次添加元素时，将其添加到队列头，而不是队列尾。添加到队列头，在队列的poll操作和peek操作时，才能模拟为栈。
为了每次添加新元素时能够添加到头部，需要先将队列1中的所有数据导到队列2中，再把新元素添加到队列1的第一个，再把队列2中的数据导回队列1。队列2实现了一个暂存的辅助功能
单队列实现
在双队列的基础上进一步优化，核心还是在push操作的时候，想办法把新元素放到队头。不需要队列2进行辅助，在新元素来的时候，正常入队列，然后将队列的前size-1个元素，依次出队列再入队列，保证每个新加入的元素都在队列的头部
