数据结构和算法基础篇（八）栈和队列（续
上一篇文章中，我们介绍了栈和队列的一道经典算法题。就是怎么使用两个队列实现栈的功能。今天我们来一道题，用栈来实现队列的功能。具体请接着阅读。
我们今天以Leetcode上的232题为例进行讲解。
232. Implement Queue using Stacks
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();queue.push(1);queue.push(2); queue.peek(); // returns 1queue.pop(); // returns 1queue.empty(); // returns false
题目的意思就是，使用栈来模拟实现一个队列的功能。具体实现以上几个函数push、peek、pop、empty等功能。
思考：通过上一篇文章的思路，我们知道可以用双栈来实现一个队列。
比如我们依次存放数据1，2，3。那么，按照队列的功能，先取出来的数据就是1，然后才是2，最后才是3。我们实现的思路依然和用队列实现栈的思路一致。
假如第一次存储，数据全部放到栈A中，此时栈顶的数据是3，然后才是2，最下面的数据是1。我们假如现在要取数据，那么我们可以将栈A上面的数据全部转移到栈B，栈A最后一个元素就是应该取的数据。
但是我们需要注意，假如栈A上面的数据被压入栈B中，此时栈B的数据是：栈顶为2，底下才是3.我们现在取数据，应该取栈B的栈顶就行。
下面详细介绍每个功能函数的实现过程。
（0）首先定义两个栈。
（1）实现push()功能，往模拟队列中存一个数据
我们将数据全部压入栈A中，也就是栈A一直保存数据。
（2）pop()功能，删除队列头部数据
思路就是，当栈B中存在数据的时候，就去栈B中删除数据。如果栈B不存在数据，就要把栈A的数据压入栈B，然后从栈B中删除数据。完成后记得size减少1.
（3）peek()函数，取出队列首部的数据
思路就是，假如栈B不为空，就去栈B取栈首的数据。如果栈B为空，需要把栈A的数据压入到栈B中，然后从栈B取栈顶的数据。
（4）empty()函数，判断队列是否有数据
思路就是判断size是否为0.当然也可以判断栈A和栈B是否有数据。
总结：使用栈实现队列和使用队列实现栈是很经典的题目，这种思想可以帮助我们解决很多问题，后续我们遇到这种问题和思想的。
- 发表于:
- 原文链接：https://kuaibao.qq.com/s/20180724G0BFFT00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
