LeetCode--Implement Stack using Queues-蒲公英云

LeetCode--Implement Stack using Queues

Problem:

Implement the following operations of a stack using queues.
- push(x) – Push element x onto stack.
- pop() – Removes the element on top of the stack.
- top() – Get the top element.
- empty() – Return whether the stack is empty.
Notes:

You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations
are valid.
Depending on your language, queue may not be supported natively.
You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.

Analysis:

【解法一：用两个队列，push: O(1)，pop: O(n)，top: O(n)】
用两个队列q1，q2实现一个栈。push时把新元素添加到q1的队尾。pop时把q1中除最后一个元素外逐个添加到q2中，然后pop掉q1中的最后一个元素，然后注意记得q1和q2，以保证我们添加元素时始终向q1中添加。top的道理类似。

【解法二：用两个队列，push: O(n)，pop: O(1)，top: O(1)】
所有元素都倒序保存在q1中，即后添加的元素在q1的最前端，如何做到呢？每次push时，把新元素放到空的q2，然后把q1中元素逐个添加到q2的队尾，最后交换q1和q2。这样q1队首的元素就是最后添加的元素，pop和top直接返回q1队首的元素就好。

Anwser1:

class MyStack {
    Queue<Integer> in =  new LinkedList<Integer>();
    Queue<Integer> out = new LinkedList<Integer>();
    // Push element x onto stack.
    public void push(int x) {
        in.add(x);
    }
    // Removes the element on top of the stack.
    public void pop() {
        while(in.size()>1) out.add(in.poll());
        in.poll();
        Queue<Integer> q=in;
        in = out;
        out = q;
    }
    // Get the top element.
    public int top() {
        while(in.size()>1) out.add(in.poll());
        int x = in.poll();
        out.add(x);
        Queue<Integer> q=in;
        in = out;
        out = q;
        return x;
    }
    // Return whether the stack is empty.
    public boolean empty() {
        return in.isEmpty();       
    }
}

Anwser2:

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    // Push element x onto stack.
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
    }
    // Removes the element on top of the stack.
    public void pop() {
        q1.poll();
    }
    // Get the top element.
    public int top() {
        return q1.peek();
    }
    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}