算法刷题(1)：使用队列实现栈

题目：

Implement the following operations of a stack using queues.

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

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

3. top() -- Get the top element.

4. 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

简单来说就是用队列实现栈结构。

栈：

栈的结构像叠砖头一样，一块一块往上叠，然后每次都是先从顶部一块块往下取下来，它是先进后出，后进先出的一种结构。

举些例子：

push(1)：把1压进栈中

push(2)：把2压进栈中

pop()：栈顶元素出栈

队列：

队列的结构就像排队打饭一样，先来的在前面，后来的在后面，先来的可以打完饭然后走人，就相当于出队，后来的最后才能打饭，它是先进先出，后进后出的一种结构。

举些例子：

push(1)：让1进入队列

push(2)：让2进入队列

pop()：队首元素打完饭了出队列

那么如何使用队列的结构去实现栈的结构呢?

首先我们假设其中有一个队列已经实现了栈的结构，其中队首的元素就是栈顶元素，即如下图。

如果此时有一个元素要压进栈顶，弹栈的时候它是要第一个出栈的，那么换句话说，如果用队列实现的话，它就要在队列的头部，这样才能第一个出队，以便实现弹栈时候第一个被弹出去。那么像上图所示如果只用一个队列的话，把该元素放进队列只能放在该队列的尾部。所以，我们再用另外一个辅助队列，下面用例子说明

如果push(3)：即相当于把3压进栈，即我们要实现的是把3进到队列的首部。

我们可以先把3进到一个辅助的空队列，这样他就成为队首元素，即相当于栈顶元素，因为队首和栈顶元素都是先出去的。

然后把原先的队列（即为实现好的栈结构，队首即为栈顶，队尾即为栈底）依次进到辅助队列内。

然后辅助Queue变成Queue，Queue变为辅助Queue，下次push元素时直接放到空的那个辅助队列中。

这样，就实现了用两个队列实现栈的算法。

实现代码：

import java.util.Queue; 
public class MyStack {
  Queue<Integer> q1 = new LinkedList<>();  //栈功能队列  Queue<Integer> q2 = new LinkedList<>(); //辅助队列    /** Initialize your data structure here. */    public MyStack() {            }        /** Push element x onto stack. */    public void push(int x) {        q2.add(x);  //将元素x放入空的辅助队列中        if(!q1.isEmpty()) {  /*吧栈功能队列的元素依次出队放进辅助队列中*/          q2.addAll(q1);            q1.clear();        }        /*把辅助队列置为栈功能队列，把栈功能队列置为辅助队列        此时辅助队列依然是空的*/        Queue<Integer> qtemp = q1;        q1 = q2;        q2 = qtemp;    }        /** Removes the element on top of the stack and returns that element. */    public int pop() {        return q1.poll();    }        /** Get the top element. */    public int top() {        return q1.peek();    }        /** Returns whether the stack is empty. */    public boolean empty() {        return q1.isEmpty();    }}

好了，今天的算法刷题到此为止讲述完毕，如果您对题目有更好的解法或者更好的想法，或者您对题目有什么疑惑或者我讲错的地方，又或者您有其他的有趣的题目想让我们讲解的，欢迎评论区留言告诉我们，我们一定进行回复，让我们共同交流共同进步！

IT界的泥石流带你一同刷题！一同进步！一同成长！