Stack of Plates

Problem

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.

Solution

  1. push(), to the last stack, if last full, create new stack. So, in a way, rather than stack overflow exception, return boolean if the stack is full.
  2. pop(), pop from the last stack, if last is empty, then delete stack
  3. popAt(int index), pop from “index”th stack, will ignore empty spaces to save time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

// Array implementation
class MyStack {

	private int top = -1;

	private int[] buffer;

	private int capacity;

	MyStack(int capacity) {
		this.capacity = capacity;
		buffer = new int[capacity];
	}

	public void push(int v) {
		buffer[++top] = v;
	}

	public int pop() {

		return buffer[top--];
	}
	// if the stack is at capacity
	public Boolean isAtCapacity() {
		return capacity == top + 1;
	}
	//return the size of the stack
	public int size() {
		return top + 1;
	}

	public String toString() {
		String s = "";
		int index = top;

		while (index >= 0) {
			s += "[" + buffer[index--] + "]" + " -> ";
		}

		return s;

	}
}
1

([credits](http://jitingxu.wordpress.com/2013/08/20/3-3-magine-a-literal-stack-of-plates-if-the-stack-gets-too-high-it-might-topple-there-fore-in-real-life-we-would-likely-start-a-new-stack-when-the-previous-stack-exceeds-some-threshold-implem/))
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101

import java.util.ArrayList;


public class SetOfStacks {

	private int threshold;

	private ArrayList<MyStack> setOfStacks = new ArrayList<>();

	SetOfStacks(int threshold) {
		this.threshold = threshold;
	}
	//get the last stack
	public MyStack getLastStack() {
		int size = setOfStacks.size();

		if (size <= 0) {
			return null;
		}
		else {
			return setOfStacks.get(size - 1);
		}
	}

	//get the nth stack
	public MyStack getNthStack(int n) {
		int size = setOfStacks.size();

		if (size <= 0) return null;
		else return setOfStacks.get(n - 1);
	}

	//push value
	public void push(int value) {
		MyStack lastStack = this.getLastStack();

		if (lastStack == null) {
			lastStack = new MyStack(threshold);
			lastStack.push(value);
			setOfStacks.add(lastStack);
		} else {
			if (!lastStack.isAtCapacity())
				lastStack.push(value);
			else {
				MyStack newLastStack = new MyStack(threshold);
				newLastStack.push(value);
				setOfStacks.add(newLastStack);
			}
		}
	}
	// the pop
	public int pop() {
		MyStack lastStack = this.getLastStack();
		int v = lastStack.pop();

		if (lastStack.size() == 0) setOfStacks.remove(setOfStacks.size() - 1);
		return v;
	}

	//pop the nth stack
	public int pop(int nth) {
		MyStack nthStack = this.getNthStack(nth);
		int v = nthStack.pop();

		if (nthStack.size() == 0) setOfStacks.remove(setOfStacks.size() - 1);
		return v;

	}

	public String toString() {
		String s = "";

		for (int i = 0; i < setOfStacks.size(); i++) {
			MyStack stack = setOfStacks.get(i);
			s = "||" + stack.toString() + s;
		}

		return s;
	}

	public static void main(String[] args) {
		SetOfStacks stacks = new SetOfStacks(3);
		stacks.push(1);
		stacks.push(2);
		stacks.push(3);
		stacks.push(4);
		stacks.push(5);
		stacks.push(6);
		stacks.push(7);
		System.out.println("the stack is: " + stacks);
		stacks.pop(1);
		System.out.println("pop 1st: " + stacks);
		stacks.pop(2);
		System.out.println("pop 2nd stack: " + stacks);
		stacks.pop(1);
		System.out.println("pop 1st stack: " + stacks);
		stacks.pop(2);
		System.out.println("pop 2nd stack: " + stacks);

	}
}