经典面试题(三十七)-- 栈排序

发布于 2021-09-07 10:44 ，所属分类：2021面试经验技巧分享

来源：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入栈，之后再将辅助栈中的元素依次倒回原栈中


代码：

 1privateStack<Integer>sortStack=newStack<>();
 2
 3publicvoidpush(intval){
 4if(sortStack.isEmpty()||sortStack.peek()>val){
 5//栈空或者栈顶元素大于val，直接入栈即可
 6sortStack.push(val);
 7}else{
 8//采用一个临时栈
 9Stack<Integer>tempStack=newStack<>();
10//将排序栈中小于val的元素依次放入临时栈中
11while(!sortStack.isEmpty()&&sortStack.peek()<val){
12tempStack.push(sortStack.pop());
13}
14//当所有小于val的元素都出栈后，将val入栈
15sortStack.push(val);
16//将临时栈中的元素重新入栈
17while(!tempStack.isEmpty()){
18sortStack.push(tempStack.pop());
19}
20}
21}
22
23publicvoidpop(){
24if(!sortStack.isEmpty()){
25sortStack.pop();
26}
27}
28
29publicintpeek(){
30returnsortStack.isEmpty()?-1:sortStack.peek();
31}
32
33publicbooleanisEmpty(){
34returnsortStack.isEmpty();
35}



以上仅是个人思路解法，觉得还不错欢迎点赞分享


往期精彩推荐

  • 二叉树(十五)-- 二叉树剪枝

  • 经典面试题(十六)--二叉树的镜像

  • 经典面试题(十一)--只出现一次的数字


点击下方链接，gongzhong号，更多精彩等你发现


相关资源