My Javascript solution, O(1) for all operations


  • 0
    M

    I was surprised to see all the O(n) solutions. This one seems to work, and it's all O(1). This solution uses nested queues, all of length 2. When a new element is pushed onto the stack, a new two-element queue is created.

    Is anything wrong with this solution?

    /**
     * @constructor
     */
    var Stack = function() {
        this.queue = new Queue();
    };
    
    /**
     * @param {number} x
     * @returns {void}
     */
    Stack.prototype.push = function(x) {
        var nextQueue = new Queue();
        nextQueue.enqueue(x);
        nextQueue.enqueue(this.queue);
        this.queue = nextQueue;
    };
    
    /**
     * @returns {void}
     */
    Stack.prototype.pop = function() {
        var x = this.queue.dequeue();
        this.queue = this.queue.dequeue();
        return x;
    };
    
    /**
     * @returns {number}
     */
    Stack.prototype.top = function() {
        return this.queue.top();
    };
    
    /**
     * @returns {boolean}
     */
    Stack.prototype.empty = function() {
        return this.queue.length() === 0;
    };
    
    
    // Wrapper class for Queue. Uses simple list operations
    var Queue = function() {
        this.lst = [];
    }
    
    Queue.prototype.enqueue = function(x) {
        this.lst.push(x);
    }
    
    Queue.prototype.dequeue = function() {
        return this.lst.shift();
    }
    
    Queue.prototype.length = function() {
        return this.lst.length;
    }
    
    Queue.prototype.top = function() {
        return this.lst[0];
    }

  • 0
    I

    I don't understand.

    shift() function return the first element of the array, and then delete it from the array.

    When you implement the pop() function, do the dequeue() twice. I suppose that two element are deleted and this.queue should be the second deleted element?


  • 0
    M

    Yes, exactly. The stack is just a bunch of nested queues, each of length 2.


  • 0
    T

    pushing 1,2,3,4,5 into this stack will produce: [5, [4, [3, [2, [1, [] ] ] ] ] ]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.