搜云库技术团队
栈排序
栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek和isEmpty。当栈为空时，peek返回-1。
示例
输入：
["SortedStack", "push", "push", "peek", "pop", "peek"]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]
输入：
["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]
题解
var SortedStack = function() {
this.stack = [];
this.auxStack = [];
};
/**
* @param {number} val
* @return {void}
*/
SortedStack.prototype.push = function(val) {
if(this.stack.length){
while(true){
var topValue = this.stack.pop();
if(topValue > val || topValue === undefined){
if(topValue !== undefined) this.stack.push(topValue);
this.stack.push(val);
while(this.auxStack.length) this.stack.push(this.auxStack.pop());
break;
}else{
this.auxStack.push(topValue);
}
}
}else{
this.stack.push(val);
}
};
/**
* @return {void}
*/
SortedStack.prototype.pop = function() {
return this.stack.pop();
};
/**
* @return {number}
*/
SortedStack.prototype.peek = function() {
if (this.stack.length === 0) return -1;
return this.stack[this.stack.length - 1];
};
/**
* @return {boolean}
*/
SortedStack.prototype.isEmpty = function() {
return this.stack.length === 0;
};
/**
* Your SortedStack object will be instantiated and called as such:
* var obj = new SortedStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.isEmpty()
*/
思路
本题有一些限制条件，必须使用栈结构进行排序，且最多只能使用一个其他的临时栈存放数据，在调用方式上是使用new实例化构造函数，那么在SortedStack构造函数上拓展原型以供调用，首先在构造函数中定义两个栈数组，分别为排序的主栈以及辅助栈，这两个栈数组只调用其相关的栈操作方法。在入栈的push操作时就对值进行排序，如果栈中没有值，那么就直接入栈，如果存在值则首先出栈栈顶值，判断该值与入栈的值的大小，如果栈顶的值大于入栈的值或者主栈中已经出栈完毕，那么首先判断出栈的值是否有效，有效则就将出栈的值首先入栈，然后将入栈的值进栈，然后将辅助栈中的值依次出栈并压入主栈，直到辅助栈空，然后结束循环，如果栈顶的值小于出栈的值且主栈并未出栈完毕，那么将该出栈的值压入辅助栈。由于主栈在入栈时就已经有序，那么出栈的pop操作直接调用pop()方法即可。对于peek操作则首先判断栈长度，如果长度为0则返回-1，否则返回栈顶元素的值。对于isEmpty操作则直接判断主栈长度是否为0即可。
每日一题
https://github.com/WindrunnerMax/EveryDay
题源
https://leetcode-cn.com/problems/sort-of-stacks-lcci
