题目

• 概述：使用队列实现栈的基本功能：

1. push(x)：将x入栈
2. pop()：将栈顶元素出栈
3. top()：获取栈顶元素
4. empty()：栈为空返回true，反之false

只允许使用队列的标准操作：push(x)， pop()，peek()，empty()，size()

假设所给出的操作都是合理的

• 出处：https://leetcode-cn.com/problems/implement-stack-using-queues/

思路

• 由于队列和栈不同，它可以操纵两端的元素，可以考虑从这一点入手

1. push(x): 直接执行队列的push(x)
2. pop()：将队首元素移出并放到队尾，执行该操作(stack.size() - 1)次，这样就使得栈顶的元素暴露出来，然后执行队列的pop()即可
3. top()：在每次push(x)时记录x，那么栈顶元素即为x，因为栈的栈顶和队列的队尾是一致的
4. empty()：和队列的empty()一致

代码

class MyStack {
    private LinkedList<Integer> queue = new LinkedList<>();
    private Integer topValue;
    
    /** Initialize your data structure here. */
    public MyStack() {
        
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        topValue = x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        for (int i = 0; i < queue.size() - 1; ++i) {
            topValue = queue.poll();
            queue.offer(topValue);
        }
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return topValue;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}