Describe how you could use a single array to implement three stacks.

CC150-3.1.java

public class Main {

	/**
	 * 3.1 Describe how you could use a single array to implement three stacks.
	 * 
	 * Solution:
	 * this part we could implement three stacks dynamically.
	 * the challenge here is that we need to keep track of the top and all available space.
	 * this can be done by using a Node structure holding the val and the former Node and a queue of empty cells
	 * 
	 * @Runtime & spaces
	 * runtime: O(1) 
	 * space: O(n)
	 */
	private class Node {
		int val;
		int former;

		public Node(int val, int former) {
			this.val = val;
			this.former = former;
		}
	}

	private Node[] data;
	private int[] tops = new int[3];
	private Queue<Integer> freeSpaces = new LinkedList<Integer>();

	public Main(int capacity) {
		data = new Node[capacity];
		for (int i = 0; i < capacity; i++) {
			freeSpaces.offer(i);
		}
		for (int i = 0; i < 3; i++) {
			tops[i] = -1;
		}
	}

	public void push(int stackId, int val) throws Exception {
		if (stackId > 2 && stackId < 0)
			throw new Exception("Invalid stack");
		if (freeSpaces.isEmpty())
			throw new Exception("Stack overflow");
		int currentTop = tops[stackId];
		Node newNode = new Node(val, currentTop);
		int spaceId = freeSpaces.poll();
		data[spaceId] = newNode;
		tops[stackId] = spaceId;
	}

	public void pop(int stackId) throws Exception {
		if (stackId > 2 && stackId < 0)
			throw new Exception("Invalid stack");
		int currentTop = tops[stackId];
		if (currentTop < 0)
			throw new Exception("Stack underflow");
		Node top = data[currentTop];
		int temp = top.val;
		int formerTopInd = top.former;
		data[currentTop] = null;
		tops[stackId] = formerTopInd;
		freeSpaces.offer(currentTop);
	}

	public int peek(int stackId) throws Exception {
		if (stackId > 2 && stackId < 0)
			throw new Exception("Invalid stack");
		int currentTop = tops[stackId];
		if (currentTop < 0)
			throw new Exception("Stack underflow");
		Node top = data[currentTop];
		int temp = top.val;
		return temp;
	}

//	public static void main(String[] args) {
//		// TODO Auto-generated method stub
//		Main so = new Main();
//
//	}
}