Leetcode – Implement Stack using Queues Solution in Python

Spread the love

Introduction

Stacks and queues are two of the most fundamental data structures in computer science, often serving as building blocks for more complex structures. In this detailed article, we will explore an interesting problem from LeetCode: implementing a stack using queues. This exercise tests your knowledge of stack and queue operations, and your creativity in using them interchangeably. We will delve into the problem, discuss the fundamental operations required, and examine different methods to implement a stack using queues in Python.

Problem Description

The problem “Implement Stack using Queues” (LeetCode #225) can be defined as follows:

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (push, top, pop, and empty).

This means that by using only queues (which are first-in-first-out, FIFO), we must simulate a stack.

Approach 1: Using Two Queues, Making Push Operation Costly

  1. Initialize two queues, q1 and q2.
  2. To perform the push operation, enqueue the element in q2, then dequeue all elements from q1 and enqueue them in q2. Swap the names of q1 and q2.
  3. The pop operation dequeues an element from q1.
  4. The top operation retrieves the front of q1.
  5. The empty operation checks if q1 is empty.
from queue import Queue

class MyStack:
    def __init__(self):
        self.q1 = Queue()
        self.q2 = Queue()

    def push(self, x):
        self.q2.put(x)
        while not self.q1.empty():
            self.q2.put(self.q1.get())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self):
        return self.q1.get()

    def top(self):
        return self.q1.queue[0]

    def empty(self):
        return self.q1.empty()

Approach 2: Using Two Queues, Making Pop Operation Costly

  1. Initialize two queues, q1 and q2.
  2. To perform the push operation, enqueue the element in q1.
  3. To perform the pop operation, dequeue all but one element from q1 and enqueue them in q2, then dequeue and return the last element from q1. Swap the names of q1 and q2.
  4. The top operation retrieves the last enqueued element.
  5. The empty operation checks if q1 is empty.
from queue import Queue

class MyStack:
    def __init__(self):
        self.q1 = Queue()
        self.q2 = Queue()
        self.top_element = None

    def push(self, x):
        self.q1.put(x)
        self.top_element = x

    def pop(self):
        while self.q1.qsize() > 1:
            self.top_element = self.q1.get()
            self.q2.put(self.top_element)
        popped_element = self.q1.get()
        self.q1, self.q2 = self.q2, self.q1
        return popped_element

    def top(self):
        return self.top_element

    def empty(self):
        return self.q1.empty()

Complexity Analysis

  • In Approach 1, the push operation is O(n), while pop, top, and empty are O(1).
  • In Approach 2, the push operation is O(1), while pop is O(n), and top and empty are O(1).

Testing the Implementation

Let’s test the stack implementation with some operations.

stack = MyStack()
stack.push(1)
stack.push(2)
print(stack.top())    # returns 2
print(stack.pop())    # returns 2
print(stack.empty())  # returns False

Conclusion

The “Implement Stack using Queues” problem is an excellent exercise to grasp the mechanics of stacks and queues and to cultivate adaptability in using data structures. Through the two approaches discussed – making either the push or pop operation costly – we gain insights into the trade-offs between different implementations.

Leave a Reply