声明：问题描述来源于leetcode
一、问题描述：
用队列实现栈
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (67.64%) | 480 | - |
stack | design
bloomberg
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。注意：
push to back、peek/pop from front、size 和 is empty 这些操作。示例：
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
1 <= x <= 9100 次 push、pop、top 和 emptypop 和 top 都保证栈不为空**进阶：**你能否仅用一个队列来实现栈。
Discussion | Solution
通过list作为容器，直接见招拆招，要什么方法就通过list来实现什么方法，xin麒觉得应该还是比较容易懂的。
xin麒的思路：
list.size() == 0的运行结果即可class MyStack {
List<Integer> list;
public MyStack() {
list = new LinkedList<>();
}
public void push(int x) {
list.add(x);
}
public int pop() {
if (list.size() != 0){
return list.remove(list.size() - 1);
}
return 0;
}
public int top() {
if (list.size() != 0){
return list.get(list.size() - 1);
}
return 0;
}
public boolean empty() {
return list.size() == 0;
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
运行：
要通过两个队列实现堆栈，那么就要比较队列和堆栈的区别:
共同点：push方法是比较类似的比较好办，直接使用add()方法传入参数即可
empty()方法也是比较容易的，因为直接判断队列是否为空即可
不同点：pop方法中在堆栈的功能是：移除并返回栈顶元素；
在队列的功能是：移除并返回队列首元素。
top方法和pop方法类似，于是难点便是如何处理pop方法了:
那么如果将第一个队列的元素一个一个往第二个队列放会有什么效果呢？
在这个过程的细节是：第一个队列的首元素不断通过pop方法添加到第二个队列里面，其中第二个队列是使用push来接收。
于是xin麒想到可以在第一个队列不断调用pop方法时，等到第一个队列只剩下1个元素时，不就是所需提取的元素了吗？因此问题就基本解决了，当第一个队列的剩下1个元素时，直接提取该元素，后面再将这个元素返回即可。
然后为了配合push方法的使用（因为此时如果再给堆栈添加元素，那么就要添加到第二个队列里面），于是将第一个队列指向第二个队列，第二个队列就重开吧。
于是可以把第一个队列称为主队列mainQueue，第二个队列称为副本队列subordinateQueue。因此empty方法直接判断主队列是否为空即可。
top方法和pop方法比较类似，把提取的元素添加追加到副本队列即可。
class MyStack {
Queue<Integer> mainQueue;
Queue<Integer> subordinateQueue;
public MyStack() {
mainQueue = new LinkedList<>();
subordinateQueue = new LinkedList<>();
}
public void push(int x) {
mainQueue.add(x);
}
public int pop() {
if (!mainQueue.isEmpty()){
while (mainQueue.size() != 1){
subordinateQueue.add(mainQueue.poll());
}
int result = mainQueue.poll();
mainQueue = subordinateQueue;
subordinateQueue = new LinkedList<>();
return result;
}
return 0;
}
public int top() {
if (!mainQueue.isEmpty()) {
while (mainQueue.size() != 1) {
subordinateQueue.add(mainQueue.poll());
}
int result = mainQueue.peek();
subordinateQueue.add(result);
mainQueue = subordinateQueue;
subordinateQueue = new LinkedList<>();
return result;
}
return 0;
}
public boolean empty() {
return mainQueue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
运行：
因为有些代码可以复合的，xin麒就把它们封装在一个函数了，这样看起来比较简洁些。
class MyStack {
Queue<Integer> mainQueue;
Queue<Integer> subordinateQueue;
public MyStack() {
mainQueue = new LinkedList<>();
subordinateQueue = new LinkedList<>();
}
public void push(int x) {
mainQueue.add(x);
}
public int xinDo(){
int result = 0;
if (!mainQueue.isEmpty()){
while (mainQueue.size() != 1){
subordinateQueue.add(mainQueue.poll());
}
result = mainQueue.poll();
mainQueue = subordinateQueue;
subordinateQueue = new LinkedList<>();
}
return result;
}
public int pop() {
return xinDo();
}
public int top() {
int result = xinDo();
mainQueue.add(result);
return result;
}
public boolean empty() {
return mainQueue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
思路：
1、push方法不变，依然是使用list的add方法;
2(重点)、不断将队列首元素往末尾元素追加，同时移除该首元素，直到首元素为栈顶元素时便提取该元素作为返回值。
pop方法和top方法类似，稍做处理即可；
empty方法判断队列是否为空即可。
int pop():思考过程：
(--size >= 1)作为循环退出的条件。当条件为false时退出循环，并且此时的首元素即为所要返回的元素，于是在队列里面移除该元素，存放到result里面。int top:class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
queue.add(x);
}
public int pop() {
int size = queue.size();
int result = 0;
if (size != 0){
while (--size >= 1){
queue.add(queue.poll());
}
result = queue.poll();
}
return result;
}
public int top() {
if (queue.isEmpty()){
return 0;
}
int result = pop();
queue.add(result);
return result;
}
public boolean empty() {
return queue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
运行：
end