Professor Warner gave us the Stack class. (A stack is a LastIn, FirstOut (LIFO) data structure.)
(I modified it slightly.)

Testing the Stack class:
[] [3, 2, 27] [3, 2] [] [3, 2, 27] [3, 2] 
Using the structure of the Stack class, write a Queue class (a FirstIn, First Out (FIFO) data structure).
Note that 'pop()' in used in Stack removes the last element from a list, while 'pop(0)' instead removes the first element.

Test your Queue class.

The Towers of Hanoi is a classic problem that can be solved by a simple algorithm.
From the Wikipedia entry:
The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
 Only one disk may be moved at a time.
 Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
 No disk may be placed on top of a smaller disk.
We can solve this programmatically by thinking of each rod as a Stack. The last element in is the disk on top, and it must be the first one out.
Below is setting up 3 Stacks, one representing each rod, and filling rod #1 with 4 disks, where the disk labeled 4 is the largest and the disk labeled 1 is the smallest.
[4, 3, 2, 1] [] [] [4, 3, 2, 1] [] [] 
This function moves the topmost disk from the source rod to the topmost position on the destination rod.
It does a bunch of error checking to make sure you haven't tried to move a disk from an empty stack or move a disk onto a rod with a smaller one below.

[2, 1] [] [2, 1] [] 
Traceback (click to the left of this block for traceback) ... ValueError: Source Rod is empty! Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_258.py", line 10, in <module> exec compile(u"print _support_.syseval(python, u'# Try to move a disk from the empty rod to the other one\\nmoveOneDisk(testDestinationRod, testSourceRod)', __SAGE_TMP_DIR__)" + '\n', '', 'single') File "", line 1, in <module> File "/home/medlock/sage4.5.3/local/lib/python2.6/sitepackages/sagenb0.8.2py2.6.egg/sagenb/misc/support.py", line 473, in syseval return system.eval(cmd, sage_globals, locals = sage_globals) File "/home/medlock/sage4.5.3/local/lib/python2.6/sitepackages/sage/misc/python.py", line 56, in eval eval(z, globals) File "", line 1, in <module> File "", line 9, in moveOneDisk ValueError: Source Rod is empty! 
[2] [1] [2] [1] 
Traceback (click to the left of this block for traceback) ... ValueError: Target Disk is bigger than the Disk on top of Destination Rod! Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_260.py", line 10, in <module> exec compile(u"print _support_.syseval(python, u'# Try to move the next disk\\nmoveOneDisk(testSourceRod, testDestinationRod)', __SAGE_TMP_DIR__)" + '\n', '', 'single') File "", line 1, in <module> File "/home/medlock/sage4.5.3/local/lib/python2.6/sitepackages/sagenb0.8.2py2.6.egg/sagenb/misc/support.py", line 473, in syseval return system.eval(cmd, sage_globals, locals = sage_globals) File "/home/medlock/sage4.5.3/local/lib/python2.6/sitepackages/sage/misc/python.py", line 56, in eval eval(z, globals) File "", line 1, in <module> File "", line 15, in moveOneDisk ValueError: Target Disk is bigger than the Disk on top of Destination Rod! 
A very tidy way to solve this problem is recursively. The following algorithm moves n disks from rod A to rod B:
The trick to recursive programming is to define a function that calls itself to solve a subproblem. The problems keeps getting chopped up into subproblems. (Move 4 disks is chopped into move 3 disks and move 1 disk; the move 3 disk part is chopped into move 2 disks and move 1 disk...) The recursion should keep chopping the problem up until, at the bottom, the smallest subproblems are trivial to solve.
Write a function that implements the above recursive algorithm, making use of the above function 'moveOneDisk' to do the middle step.
To see what is going on, put 'print rodA, rodB, rodC' just before and just after the middle step.

Test your recursive function by solving the puzzle with 4 disks.
The first output is '[4, 3, 2, 1] [] []'.
The last output should be '[] [] [4, 3, 2, 1]' if you solved the puzzle.
[4, 3, 2, 1] [] [] [4, 3, 2, 1] [] [] [4, 3, 2] [] [1] [4, 3, 2] [] [1] [4, 3, 2, 1] [] [] [4, 3, 2, 1] [] [] [4, 3, 2] [] [1] [4, 3, 2] [] [1] 
