This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).
We'll use two stacks (left and right) to implement the queue. The left stack will be used for enqueue and the right stack will be used for dequeue.
To prevent multiple dequeue calls from needlessly shifting elements around between the stacks, we'll shift elements in a lazy manner.
Complexity:
Complexity:
Complexity:
In [1]:
%run ../stack/stack.py
In [2]:
class QueueFromStacks(object):
def __init__(self):
self.left_stack = Stack()
self.right_stack = Stack()
def shift_stacks(self, source, destination):
while source.peek() is not None:
destination.push(source.pop())
def enqueue(self, data):
if self.left_stack.is_empty() and not self.right_stack.is_empty():
self.shift_stacks(self.right_stack, self.left_stack)
self.left_stack.push(data)
def dequeue(self):
if self.right_stack.is_empty() and not self.left_stack.is_empty():
self.shift_stacks(self.left_stack, self.right_stack)
return self.right_stack.pop()
In [3]:
%%writefile test_queue_from_stacks.py
from nose.tools import assert_equal
class TestQueueFromStacks(object):
def test_queue_from_stacks(self):
print('Test: Dequeue on empty stack')
queue = QueueFromStacks()
assert_equal(queue.dequeue(), None)
print('Test: Enqueue on empty stack')
print('Test: Enqueue on non-empty stack')
print('Test: Multiple enqueue in a row')
num_items = 3
for i in range(0, num_items):
queue.enqueue(i)
print('Test: Dequeue on non-empty stack')
print('Test: Dequeue after an enqueue')
assert_equal(queue.dequeue(), 0)
print('Test: Multiple dequeue in a row')
assert_equal(queue.dequeue(), 1)
assert_equal(queue.dequeue(), 2)
print('Test: Enqueue after a dequeue')
queue.enqueue(5)
assert_equal(queue.dequeue(), 5)
print('Success: test_queue_from_stacks')
def main():
test = TestQueueFromStacks()
test.test_queue_from_stacks()
if __name__ == '__main__':
main()
In [4]:
%run -i test_queue_from_stacks.py