Loading... # [面试题 03.05. 栈排序](https://leetcode.cn/problems/sort-of-stacks-lcci/) ## 题目 栈排序。 编写程序,对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据,但不得将元素复制到别的数据结构(如数组)中。该栈支持如下操作:`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] ``` **说明:** 1. 栈中的元素数目在[0, 5000]范围内。 ## 题解 解题思路,将数据栈命名为 dataStack, 辅助栈命名为 helperStack. 1. push: 永远 push 到 dataStack 中. 2. pop: sort() 后, 如果 helperStack 不为空则 pop(); 3. peek: sort() 后, 如果 helperStack 不为空则 peek(), 为空返回 -1; 4. isEmpty: 判断 dataStack 和 helperStack 是否都不为空. 5. sort: 排序操作,将 dataStack 排序后压入到 helperStack 5.1 取 dataStack 中栈顶元素即为 dataTopItem 5.2 如果 dataTopItem 小于等于 helperStack 栈顶元素,则将 dataTopItem 压入到 helperStack 栈顶. 5.3 如果 dataTopItem 大于 helperStack 栈顶元素,则依次将 helperStack 栈顶元素压回 dataStack, 然后比较 helperStack 新的栈顶元素和 dataTopItem 的大小,参考 5.2 的逻辑。 直到最后 dataStack 中的元素全部压入到 helperStack 中. ```java import java.util.Stack; //leetcode submit region begin(Prohibit modification and deletion) class SortedStack { private Stack<Integer> dataStack; private Stack<Integer> helperStack; public SortedStack() { dataStack = new Stack<>(); helperStack = new Stack<>(); } public void push(int val) { dataStack.push(val); } public void pop() { sort(); if (!helperStack.isEmpty()) { helperStack.pop(); } } public int peek() { sort(); if (helperStack.isEmpty()) { return -1; } else { return helperStack.peek(); } } public boolean isEmpty() { return dataStack.isEmpty() && helperStack.isEmpty(); } private void sort() { if (dataStack.isEmpty()) { return; } while (!dataStack.isEmpty()) { // 取数据栈栈顶元素 Integer dataTopItem = dataStack.pop(); // 判断只要辅助栈有元素小于数据栈栈顶元素,则取出并压回数据栈. while (!helperStack.isEmpty() && helperStack.peek() < dataTopItem) { dataStack.push(helperStack.pop()); } // 确保辅助栈没有比数据栈顶元素小的元素,则压入到辅助栈 helperStack.push(dataTopItem); } } } ``` 最后修改:2022 年 09 月 26 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请我喝杯咖啡吧。