Implement Queue using Stacks

QueueStackDesign

20 min

Problem Statement

Implement a first in, first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

MyQueue() initializes the object.
void push(int x) pushes element x to the back of the queue.
int pop() removes the element from the front of the queue and returns it.
int peek() returns the element at the front of the queue.
boolean empty() returns true if the queue is empty, false otherwise.

Example

Example 1:

Operation Sequence:

push(1)returns: 1

push(2)returns: 2

peek()returns: 1

pop()returns: 1

empty()returns: false

Solution

The core idea is to use two stacks, `s1` and `s2`, to simulate a queue. `s1` will be used for push operations, and `s2` will be used for pop and peek operations. This amortized approach gives us O(1) time complexity for most operations.

Algorithm Steps

For `push`, simply push the element onto `s1`.
For `pop` and `peek`, if `s2` is empty, we must transfer all elements from `s1` to `s2`. This reverses the order, giving us the FIFO behavior.
After the potential transfer, `pop` removes and returns the top of `s2`, and `peek` returns the top of `s2` without removing it.
The queue is `empty` if both stacks are empty.

Stack 1 (for push)

Stack 2 (for pop/peek)

Start with two empty stacks.

Implement Queue using Stacks Solution


class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def push(self, x: int) -> None:
        self.s1.append(x)

    def pop(self) -> int:
        self.peek()
        return self.s2.pop()

    def peek(self) -> int:
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    def empty(self) -> bool:
        return not self.s1 and not self.s2