Skip to content

Instantly share code, notes, and snippets.

@nealhu
Created July 4, 2014 02:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nealhu/36b8feb85c435958e9b6 to your computer and use it in GitHub Desktop.
Save nealhu/36b8feb85c435958e9b6 to your computer and use it in GitHub Desktop.
CC_3_3
// Cracking the Coding Interview
// 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.
import java.util.LinkedList;
import java.util.ArrayList;
class SetOfStacks<T> {
private ArrayList<LinkedList<T>> stacks;
private int capacity;
public SetOfStacks(int c) {
capacity = c;
stacks = new ArrayList<LinkedList<T>>();
}
public T pop() throws Exception {
if (!stacks.isEmpty()) {
int size = stacks.size();
if (!stacks.get(size-1).isEmpty()) {
T tmp = stacks.get(size-1).pop();
if (stacks.get(size-1).isEmpty()) {
stacks.remove(size-1);
}
return tmp;
} else {
throw new Exception();
}
} else {
throw new Exception();
}
}
public void push(T element) {
if (stacks.isEmpty()) {
stacks.add(new LinkedList<T>());
}
int size = stacks.size();
if (stacks.get(size-1).size() >= capacity) {
// new stack
stacks.add(new LinkedList<T>());
stacks.get(size).push(element);
} else {
stacks.get(size-1).push(element);
}
}
public T popAt(int index) throws Exception {
if (index >= stacks.size() || stacks.get(index).isEmpty()) {
throw new Exception();
}
T tmp = stacks.get(index).pop();
rollover(index);
return tmp;
}
// move the end of next stack to current stack
private void rollover(int index) {
if (index == stacks.size()-1) {
// last stack
// remove it if it's empty
if (stacks.get(index).isEmpty()) {
stacks.remove(index);
}
return;
} else {
stacks.get(index).push(stacks.get(index+1).removeLast());
rollover(index+1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment