IT博客汇 | [原]LeetCode Implement Queue using Stacks

[原]LeetCode Implement Queue using Stacks

yangliuy发表于 2015-07-21 14:48:29

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.

Notes:

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

You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

思路分析：这题和几年前写过的一篇面经博文是相同的题目：面试题研究用两个栈模拟实现队列。基本做法很简单，用两个栈就可以模拟一个队列，基本思路是两次后进先出 = 先进先出，元素入队列总是入A栈，元素出队列如果B栈不为空直接弹出B栈头元素；如果B栈为空就把A栈元素出栈全部压入B栈，再弹出B栈头，这样就模拟出了一个队列。核心就是保证每个元素出栈时都经过了A，B两个栈，这样就实现了两次后进先出=先进先出。

AC Code

class MyQueue {
    // Push element x to the back of queue.
    Stack<Integer> stackA = new Stack<Integer>();
    Stack<Integer> stackB = new Stack<Integer>();
    
    
    public void push(int x) {
        stackA.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if(!stackB.isEmpty()) {
            stackB.pop();
        } else {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
            stackB.pop();
        }
    }

    // Get the front element.
    public int peek() {
        if(!stackB.isEmpty()) {
            return stackB.peek();
        } else {
            while(!stackA.isEmpty()){
                stackB.push(stackA.pop());
            }
            return stackB.peek();
        }
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return (stackA.isEmpty() && stackB.isEmpty());
    }
}