Staqueue.py

#!/usr/bin/python

class Stack:

	def __init__(self):
		self.__data=[]

	def push(self,x):
		self.__data.append(x)

	def pop(self):
                if self.__data:
		    return self.__data.pop()

	def size(self):
		return len(self.__data)


class Staqueue:
	'''A queue implementation using two stacks'''

	def __init__(self):
		self.__a=Stack()
		self.__b=Stack()
		self.__min=[]

	def enqueue(self,x):
		self.__min.append(x)
		
		t,i=self.__min[-1],-2 ##Extra O(n) space needed, where n is the number of elements in Staqueue
		while i>=-len(self.__min) and t<self.__min[i]:
			self.__min[i]=t
			i-=1

		self.__a.push(x)

	def dequeue(self):
		temp=None
		if not self.__b.size():
			while self.__a.size():
				self.__b.push(self.__a.pop())
		temp=self.__b.pop()

		self.__min=self.__min[1:]
		
		return "Empty Staqueue!" if temp==None else temp

	def getMinimum(self):
		if self.__min:
			return self.__min[0]


if __name__ == "__main__":
	from random import choice
	
	a=Staqueue()
	
	l=[choice(range(1,500)) for i in range(1,10)]
	print l,"\n"	

	for j in l:
		a.enqueue(j)

	for k in range(len(l)):
		print a.dequeue(),'\t',a.getMinimum()