#CC150 #CC150-chap3 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 structureSetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new sta…

SetOfStacks.java

package chap3;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 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 structureSetOf Stacks
 * that mimics this. SetOf Stacks should be composed of several stacks and
 * should create a new stack once the previous one exceeds capacity.
 * SetOfStacks.push() and SetOfStacks.pop() should be have 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.
 * 
 * @author xl16
 * 
 */

/*
 * Use an array to keep track of the stacks. When pushing, create a new stack if
 * the latest stack exceeds the capacity. When popping, delete the current stack
 * if it is empty.
 * 
 * Follow Up: just pop from the target stack from the array. Allow the stacks to
 * be empty. Need to discuss this with the interviewer. Time: push, pop: O(1)
 * Space: O(n)
 */

public class SetOfStacks {
	private int maxSize;
	private int totalSize;
	private List<Stack> stacks;

	public SetOfStacks(int maxSize) {
		this.maxSize = maxSize;
		totalSize = 0;
		stacks = new ArrayList<Stack>();
	}

	private Stack getLatestStack() {
		if (stacks.size() == 0) {
			return null;
		}
		return stacks.get(stacks.size() - 1);
	}

	public void push(Object item) {
		totalSize++;
		int stackIndex = (totalSize - 1) / maxSize;
		// Create a new Stack
		if (stacks.size() - 1 < stackIndex) {
			Stack newStack = new Stack();
			newStack.push(item);
			stacks.add(newStack);
		} else {
			// Push the item to the latest stack
			getLatestStack().push(item);
		}
	}

	public Object pop() {
		Stack latestStack = getLatestStack();
		if (latestStack == null || latestStack.empty()) {
			return null; // or throw empty stack exception
		}
		Object item = latestStack.pop();
		// Remove the stack from the set of stacks
		if (latestStack.empty()) {
			stacks.remove(latestStack);
		}
		totalSize--;
		return item;
	}

	/**
	 * FOLLOW UP: Need to discuss with the interviewer. Can we allow the stacks
	 * to not be full? Do we need to delete a stack when it is empty?
	 * 
	 * Below we allow stacks to be not full, and empty. The popAt operation does
	 * not affect the totalSize.
	 * 
	 * The solution in the book rolls elements over.
	 * 
	 * @param i
	 * @return
	 */
	public Object popAt(int i) {
		if (stacks.get(i) == null) {
			return null;// Or throw empty stack exception
		}
		Object item = stacks.get(i).pop();
		// Discuss this with the interviewer
		if (stacks.get(i).empty()) {
			stacks.remove(i);
		}
		return item;
	}

	public String toString() {
		String str = "";
		for (Stack stack : stacks) {
			str += "stack " + stack.toString() + "->";
		}
		return str;
	}

	public static void main(String[] args) {
		SetOfStacks setOfStacks = new SetOfStacks(2);
		setOfStacks.push(1);
		System.out.println(setOfStacks.toString());
		setOfStacks.push(2);
		System.out.println(setOfStacks.toString());
		setOfStacks.pop();
		System.out.println(setOfStacks.toString());
		setOfStacks.pop();
		System.out.println(setOfStacks.toString());
		setOfStacks.push(4);
		System.out.println(setOfStacks.toString());
	}
}