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.
  • You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Interface Queue

add(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.

element()Retrieves, but does not remove, the head of this queue.

offer(E e)Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.

peek()Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

poll() Retrieves and removes the head of this queue, or returns null if this queue is empty.

remove() Retrieves and removes the head of this queue.

【解法一:用两个队列,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队首的元素就好。

// Solution 1: Use a temp queue to rearrange the original queue during push.
//             Each time the newly push item will be in the font.
//             Other operations are the same as queue.
public class MyStack {

    private Queue<Integer> q;
    Queue<Integer> temp;

    /** Initialize your data structure here. */
    public MyStack() {
        // Queue is an interface, can not be instantiated itself.
        // Use LinkedList to implement.
        q = new LinkedList<Integer>();
        temp  = new LinkedList<Integer>();
    }

    /** Push element x onto stack. */
    public void push(int x) {

        while (!q.isEmpty()) {
            temp.add(q.remove());
        }
        q.add(x);
        while (!temp.isEmpty()) {
            q.add(temp.remove());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return q.remove();
    }

    /** Get the top element. */
    public int top() {
        return q.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */ 

【解法三:一个队列,push: O(1),pop: O(n),top: O(n)】

push时直接添加到队尾就好。pop和top时,把队列除最后一个元素外,逐个循环添加到队列的尾部。

http://blog.csdn.net/ljiabin/article/details/46489545

Advertisements