How to Implement a Queue Using Two Stacks in python?

By Subham, 7 months ago
  • Bookmark
0

Given the Stack class below, implement a Queue class using two stacks

Note, this is a "classic" interview problem. Use a Python list data structure as your Stack.


# Uses lists instead of your own Stack class.
stack1 = []
stack2 = []

Solution

Fill out your solution below:


class Queue2Stacks(object):
   
  def __init__(self):
     
    # Two Stacks
    self.in_stack = []
    self.out_stack = []
   
  def enqueue(self, element):
    # FILL OUT CODE HERE
    self.in_stack.append(element)
    pass
   
  def dequeue(self):
     
    # FILL OUT CODE HERE
    if not self.out_stack:
      while self.in_stack:
        self.out_stack.append(self.in_stack.pop())
    return self.out_stack.pop()
    pass

Queue
Stack
Python
1 Answer
0

Solution :

The key insight is that a stack reverses order (while a queue doesn't). A sequence of elements pushed on a stack comes back in reversed order when popped. Consequently, two stacks chained together will return elements in the same order, since reversed order reversed again is original order.


We use an in-stack that we fill when an element is enqueued and the dequeue operation takes elements from an out-stack. If the out-stack is empty we pop all elements from the in-stack and push them onto the out-stack.


class Queue2Stacks(object):
   
  def __init__(self):
     
    # Two Stacks
    self.instack = []
    self.outstack = []
   
  def enqueue(self,element):
     
    # Add an enqueue with the "IN" stack
    self.instack.append(element)
   
  def dequeue(self):
    if not self.outstack:
      while self.instack:
        # Add the elements to the outstack to reverse the order when called
        self.outstack.append(self.instack.pop())
    return self.outstack.pop()  

Your Answer

Webinars

More webinars

Related Discussions

Running random forest algorithm with one variable

View More