We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Implement Queue using Stacks

Difficulty: Easy

Problem Description

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

Key Insights

  • Use two stacks to simulate the behavior of a queue.
  • The first stack is used for pushing new elements.
  • The second stack is used for popping elements and providing access to the front of the queue.
  • When popping or peeking from the queue, if the second stack is empty, transfer all elements from the first stack to the second stack.

Space and Time Complexity

Time Complexity:

  • Amortized O(1) for push, pop, and peek operations due to the transfer of elements being infrequent over a series of operations.

Space Complexity:

  • O(n) where n is the number of elements in the queue, as all elements need to be stored in the two stacks.

Solution

We will use two stacks to implement the queue. The main operations of a queue (push, pop, peek, and empty) will be handled by these two stacks.

  1. Push: Always push the new element onto the first stack.
  2. Pop: To remove an element, check if the second stack is empty. If it is, pop all elements from the first stack and push them onto the second stack (reversing their order) before popping from the second stack.
  3. Peek: Similar to pop, if the second stack is empty, transfer elements from the first stack to the second stack before returning the top element of the second stack.
  4. Empty: The queue is empty if both stacks are empty.

Code Solutions

class MyQueue:

    def __init__(self):
        self.stack1 = []  # Stack to hold the incoming elements
        self.stack2 = []  # Stack to hold the outgoing elements

    def push(self, x: int) -> None:
        self.stack1.append(x)  # Push onto stack1

    def pop(self) -> int:
        self.peek()  # Ensure stack2 has the current front element
        return self.stack2.pop()  # Pop from stack2

    def peek(self) -> int:
        if not self.stack2:  # If stack2 is empty
            while self.stack1:  # Transfer elements from stack1 to stack2
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]  # Return the top of stack2

    def empty(self) -> bool:
        return not self.stack1 and not self.stack2  # Queue is empty if both stacks are empty
← Back to All Questions