Sort Stack: Write a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.
Hints: #15, #32, #43
解法1
就是要把一个Stack排序，最小的元素在top，最大的元素在bottom。
弄一个临时的Stack，保证Stack的顺序是从大到小，最后再把这个Stack压回原Stack，这样原来Stack就变成从小到大了。
应该会牵涉到递归。
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
|
// 保证最小元素压到最下面，即newVal必须 >= top
public void pushSort(Stack stack, int newVal) {
if (stack.isEmpty()) {
stack.push(newVal);
return;
}
int oldVal = stack.peek();
if (newVal < oldVal) {
// 暂且把top拿掉
stack.pop();
// 把newVal push到Stack中
pushSort(stack, newVal);
// 把top放回来
stack.push(oldVal);
return;
}
stack.push(newVal);
}
public void sortStack(Stack stack) {
Stack tmp = new Stack();
while (!stack.isEmpty()) {
pushSort(tmp, stack.pop());
}
while (!tmp.isEmpty()) {
stack.push(tmp.pop());
}
}
|
解法2
可以不用递归，比如下面S1是要排序的Stack，S2是一个保持大到小顺序的Stack，现在要把5放到S2怎么弄？
1
2
3
4
5
6
|
| S1 | S2 |
|------|------|
| | 12 |
| 5 | 8 |
| 10 | 3 |
| 7 | 1 |
|
步骤这样的：
Step 1：先把 5 pop出来；Step 2：把 12、8 pop & push 到S1；Step 3：把 5 push到S2。
1
2
3
4
5
6
7
|
Step 1 Step 2 Step 3
| S1 | S2 | | S1 | S2 | | S1 | S2 |
|------|------| |------|------| |------|------|
| | 12 | | 8 | | | 8 | |
| | 8 | -> | 12 | | -> | 12 | 5 |
| 10 | 3 | | 10 | 3 | | 10 | 3 |
| 7 | 1 | | 7 | 1 | | 7 | 1 |
|
注意：做这个题目之前得先画图，例子不能太简单，否则你很难发现解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public void sortStack(Stack stack) {
Stack s2 = new Stack();
while (!stack.isEmpty()) {
int val = stack.pop();
while (!s2.isEmpty() && s2.peek() > val) {
stack.push(s2.pop());
}
s2.push(val);
}
while (!s2.isEmpty()) {
stack.push(s2.pop());
}
}
|
评论