从零学算法

225.请你仅使用队列实现一个后入先出（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 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
[“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

• 首先队列是是先进先出，也就是 offer 把元素加到末尾，poll 时推出首部元素。我们使用一个队列，在每次 push 时，我们先记录当前队列长度，然后把元素 offer 到末尾，再把新元素之前的元素都插到新元素后面即可。比如此时队列有 [2,1]，在 push 3 时先看到时候要换几个元素的位置，也就是此时队列长度，此时长度为 2，ok 我先正常 off，此时为 [2,1,3]，接下来循环队列两次，把应该在 3 后面的两个元素重新 offer 回来，即 stack.off(stack.poll()) （把首元素插到末尾）即可，这样就等于把 [2,1] 插到 3 的末尾成了 [3,2,1]。（最开始我想的是这能不能和用两个栈实现队列一样操作，用两个队列实现栈，结果发现把一个队列的值 poll 到另一个队列，顺序不还是一样吗？但是，如果是 poll 到自身末尾，不就等于更改了顺序，所以使用一个队列）

•   class MyStack {
        Queue<Integer> stack = new LinkedList<>();
        public MyStack() {
    
        }
        public void push(int x) {
            int size = stack.size();
            stack.offer(x);
            while(size-- > 0){
                stack.offer(stack.poll());
            }
        }
        public int pop() {
            return stack.poll();
        }
        public int top() {
            return stack.peek();
        }
        public boolean empty() {
            return stack.isEmpty();
        }
    }
  

• 使用两个队列其实也可以，我们为了让先进先出的队列成为后进先出的栈，就是需要每次把 push 的元素加到队列首而不是尾，我们用一个空的队列 B，每次 push 时把元素 push 到空队列，然后把我们要使用的队列 A poll 到 B，A 就成了正确顺序的队列，最后把 B 置空等下一次 push。比如 A 为 [2,1] ，push 3 时先 push 到 B，此时 B 为 [3]，然后把 A 的 push 进来成 [3,2,1]，再让 A 成为 B，B 继续为空等下一次 push 即可。

•   class MyStack {
        Queue<Integer> stack = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        public MyStack() {
    
        }
        
        public void push(int x) {
            queue.offer(x);
            while(!stack.isEmpty()){
                queue.offer(stack.poll());
            }
           	// stack 都 poll 完了，成为空队列了，所以让它和 queue 互换即可
            Queue<Integer> temp = stack;
            stack = queue;
            queue = temp;
        }
        
        public int pop() {
            return stack.poll();
        }
        
        public int top() {
            return stack.peek();
        }
        
        public boolean empty() {
            return stack.isEmpty();
        }
    }