栈排序

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