Chapter 三 Stacks and Queues - 3.1

Chapter 3 Stacks and Queues - 3.1
Problem 3.1: Describe how you could use a single array to implement three stacks.

Splitting the array into three individual parts is quite intuitive.

How can we take full advantage of the unused space? I was inspired by the implementation of circular queue. Actually, in my perspective, my solution is better than the one on answer page. The idea is not complicated: When there is no free space next to top of the stack, into which we want to push a value, I shift other stacks to make a free space available for the stack.

It takes me more than two hours to implement the class. Thanks to work break down method, I encapsulated some work into utility functions and made the implementation quite smooth.
from n_stacks import *if __name__ == "__main__": triple_stacks = n_stacks(3, 9) print "stack 0: length", triple_stacks.length(0) print "stack 1: length", triple_stacks.length(1) print "stack 2: length", triple_stacks.length(2) print "stack 0: push 0", triple_stacks.push(0, 0) print "stack 0: push 1", triple_stacks.push(0, 1) print "stack 0: push 2", triple_stacks.push(0, 2) print "stack 1: push 10", triple_stacks.push(1, 10) print "stack 1: push 11", triple_stacks.push(1, 11) print "stack 1: push 12", triple_stacks.push(1, 12) print "stack 2: push 20", triple_stacks.push(2, 20) print "stack 2: push 21", triple_stacks.push(2, 21) print "stack 2: push 22", triple_stacks.push(2, 22) print "stack 2: push 23", triple_stacks.push(2, 23) print "stack 0: pop", triple_stacks.pop(0) print "stack 2: push 23", triple_stacks.push(2, 23) print "stack 2: push 24", triple_stacks.push(2, 24) print "stack 1: pop", triple_stacks.pop(1) print "stack 2: push 24", triple_stacks.push(2, 24) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 0: push 2", triple_stacks.push(0, 2) print "stack 0: push 3", triple_stacks.push(0, 3) print "stack 0: push 4", triple_stacks.push(0, 4) print "stack 0: push 5", triple_stacks.push(0, 5) print "stack 0: push 6", triple_stacks.push(0, 6) print "stack 2: push 20", triple_stacks.push(2, 20) print "stack 2: push 21", triple_stacks.push(2, 21) print "stack 0: length", triple_stacks.length(0) print "stack 1: length", triple_stacks.length(1) print "stack 2: length", triple_stacks.length(2) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 0: pop", triple_stacks.pop(0) print "stack 1: push 12", triple_stacks.push(1, 12) print "stack 1: push 13", triple_stacks.push(1, 13) print "stack 1: push 14", triple_stacks.push(1, 14) print "stack 1: push 15", triple_stacks.push(1, 15) print "stack 1: push 16", triple_stacks.push(1, 16) print "stack 1: push 17", triple_stacks.push(1, 17) print "stack 0: length", triple_stacks.length(0) print "stack 1: length", triple_stacks.length(1) print "stack 2: length", triple_stacks.length(2) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 1: pop", triple_stacks.pop(1) print "stack 0: length", triple_stacks.length(0) print "stack 1: length", triple_stacks.length(1) print "stack 2: length", triple_stacks.length(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 2: pop", triple_stacks.pop(2) print "stack 0: length", triple_stacks.length(0) print "stack 1: length", triple_stacks.length(1) print "stack 2: length", triple_stacks.length(2)