CC_3_1

ThreeStack.java

// Cracking the Coding Interview
// 3.1  Describe how you could use a single array to implement three stacks.

class ThreeStack {
	public static final int TOTAL_SIZE = 10;
	public static int[] buf = new int[TOTAL_SIZE];
	private static int[] offset = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] start = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] end = new int[]{0, TOTAL_SIZE/3, TOTAL_SIZE*2/3};
	private static int[] length = new int[3];
	private static int[] capacity = new int[] {TOTAL_SIZE/3, TOTAL_SIZE/3, TOTAL_SIZE - TOTAL_SIZE/3*2};

	public static void push(int stackNum, int value) throws Exception {
		if (stackNum < 3) {
			if (length[stackNum] < capacity[stackNum]) {
				buf[end[stackNum]] = value;
				end[stackNum] = (end[stackNum] + 1 - offset[stackNum]) % capacity[stackNum] + offset[stackNum];
				length[stackNum]++;
				return;
			} 
		}
		throw new Exception();
	}
	public static int pop(int stackNum) throws Exception {
		if (stackNum < 3) {
			if (length[stackNum] > 0) {
				int tmp = buf[start[stackNum]];
				start[stackNum] = (start[stackNum] + 1 - offset[stackNum]) % capacity[stackNum] + offset[stackNum];
				length[stackNum]--;
				return tmp;
			}
		}
		throw new Exception();
	}
	public static int peek(int stackNum) throws Exception {
		if (stackNum < 3) {
			if (length[stackNum] > 0) {
				return buf[start[stackNum]];
			}
		}
		throw new Exception();
	}

}