Home Computer Science Java Algorithm

40 · Implement Queue by Two Stacks - LintCode

# Description

As the title described, you should only use two stacks to implement a queue's actions.

The queue should support push(element) , pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

# Solution

# 清𥇦點的版本

public class MyQueue {
    private Stack<Integer> pushS;
    private Stack<Integer> popS;
    public MyQueue() {
        // do intialization if necessary
        pushS = new Stack<Integer>();
        popS = new Stack<Integer>();
    }
    /*
     * @param element: An integer
     * @return: nothing
     */
    public void push(int element) {
        // write your code here
        moveBackItems();
        pushS.push(element);
    }
    /*
     * @return: An integer
     */
    public int pop() {
        // write your code here
        moveItems();
        return popS.pop();
    }
    /*
     * @return: An integer
     */
    public int top() {
        // write your code here
        moveItems();
        return popS.peek();
    }
    private void moveItems() {
        while (! pushS.isEmpty()) {
            popS.push(pushS.pop());
        }
    }
    private void moveBackItems() {
        while (! popS.isEmpty()) {
            pushS.push(popS.pop());
        }
    }
}
# 直觀點的
public class MyQueue {
    Stack<Integer> A;
    Stack<Integer> B;
    public MyQueue() {
        A = new Stack<>();
        B = new Stack<>();
    }
    /*
     * @param element: An integer
     * @return: nothing
     */
    public void push(int element) {
        A.push(element);
    }
    /*
     * @return: An integer
     */
    public int pop() {
        while (!A.empty()) {
            B.push(A.pop());
        }
        int result = B.empty() ? -1 : B.pop();
        while (!B.empty()){
            A.push(B.pop());
        }
        return result;
    }
    /*
     * @return: An integer
     */
    public int top() {
        while (!A.empty()){
            B.push(A.pop());
        }
        int result = B.peek();
        //move B back to A
         while (!B.empty()){
            A.push(B.pop());
        }
        return result;
      
    }
}```