首页 > 代码库 > CC150 3.3
CC150 3.3
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.
interface SetOfStacks<T> { push(T t); T pop(); T popAt(); static final int SUM_LENGTH = 10; } class SetOfStacksImpl<T> implements SetOfStacks { Stack<T>[] subStacks; int cur; SetOfStacksImpl() { // Initialize sub stacks array. subStacks = new Stack<T>[100]; subStacks[0] = initStack(); cur = 0; } push(T t) { if (t == null) return; if (subStacks[cur].isFull()) { if (cur >= subStacks.length) { // resize subStacks // or throw new OverFlowException(); } // Add new stack at head. Stack<T> newStack = initStack(); cur++; } subStacks[cur].push(t); } T pop() { T t = subStacks[cur].pop; while (curStacks[cur].isEmpty() && cur >= 0) { cur --; } return t; } T popAt(int i) { if (i > cur || i >= subStacks.length || i < 0) return null; T t = subStacks[i].pop(); // Only shrink when i is cur if (i == cur) { while (curStacks[cur].isEmpty() && cur >= 0) cur --; } return t; } }
A better solution? Instead of using a linked list holding sub stacks, using a map<stackIndex, stack>.
The benefit is that popAt(int) would be O(1).
Not a huge difference.
CC150 3.3