Stack of Plates: 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.
Hints: #64, #87
解答
可以用Stack of Stacks来解决，当push超过capacity的时候，追加一个Stack。每次pop都从top Stack中pop。
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
|
public class SetOfStacks {
private Stack<Stack> stackOfStacks = new Stack<>();
private int capacity;
public SetOfStacks(int capacity) {
this.capacity = capacity;
pushNewStack();
}
private Stack pushNewStack() {
Stack top = new Stack<>(capacity)
stackOfStacks.push(top);
return top;
}
private Stack peekTopStack() {
return stackOfStacks.peek();
}
private Stack popTopStack() {
return stackOfStacks.pop();
}
private Stack peekTopStackUntilNotEmpty() {
Stack top = stackOfStacks.peek();
if (top != null && top.isEmpty()) {
stackOfStacks.pop();
top = stackOfStacks.peek();
}
return top;
}
public void push(Object value) {
Stack top = peekTopStack();
if (top == null) {
top = pushNewStack();
} else if (top.isFull()) {
top = pushNewStack();
}
top.push(value);
}
public Object pop() {
Stack top = peekTopStackUntilNotEmpty();
if (top == null) {
return null;
}
return top.pop();
}
public Object peek() {
Stack top = peekTopStackUntilNotEmpty();
if (top == null) {
return null;
}
return top.peek();
}
public boolean isEmpty() {
Stack top = peekTopStackUntilNotEmpty)();
if (top == null) {
return true;
}
return top.isEmpty();
}
}
|
解答FOLLOW UP
如果在Stack 1 pop了一个元素，那么就得把 Stack 2的一个元素弄到Stack 1里去，以此类推把Stack 3、4、5 …的都挪动一下。
用一个ArrayList存放Stack，Stack提供一个从Bottom移除元素的方法。
评论