来源：LeetCode
难度：简单
描述：
栈排序。编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
示例1：
输入：
[“SortedStack”, “push”, “push”, “peek”, “pop”, “peek”]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]
示例2：
输入：
[“SortedStack”, “pop”, “pop”, “push”, “pop”, “isEmpty”]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]
分析：
所谓的栈排序，其实就是栈顶元素到栈底元素之间依次增加，因此咱们需要注意的是入栈的过程。
由于咱们的目的是始终维持栈元素从小到大的顺序；所以在每次push时，需要寻找第一个大于等于val的位置，再进行push操作
由于题目要求只能用栈这一种数据结构，因此咱们在寻找第一个大于等于val的位置时，利用一个临时栈存储原栈出栈的元素即可
解题
方法一：栈辅助法
思路：
在push操作时，如果栈空或者栈顶元素大于等于待入栈的元素val，那么直接将val入栈即可
如果栈顶元素小于val，那么将原栈中所有小于val的元素依次出栈并存放到辅助栈中，直到找到第一个大于等于val的元素，此时将val入栈，之后再将辅助栈中的元素依次倒回原栈中
代码：
1private Stack<Integer> sortStack = new Stack<>();
2
3public void push(int val) {
4 if (sortStack.isEmpty() || sortStack.peek() > val) {
5 //栈空或者栈顶元素大于val，直接入栈即可
6 sortStack.push(val);
7 } else {
8 //采用一个临时栈
9 Stack<Integer> tempStack = new Stack<>();
10 //将排序栈中小于val的元素依次放入临时栈中
11 while (!sortStack.isEmpty() && sortStack.peek() < val) {
12 tempStack.push(sortStack.pop());
13 }
14 //当所有小于val的元素都出栈后，将val入栈
15 sortStack.push(val);
16 //将临时栈中的元素重新入栈
17 while (!tempStack.isEmpty()) {
18 sortStack.push(tempStack.pop());
19 }
20 }
21}
22
23public void pop() {
24 if (!sortStack.isEmpty()) {
25 sortStack.pop();
26 }
27}
28
29public int peek() {
30 return sortStack.isEmpty() ? -1 : sortStack.peek();
31}
32
33public boolean isEmpty() {
34 return sortStack.isEmpty();
35}以上仅是个人思路解法
转载请注明：XAMPP中文组官网 » 经典面试题37_栈排序解法思路