232. Implement Queue using Stacks.md

232. Implement Queue using Stacks

Question

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Thinking:

• Method 1：通过linkedlist实现

class MyQueue {
    LinkedList<Integer> q;
    /** Initialize your data structure here. */
    public MyQueue() {
        q = new LinkedList<Integer>();
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
        q.add(x);
    }
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return q.poll();
    }
    /** Get the front element. */
    public int peek() {
        return q.get(0);
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return q.isEmpty();
    }
}

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

• Method 2: 通过双栈实现

class MyQueue {
    Stack<Integer> st1;
    Stack<Integer> st2;
    /** Initialize your data structure here. */
    public MyQueue() {
        st1 = new Stack<Integer>();
        st2 = new Stack<Integer>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if(st1.isEmpty()){
            int size = st2.size();
            for(int i = 0; i < size; i++)
                st1.push(st2.pop());
        }
        st1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(st2.isEmpty()){
            int size = st1.size();
            for(int i = 0; i < size; i++)
                st2.push(st1.pop());
        }
        return st2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if(st2.isEmpty()){
            int size = st1.size();
            for(int i = 0; i < size; i++)
                st2.push(st1.pop());
        }
        return st2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return st1.isEmpty() && st2.isEmpty();
    }
}

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

二刷

1. Implement the queue using two stacks.
2. We have a stack for save values and another one for temperory saving, when we want to use peek or poll, we pop all values saved in one stack to another and read(or pop) the peek values at the top of another stack. After we finished the action, we need to pop the values back to the original stack.

class MyQueue {
    Stack<Integer> save = null;
    Stack<Integer> temp = null;
    /** Initialize your data structure here. */
    public MyQueue() {
        this.save = new Stack<>();
        this.temp = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        this.save.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        while(!this.save.empty()){
            this.temp.push(this.save.pop());
        }
        int result = this.temp.pop();
        while(!this.temp.empty()){
            this.save.push(this.temp.pop());
        }
        return result;
    }

    /** Get the front element. */
    public int peek() {
        while(!this.save.empty()){
            this.temp.push(this.save.pop());
        }
        int result = this.temp.peek();
        while(!this.temp.empty()){
            this.save.push(this.temp.pop());
        }
        return result;
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return this.save.empty();
    }
}

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