#ctci

TowerOfHanoi.java

import java.util.Stack;

public class TowerOfHanoi {
	private class HanoiStack<E> extends Stack<E> {
		String name;

		public HanoiStack(String name) {
			super();
			this.name = name;
		}
	}

	private HanoiStack<Integer> start;
	private HanoiStack<Integer> transit;
	private HanoiStack<Integer> end;
	private int n;

	public TowerOfHanoi(int n) {
		this.n = n;
		start = new HanoiStack<Integer>("start");
		transit = new HanoiStack<Integer>("transit");
		end = new HanoiStack<Integer>("end");

		for (int i = n-1; i >= 0; i++)
			start.push(i);
	}

	public void move() {
		move(n, start, transit, end);
	}

	private void move(int n, HanoiStack<Integer> from, HanoiStack<Integer> via,
			HanoiStack<Integer> to) {
		if (n == 1) {
			// base case, when there is only one element to move,
			// we can move it directly without the help of a third stack
			moveTop(from, to);
			return;
		}

		// move the top n - 1 elements from stack FROM to stack VIA through
		// stack TO
		move(n - 1, from, to, via);
		// move the top of stack FROM to stack TO
		moveTop(from, to);
		// move the top n - 1 elements from stack VIA to stack TO through stack
		// FROM
		move(n - 1, via, from, to);
	}

	private void moveTop(HanoiStack<Integer> from, HanoiStack<Integer> to) {
		int num = from.pop();
		to.push(num);
		System.out.println("move " + num + " from " + from.name + " to "
				+ to.name);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TowerOfHanoi tower = new TowerOfHanoi(3);
		tower.move();
	}

}