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

我们知道栈和队列都是一种线性结构，同样的数组、链表也是线性数据结构。

之前的一篇文章（五）介绍了一道lintcode最小值的栈的题目。本文将继续以一道Leetcode上面的经典题目来介绍栈和队列。

225. Implement Stack using Queues

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();stack.push(1);stack.push(2); stack.top(); // returns 2stack.pop(); // returns 2stack.empty(); // returns false

题目的意思就是用队列来模拟实现栈的功能，实现上面的几个功能。

思考：我们知道如果使用一个队列来实现栈肯定不可能的。那么使用两个队列来实现栈的功能呢？

答案是可以的。那么怎么实现以上几个功能呢？

我们先来看一下过程，假如我们存入3个数据，分别是1，2，3.按照栈的功能，3在栈顶，应该最先取出来。但是我们实际上是使用队列存储的，队列中在队首是1，因为队列是先进先出的结构。那么我们假如按照栈的方式要取出栈顶元素（数据3），怎么办？

我们可以这样看，假如一开始数据存放到队列A中，那么取数据的时候，只要将这个队列中的最后一个元素保留，其他元素保存到队列B中即可。然后取栈顶元素就是取队列A中最后一个数据。等取完数据，这个队列A就成为空队列了。

如下下次继续取数据，怎么办？现在剩余数据在队列B中，那么同样执行上面过程，将队列B中的数据放到队列A中，只保留队列B最后一个数据。这样即可按照栈的方式取到对应的数据2.

我们先来熟悉一下队列的相关API。

下面我们开始介绍怎么实现模拟栈的几个方法。

首先我们定义两个队列和一个数据长度的变量。

（1）实现栈的push方法 存数据到栈中

思路就是判断size是否为0，如果没有数据就向队列A中添加数据。如果size不为0，那么就看队列A或B谁没有空着，这时候就向非空的队列添加数据。

（2）实现pop方法移除栈顶元素

思路就是判断队列A还是队列B非空，那么将非空的队列中数据移除保存到另一个队列中，最后知道本队列剩下最后一个数据执行移除操作。移除完记得size减1.

（3）实现top方法获取栈顶元素

思路和上面一样，只是最后一个元素不删除，而是返回具体的值，然后把这个元素放入另一个队列。

（4）实现empty方法，判断栈是否为空。

思路就是观察size的长度是否为0.或者也可以使用队列A和B中是否为空来判断。

下一篇文章，我们将介绍如何用栈来模拟实现队列功能。