Solution: Implement Queue Using Stacks

Statement#

Design a custom queue, MyQueue, using only two stacks. Implement the Push(), Pop(), Peek(), and Empty() methods:

• Void Push(int x): Pushes element to the back of the queue.
• Int Pop(): Removes and returns the element from the front of the queue.
• Int Peek(): Returns the element at the front of the queue.
• Boolean Empty(): Returns TRUE if the queue is empty. Otherwise FALSE.

You are required to only use the standard stack operations, which means that only the Push() to top, Peek() and Pop() from the top, Size(), and Is Empty() operations are valid.

Note: In some interview questions, Void Push(int x) and Int Pop() might be referred to as Void Enqueue(int x) and Int Dequeue(), respectively.

Constraints:

• $1 <=$ x $<= 100$
• A maximum of $100$ calls can be made to Push(), Pop(), Peek(), and Empty()
• The Pop() and Peek() methods will always be called on non-empty stacks.

Solution#

A queue is a first in, first out (FIFO) data structure, while a stack is a last in, first out (LIFO) data structure. We will use two stacks, stack1 and stack2, to preserve the FIFO property of a queue.

• Push(): Whenever a new element is to be pushed, we will pop all elements from stack1 and push into stack2 so that the latest element is pushed to the bottom of stack1. We will then pop the elements from stack2 and push back into stack1, preserving the FIFO order.

• Pop(): Since the order of insertion was preserved during Push(), we will simply Pop() from the top of stack1.

• Empty(): Since stack1 contains all the elements, its size is checked to see if the queue is empty.

• Peek(): We will return the top of stack1, which is the front of the queue, because the FIFO order was preserved.

The slides below illustrate how we would like the algorithm to run:

Let’s take a look at the code for this solution below:

Time complexity#

• Push() has a time complexity of $O(n)$, where $n$ is the number of elements. We transfer all the elements to stack2 and back, making the total number of operations in $O(n)$.
• Pop() has a time complexity of $O(1)$ because the top of the stack points to the front of the queue.
• Empty() has a time complexity of $O(1)$.
• Peek() has a time complexity of $O(1)$ because the front is returned.

Space complexity#

• Push() has a space complexity of $O(n)$, where $n$ is the number of elements. We use two stacks to store the elements in the form of a queue, making the total space complexity to be $2.n$, which can be represented as $O(n)$.
• Pop() has a space complexity of $O(1)$.
• Empty() has a space complexity of $O(1)$.
• Peek() has a space complexity of $O(1)$.