Stack Sorting#

Stack sorting. Write a program that sorts a stack so that the smallest element is at the top of the stack. You can only use one other temporary stack at most to store data, but you can't copy elements to other data structures (such as arrays). This stack supports the following operations: push, pop, peek, and isEmpty. When the stack is empty, the peek returns -1.

Example#

Solution#

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()
 */

Idea#

There are some constraints in this problem. We must sort the stack using a stack and at most only one temporary stack and also, we need to use the new keyword to instantiate the constructor function. So, on the constructor SortedStack function, we expand the prototype for call and define two stack arrays, one for the main stack of sorted elements and the other for the auxiliary stack. We only call their respective stack operation methods. In the push operation when pushing into the main stack, we sort the value. If there are no values in the stack, push the value directly. If there are values, first pop the top value from the stack, then compare it with the value being pushed. If the top value of the stack is greater than the incoming value, or the main stack is empty after popping, first check if the popped value is valid. If valid, push the popped value first, then push the value being pushed. Then pop the values from the auxiliary stack and push them into the main stack until the auxiliary stack is empty. If the top value is less than the value being popped and the main stack is not empty after popping, push the popped value into the auxiliary stack. As the main stack is already sorted when pushing, the pop operation just calls the pop() method directly. For the peek operation, first check the stack length. If the length is 0, return -1, otherwise, return the value of the top element of the stack. For the isEmpty operation, just check if the length of the main stack is 0.

Daily Question#

Question Source#