栈排序.md

栈排序

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：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