Chapter 3 Stacks and Queues - 3.5
Problem 3.5: Implement a MyQueue class which implements a queue using two stacks.

The word "two stacks" is a strong hint. I implemented my solution quickly.
from stack import *class MyQueue: def __init__(self): self.in_stack = stack() self.out_stack = stack() def enqueue(self, value): self.in_stack.push(value) def dequeue(self): # If all elements are not in out_stack if self.out_stack.size() == 0: # Pop all elements from in_stack # and push them into out_stack while self.in_stack.size() != 0: self.out_stack.push(self.in_stack.pop()) return self.out_stack.pop()# Test casesif __name__ == "__main__": my_queue = MyQueue() for i in range(0, 5): print "Enqueue", i my_queue.enqueue(i) for i in range(0, 3): print "Dequeue", my_queue.dequeue() for i in range(10, 18): print "Enqueue", i my_queue.enqueue(i) for i in range(0, 11): print "Dequeue", my_queue.dequeue()
The lesson: never stop thinking about optimization!!!