Leetcode – Implement Queue using Stacks Solution in Python

Spread the love

Introduction

The “Implement Queue using Stacks” is a classical problem which can be found on LeetCode. It falls under the category of data structures and is often asked in coding interviews. The task focuses on testing one’s ability to manipulate and efficiently use fundamental data structures. In this extensive article, we will discuss the problem statement, understand the concept of queue and stack, and explore various approaches to implement a queue using stacks in Python. Additionally, we will evaluate the time and space complexities of each approach.

Problem Statement

The problem requires you to implement a queue using instances of stack data structure. Specifically, the problem states:

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, pop, peek, and empty).

Input

  • push(x): Add an element x to the back of the queue.
  • pop(): Remove the element from the front of the queue and return it.
  • peek(): Return the element at the front of the queue without removing it.
  • empty(): Return True if the queue is empty, False otherwise.

Understanding Queue and Stack

Before we delve into the solutions, let’s briefly discuss what queues and stacks are:

  • Queue: A queue is a linear data structure that follows a First In First Out (FIFO) order for accessing elements. Elements are added (enqueued) to the back and removed (dequeued) from the front.
  • Stack: A stack is a linear data structure that follows a Last In First Out (LIFO) order for accessing elements. Elements are added (pushed) and removed (popped) from the top.

Approach 1: Two Stacks with Amortized O(1) Push Operation

We can use two stacks, namely inputStack and outputStack. inputStack is used to make the push operation efficient, while outputStack is used for the pop and peek operations.

  1. For push(x), simply push x onto inputStack.
  2. For pop(), if outputStack is empty, pop all elements from inputStack and push them onto outputStack. Then, pop the top element from outputStack.
  3. For peek(), similar to pop(), but instead of popping, return the top element of outputStack.
  4. For empty(), return True if both stacks are empty, False otherwise.
class MyQueue:

    def __init__(self):
        # Initialize two stacks
        self.inputStack = []
        self.outputStack = []

    def push(self, x):
        # Push element x to the inputStack
        self.inputStack.append(x)

    def pop(self):
        # If outputStack is empty, pop all elements from inputStack and push them onto outputStack
        if not self.outputStack:
            while self.inputStack:
                self.outputStack.append(self.inputStack.pop())
        # Pop the top element from outputStack
        return self.outputStack.pop()

    def peek(self):
        # Similar to pop, but instead of popping return the top element of outputStack
        if not self.outputStack:
            while self.inputStack:
                self.outputStack.append(self.inputStack.pop())
        return self.outputStack[-1]

    def empty(self):
        # Return True if both stacks are empty, False otherwise
        return not self.inputStack and not self.outputStack

Time Complexity

  • push(x) has an amortized time complexity of O(1).
  • pop() and peek() have an amortized time complexity of O(1) because each element is moved from inputStack to outputStack once.
  • empty() has a time complexity of O(1).

Space Complexity

The space complexity is O(n), where n is the number of elements in the queue.

Approach 2: Two Stacks with O(1) Pop Operation

This approach is the reverse of the first approach. The idea is to make the pop operation efficient instead of the push operation.

  1. For push(x), pop all elements from inputStack and push them onto outputStack. Push x onto inputStack. Pop all elements from outputStack and push them back onto inputStack.
  2. For pop(), simply pop the top element from inputStack.
  3. For peek(), return the top element of inputStack.
  4. For empty(), return True if inputStack is empty, False otherwise.
class MyQueue:

    def __init__(self):
        # Initialize two stacks
        self.inputStack = []
        self.outputStack = []

    def push(self, x):
        # Pop all elements from inputStack and push them onto outputStack
        while self.inputStack:
            self.outputStack.append(self.inputStack.pop())
        # Push x onto inputStack
        self.inputStack.append(x)
        # Pop all elements from outputStack and push them back onto inputStack
        while self.outputStack:
            self.inputStack.append(self.outputStack.pop())

    def pop(self):
        # Pop the top element from inputStack
        return self.inputStack.pop()

    def peek(self):
        # Return the top element of inputStack
        return self.inputStack[-1]

    def empty(self):
        # Return True if inputStack is empty, False otherwise
        return not self.inputStack

Time Complexity

  • push(x) has a time complexity of O(n).
  • pop() and peek() have a time complexity of O(1).
  • empty() has a time complexity of O(1).

Space Complexity

The space complexity is O(n), where n is the number of elements in the queue.

Conclusion

In this article, we examined the “Implement Queue using Stacks” problem, understood the fundamental characteristics of queue and stack data structures, and explored two distinct approaches to implement a queue using stacks. The first approach optimizes the push operation, whereas the second approach optimizes the pop operation. The choice between the approaches depends on the expected usage patterns of the queue. It’s important to understand the trade-offs between different approaches and choose the one that best fits the problem’s requirements. This problem exemplifies how one can build sophisticated data structures by combining simpler ones in innovative ways.

Leave a Reply