#=====================================================================
# 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() )