[Leetcode] Implement Stack using Queues 用队列实现栈

双队列法

复杂度

时间 O(N) 空间 O(N)

思路

和Implement Queue using Stack类似，我们也可以用两个队列来模拟栈的操作。当push时，我们将数字offer进非空的队列就行了。当pop时，因为要拿的是队列最后一个数，我们先将它前面的数offer进另一个队列，然后单独拿出最后一个数，并且不再offer进另一个队列，这样，另一个队列就少了最后一个数，而我们也拿到了最后一个数，而本来的队列就变成空了，等待下次的pop操作来填满。top操作和pop一样，区别在于我们拿到最后一个数后，还要再把它offer进另一个队列中。

代码

class MyStack {        Queue<Integer> queue1;    Queue<Integer> queue2;    int size;        public MyStack(){        this.queue1 = new LinkedList<Integer>();        this.queue2 = new LinkedList<Integer>();        this.size = 0;    }        // Push element x onto stack.    public void push(int x) {        if(queue1.isEmpty()){queue2.offer(x);        } else {queue1.offer(x);        }        size++;    }    // Removes the element on top of the stack.    public int pop() {        if(size == 0){return -1;        }        int res = 0;        // 将前面的数都offer进另一个队列，然后拿出最后一个数        if(queue1.isEmpty()){for(int i = 0; i < size - 1; i++){    queue1.offer(queue2.poll());}res = queue2.poll();        } else {for(int i = 0; i < size - 1; i++){    queue2.offer(queue1.poll());}res = queue1.poll();        }        size--;        return res;    }    // Get the top element.    public int top() {        if(size == 0){return -1;        }        // 先执行pop        int top = pop();        // 然后将pop出来的数再塞回队列就行了        if(queue1.isEmpty()){queue2.offer(top);        } else {queue1.offer(top);        }        // 注意size也要加1        size++;        return top;    }    // Return whether the stack is empty.    public boolean empty() {        return size == 0;    }}