Queue via Stacks

Implement a queue using two stacks.

Solution

A queue implements a FIFO ordering, while a stack implements a LIFO ordering. Let’s say that when we push an element onto the queue, we push it onto one of the two stacks which make up that class. Now, when we want to pop an element from the queue, we need to pop the element from the bottom of that stack.

If we iterate through the stack, pushing each element onto another stack, we can reverse the order of the first stack. The first stack will have LIFO ordering, while the second stack will have FIFO ordering.

In order to save computation, we will reverse the first stack whenever we need to peek or pop an element from the queue. The implementation is as follows:

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

  def push(self, value):
    if(self.top == None):
      node = Node(value)
      self.top = node

    else:
      node = Node(value)
      node.next = self.top
      self.top = node

  def pop(self):
    value = self.top.value
    self.top = self.top.next
    return value

class Queue:
  def __init__(self):
    self.first = None
    self.last = None
    self.stack = Stack()
    self.r_stack = Stack()

  def push(self, value):
    self.stack.push(value)

  def reverse(self):
    while(self.stack.top != None):
      value = self.stack.pop()
      self.r_stack.push(value)

  def pop(self):
    self.reverse()
    value = self.r_stack.pop()
    return value