C3P3.java

package chapter3;
/*
 * Career Cup 3.3
 *
 * Imagine a (literal) stack of plates. If the stack gets too high, 
 * it might topple. Therefore, in real life, we would likely start 
 * a new stack when the previous stack exceeds some threshold. 
 *
 * Implement a data structure SetOfStacks that mimics this. SetOfStacks 
 * should be composed of several stacks and should create a new stack 
 * once the previous one exceeds capacity.SetOfStacks.push() and 
 * SetOfStacks.pop() should behave identically to a single stack 
 * (that is, pop() should return the same values as it would 
 * if there were just a single stack).
 *
 * FOLLOW UP
 * Implement a function popAt(int index) which performs a pop 
 * operation on a specific sub-stack.
 */
public class C3P3 {

  static class StackWithLimitedSize {
		final static int CAPACITY = 2;
		int top = -1;
		int array[] = new int[CAPACITY];
		StackWithLimitedSize next;

		public boolean isEmpty() {
			return top == -1;
		}

		public boolean isFull() {
			return top == CAPACITY - 1;
		}

		public void push(int data) {
			array[++top] = data;
		}

		public int pop() {
			return array[top--];
		}

		public int peek() {
			return array[top];
		}
	}

	static class SetofStacks {
		StackWithLimitedSize top = null;

		public int popAt(int index) {
			StackWithLimitedSize pStack = top, prev = null;
			while (--index > 0) {
				prev = pStack;
				pStack = pStack.next;
			}
			int data = pStack.pop();
			if(pStack.isEmpty())
				prev.next = pStack.next;
			return data;
		}

		public void push(int data) {
			if (top == null || top.isFull()) {
				StackWithLimitedSize stack = new StackWithLimitedSize();
				stack.push(data);
				stack.next = top;
				top = stack;
			} else {
				top.push(data);
			}
		}

		public int pop() {
			int data = top.pop();
			if (top.isEmpty())
				top = top.next;
			return data;
		}

		public int peek() {
			return top.peek();
		}

		public boolean isEmpty() {
			return top == null;
		}

	}

	public static void main(String[] args) {
		SetofStacks setofStacks = new SetofStacks();
		setofStacks.push(1);
		setofStacks.push(2);
		setofStacks.push(3);
		System.out.println(setofStacks.popAt(2));
		System.out.println(setofStacks.popAt(2));
		System.out.println(setofStacks.pop());
		System.out.println(setofStacks.isEmpty());
	}

}