Dequeue
by Isai Damier, Android Engineer @ Google

#=====================================================================
# Author: Isai Damier
# Title: QueueWithStack
# Project: geekviewpoint
# Package: datastructure
#
# Description: To implement a Queue using Stack datastructure,
#    two stacks are sufficient: a stack for enqueuing and a stack
#    for dequeuing. Recall that stacks are LIFO objects (i.e. Last
#    In First Out), whereas queues are normally FIFO objects (i.e.
#    First In First Out). Hence although adding elements to a stack
#    is similar to adding elements to a queue, the removal process
#    for each datastructure is different.
#
#    Notice how in the following implementation queue.enqueue() is
#    the same as stack.put(). However, two stacks are used for
#    proper dequeuing.
#=====================================================================
 
 from Queue import LifoQueue
class QueueWithStack( object ):

  def __init__( self ):
    self.input_stack = LifoQueue()
    self.output_stack = LifoQueue()

  #=====================================================================
  # Statement:
  #   Remove an element from the queue.
  #
  # Time Complexity of Solution:
  #   Best = const Worst = O(n).
  #
  # Technical Details:
  #   0] If the output_stack stack is not empty, pop it and return the
  #      top element
  #   1] Otherwise, empty the input_stack stack into the output_stack stack
  #   2] Now pop the output_stack stack and return the element.
  #
  #=====================================================================
  def dequeue( self ):
    if not self.output_stack.empty():
      return self.output_stack.get()

    while not self.input_stack.empty():
      self.output_stack.put( self.input_stack.get() )

    return self.output_stack.get()
import unittest
from algorithms.QueueWithStack import QueueWithStack

class Test( unittest.TestCase ):
  #=====================================================================
  # Test of dequeue method, of class QueueWithStack.
  #=====================================================================

  def testDequeue( self ):
    queue = QueueWithStack()
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
    self.assertTrue( queue.isEmpty() )
    self.assertEquals( 0, queue.size() )
    for  d in data:
      queue.enqueue( d )

    self.assertFalse( queue.isEmpty() )
    self.assertEquals( len( data ), queue.size() )

    for i in range( len( data ) ):
      self.assertEquals( len( data ) - i, queue.size() )
      self.assertEquals( data[i], queue.dequeue() )


    self.assertTrue( queue.isEmpty() )
    self.assertEquals( 0, queue.size() )