LeetCode problem 225: Stack implementation with queues

The topic of dry

You can implement a last in, first out (LIFO) stack with just two queues and support all four operations of a normal stack (push, top, POP, and Empty).

Implement MyStack class:

• Void push(int x) pushes element x to the top of the stack.
• Int pop() removes and returns the top element of the stack.
• Int top() returns the top element of the stack.
• Boolean empty() Returns true if the stack is empty; Otherwise, return false.

Note:

• You can only use the basic operations of queues — namely push to Back, peek/ Pop from Front, size, and is empty.
• Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

Source: LeetCode link: leetcode-cn.com/problems/im… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: Double queue

How to implement the stack using queues is outlined below:

We know that the stack is fifo, and the queue is fifO. So we set up two queues, one of which is always empty. And we always add data to an empty queue, and then add all values from the non-empty queue to the current queue according to queue rules.

So only push is special.

Let’s look at the code implementation:

/** * Initialize your data structure here. */
var MyStack = function () {
    this.queue1 = []
    this.queue2 = []
};

/**
 * Push element x onto stack. 
 * @param {number} x
 * @return {void}* /
MyStack.prototype.push = function (x) {
    if (this.queue2.length == 0) {
        this.queue2.push(x)
        for (let i = 0; i < this.queue1.length;) {
            let a = this.queue1.pop();
            console.log(a,'aaaa')
            this.queue2.unshift(a)

        }
    } else if (this.queue1.length == 0) {
        this.queue1.push(x)
        for (let i = 0; i < this.queue2.length;) {
            let a = this.queue2.pop();
            console.log(a, 'bbbb')
            this.queue1.unshift(a)
        }
    }
}

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}* /

MyStack.prototype.pop = function () {
    if (this.queue2.length == 0) {
        return this.queue1.pop()
    } else {
        return this.queue2.pop()
    }
}

/**
 * Get the top element.
 * @return {number}* /
MyStack.prototype.top = function () {
    return this.queue1.length == 0 ? this.queue2[this.queue2.length - 1] : this.queue1[this.queue1.length - 1]};/**
 * Returns whether the stack is empty.
 * @return {boolean}* /
MyStack.prototype.empty = function () {
    if (this.queue2.length == 0 && this.queue1.length == 0) {
        return true
    }
    return false
};

/** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() * /
Copy the code