47 lines
1.7 KiB
Markdown
47 lines
1.7 KiB
Markdown
# 3.3. Stack of plates
|
|
|
|
> Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetO-fStacks 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 werejust a single stack)
|
|
|
|
Follow up: implement popAt(int index), to pop an element in a specific stack in the list of stacks.
|
|
|
|
## First idea
|
|
|
|
```java
|
|
class SetOfStacks {
|
|
Arraylist<Stack> stacks new Arraylist<Stack>();
|
|
public void push(int v) { ... }
|
|
public int pop() {... }
|
|
}
|
|
```
|
|
|
|
Push must call the push function on the last stack in the array of stacks. But if the last stack is at capacty, create new stack.
|
|
|
|
```java
|
|
void push(int v) {
|
|
Stack last= getlastStack();
|
|
if (last != null && !last.isFull()) { //add to last stack
|
|
last.push(v);
|
|
} else { //must create new stack
|
|
Stack stack = new Stack(capacity);
|
|
stack.push(v);
|
|
stacks.add(stack);
|
|
}
|
|
}
|
|
```
|
|
|
|
Pop should behave in similar way to `push`, it should operate on the last stack. If, after popping, the last stack is empty, remove the stack from the list of stacks.
|
|
|
|
```java
|
|
int pop() {
|
|
Stack last= getlastStack();
|
|
if (last == null) throw new EmptyStackException();
|
|
int v = last.pop();
|
|
if (last.size== 0) stacks.remove(stacks.size() - 1);
|
|
return v;
|
|
}
|
|
```
|
|
|
|
## Follow up
|
|
|
|
[Code in Github](https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2003.%20Stacks%20and%20Queues/Q3_03_Stack_of_Plates).
|