03.04. Implement Queue using Stacks

Description

Implement a MyQueue class which implements a queue using two stacks.

Example:


MyQueue queue = new MyQueue();



queue.push(1);

queue.push(2);

queue.peek();  // return 1

queue.pop();   // return 1

queue.empty(); // return false

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).

Solutions

Solution 1: Double Stack

We use two stacks, where stk1 is used for enqueue, and another stack stk2 is used for dequeue.

When enqueueing, we directly push the element into stk1. The time complexity is $O(1)$.

When dequeueing, we first check whether stk2 is empty. If it is empty, we pop all elements from stk1 and push them into stk2, and then pop an element from stk2. If stk2 is not empty, we directly pop an element from stk2. The amortized time complexity is $O(1)$.

When getting the front element, we first check whether stk2 is empty. If it is empty, we pop all elements from stk1 and push them into stk2, and then get the top element from stk2. If stk2 is not empty, we directly get the top element from stk2. The amortized time complexity is $O(1)$.

When checking whether the queue is empty, we only need to check whether both stacks are empty. The time complexity is $O(1)$.