【百日算法计划】:每日一题,见证成长(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();}}}