How to implement a Queue using Stacks in Python

A common programming interview question, and for a change, one that you will actually be able to use in the job, is that of implementing a Queue by means of using Stacks in Python.

The 5 common operations of a Queue

  1. Instantiation
  2. push(val)
  3. pop()
  4. peek()
  5. empty()

What each operation does

Instantiation is the Queue’s storage object that will be used.

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []

push(val) is the way to add data to the Queue.

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack.append(x)

pop() is the way to remove and return the front element in the Queue.

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if len(self.stack) > 0:
          return self.stack.pop(0)
        else:
          return None

peek() is the way to return the front element without removing it.

    def peek(self) -> int:
        """
        Get the front element.
        """
        if len(self.stack):
          return self.stack[0]
        else:
          return None

empty() is the way to tell if a Queue is empty and contains any values.

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        if len(self.stack) > 0:
          return False
        else:
          return True

Putting it together

class MyQueue:

    def __init__(self):
        """
        Initialize the data structure
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the front element and returns it
        """
        if len(self.stack) > 0:
          return self.stack.pop(0)
        else:
          return None
        

    def peek(self) -> int:
        """
        Return the front element without removal
        """
        if len(self.stack):
          return self.stack[0]
        else:
          return None

        

    def empty(self) -> bool:
        """
        Determine if the queue is empty or not
        """
        if len(self.stack) > 0:
          return False
        else:
          return True

How to use our custom Queue

# We instantiate our Class object
obj = MyQueue()

# We add data to it
val = 123
obj.push(val)

# We pop the first element off the Queue and return it to a variable
element1 = obj.pop()

# We peek to get the first element without removal
element2 = obj.peek()

# We get a Boolean (True/False) if the Queue is empty or not
is_empty = obj.empty()
Tags:

Leave a Reply

Your email address will not be published.