【百日算法计划】：每日一题，见证成长（021）

题目

栈排序

编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

思路

• 构造两个栈，一个用作临时栈；
• 每次新元素入栈的时候，循环与栈顶元素比较，比栈顶元素小则直接入栈，否则，将栈里元素搬移到临时栈中；直到栈为空或新元素小于栈顶元素。

public class Code03 {static class SortedStack {Stack<Integer> stack = new Stack();Stack<Integer> tmpStack = new Stack();//临时栈public SortedStack() {}public void push(int val) {//如果栈不为空且新元素比栈顶元素大 则要把栈顶元素搬移到临时栈中while (!stack.isEmpty() && stack.peek() < val){tmpStack.push(stack.pop());//加入到临时栈}stack.push(val); //新元素入栈while (!tmpStack.isEmpty()){stack.push(tmpStack.pop());//再把临时栈中元素放回stack}}public void pop() {if (!stack.isEmpty()){stack.pop();}}public int peek() {if (stack.isEmpty()) return -1;return stack.peek();}public boolean isEmpty() {return stack.isEmpty();}}}