数据结构和算法基础篇（八）栈和队列（续

上一篇文章中，我们介绍了栈和队列的一道经典算法题。就是怎么使用两个队列实现栈的功能。今天我们来一道题，用栈来实现队列的功能。具体请接着阅读。

我们今天以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是否有数据。

总结：使用栈实现队列和使用队列实现栈是很经典的题目，这种思想可以帮助我们解决很多问题，后续我们遇到这种问题和思想的。