232. 用栈实现队列 (opens new window)

1.双栈模拟队列

每次出栈时，如果out为空才将in栈内的元素倒入out“清一次货”。

因此每次出队列操作并不需要将栈内所有元素都倒过来，输出栈底元素。out输出栈保证了栈顶元素一定是最先进入队列的元素，故只需要查看out是否为空再直接出栈即可。

class MyQueue {
    Stack<Integer> in;
    Stack<Integer> out;
    public MyQueue() {
        in=new Stack<>();
        out=new Stack<>();
    }
    public void push(int x) {
        in.add(x);
    }
    public int pop() {
        if(out.size()==0){
            while(in.size()>0){
                out.push(in.pop());
            }
        }
        int res=out.pop();
        return res;
    }
    
    public int peek() {
       if(out.size()==0){
            while(in.size()>0){
                out.push(in.pop());
            }
        }
        int res=out.peek();
        return res;
    }
    
    public boolean empty() {
        return in.size()==0&&out.size()==0;
    }
}

225. 用队列实现栈 (opens new window)

1.单队列模拟栈

每次出栈操作时。只需要重新将队列的元素倒出来再重新装入队列中，最后一个导出来的元素就是“栈顶元素”。

class MyStack {
    Deque<Integer> deque;
    public MyStack() {
        deque=new LinkedList<>()
    }
    
    public void push(int x) {
        deque.offerLast(x);
    }
    
    public int pop() {
        int len=deque.size();
        while(len>1){
            deque.offerLast(deque.pollFirst());
            len--;
        }
        return deque.pollFirst();
    }

    public int top() {
        int len=deque.size();
        while(len>1){
            deque.offerLast(deque.pollFirst());
            len--;
        }
        int res=deque.peekFirst();
        deque.offerLast(deque.pollFirst());
        return res;
    }
    
    public boolean empty() {
        return deque.size()==0;
    }
}