Coding for Interviews: Stack 1

gistfile1.txt

# Not really a "use-case" per se, but I always thought this problem was 
# interesting because it has a really simple answer (as you can see below).
# Sometimes it is asked in coding interviews.
#
# How do you implement a Queue using only Stack data structure?

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

class Stack: 
	top = None
	
	# put at item at the front of the stack
	def push(self, item):
		node = Node(item, self.top)
		self.top = node

	# remove the first item and return it
	def pop(self):
		if self.top.next != None:
			old_top = self.top
			self.top = old_top.next
			old_top.next = None
			return old_top.item
		elif self.top != None:
			item = self.top.item
			self.top = None
			return item
		else:
			return None

	# sneak a look at the first item, but don't remove it
	def peek(self):
		return self.top.item

	def print_me(self):
		curr = self.top
		print "=== current stack ==="
		while curr != None:
			print curr.item
			curr = curr.next

class Queue:
	stack1 = None
	stack2 = None

	def __init__(self):
		self.stack1 = Stack()
		self.stack2 = Stack()

	# put an item at the end of the queue
	def enqueue(self, item):
		if self.stack1.top == None and self.stack2.top != None:
			while self.stack2.top != None:
				self.stack1.push(self.stack2.pop())
		self.stack1.push(item)

	# remove and return the oldest item
	def dequeue(self):
		if self.stack2.top == None and self.stack1.top != None:
			while self.stack1.top != None:
				self.stack2.push(self.stack1.pop())
		return self.stack2.pop()

def main():
	q = Queue()
	q.enqueue("a")
	q.enqueue("b")
	q.enqueue("c")
	print q.dequeue()
	print q.dequeue()
	q.enqueue("d")
	q.enqueue("e")
	print q.dequeue()

if __name__ == '__main__':
    main()