算法刷题(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 2
stack.pop(); // returns 2
stack.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界的泥石流带你一同刷题！一同进步！一同成长！
欢迎关注我们的微信公众号：IT界的泥石流
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
