logo头像

不破不立

《程序员代码面试指南》用一个辅助栈实现另一个栈的排序

  一个栈中的元素类型为整型,现在将该栈从栈顶到栈底按从大到小的顺序排序,只允许申请一个辅助栈。如何利用好这个辅助栈是这道题的解题关键所在。

用一个辅助栈实现另一个栈的排序

  如何利用好这个辅助栈是这道题的解题关键所在。

题目

  一个栈中的元素类型为整型,现在将该栈从栈顶到栈底按从大到小的顺序排序,只允许申请一个辅助栈。除此之外可以申请新的变量,但不能申请额外的数据结构。如何完成排序?

实现思想

  假设存有数据的栈名A,辅助栈为B;

  1. 首先pop出A栈栈顶元素,将其push到B栈中;

  2. 接着,继续pop出A栈栈顶元素保存在变量cur中,然后和B栈栈顶元素(temp)比较:

    1)若cur>temp,则将temp元素pop出B栈,push入A栈,继续和B栈栈顶元素进行上述的比较;

    2)若cur<=temp ,则直接将cur元素push入B栈内;

  3. 继续第2步操作直至A栈空,然后将B栈元素一一push入A栈。

  4. 至此,排序完毕,A栈元素即是排序后的结果。

#代码实现

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
package site.sixteen.stack_queue;

import java.util.Stack;

/**
* StackSortByStack
*
* @author panhainan@yeah.net(@link https://sixteen.site)
* @version 1.0
* @use 用一个辅助栈实现另一个栈的排序
* @date 2018/8/27
**/
public class StackSortByStack {

public static void stackSortByStack(Stack<Integer> dataStack) {
Stack<Integer> assistStack = new Stack<>();
Integer cur;
while (!dataStack.empty()) {
cur = dataStack.pop();
while (!assistStack.empty() && assistStack.peek() < cur) {
dataStack.push(assistStack.pop());
}
assistStack.push(cur);
}
while (!assistStack.empty()) {
dataStack.push(assistStack.pop());
}
}

public static void main(String[] args) {
Stack<Integer> data = new Stack<>();
data.push(3);
data.push(4);
data.push(2);
data.push(1);
data.push(5);
stackSortByStack(data);
while (!data.empty()) {
System.out.println(data.pop());
}
}

}

评论系统未开启,无法评论!

如果有好的建议或疑问等可以发送邮件至:panhainan@yeah.net,或者添加QQ:1016593477,将你的建议或者疑问告诉作者,作者会对你的建议进行处理并补充到文章的尾部,谢谢大家的谅解!