The stack for the team

LeetCode portal03.04. Implement Queue using Stacks LCCI

The title

Implement a MyQueue class that uses two stacks to implement a queue.

Implement a MyQueue class which implements a queue using two stacks.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // return 1
queue.pop();   // return 1
queue.empty(); // return false

Copy the code

Notes:

  • You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Thinking line

Their thinking

The key to this problem is how to use stacks to simulate queues. We know that stacks are FILO(FIFO) and queues are FIFO(FIFO), so if we let all the elements in stack A pop into another stack B, then stack B is A queue relative to stack A.

Let’s go through the code with this idea.

I decided to use a variable temp to hold the value of the push in MyQueue, and we’ll use the stack this.queue for the queue operations. If this queue has a value, pop it out and use temp to receive it. Temp is then used to receive the element to be pushed. Finally, perform the reverse of the above operation, pop all elements in temp and receive them with this.queue. Then we complete the transition from stack to queue.

/** * Initialize your data structure here. */
var MyQueue = function () {
    this. queue = []
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}* /
MyQueue.prototype.push = function (x) {
    const temp = []
    while(this.queue.length) {
        temp.push(this.queue.pop())
    };
    temp.push(x)
    while(temp.length) {
        this.queue.push(temp.pop())
    }
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function () {
    return this.queue.pop();
};

/**
 * Get the front element.
 * @return {number}* /
MyQueue.prototype.peek = function () {
    return this.queue[this.queue.length -1];
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}* /
MyQueue.prototype.empty = function () {
    return this.queue.length === 0
};

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

Let’s use the ES6 Class syntax again.

class MyQueue {
    constructor() {
        this.queue = [];
    }
    peek() {
        return this.queue[this.queue.length - 1];
    }
    empty() {
        return this.queue.length === 0
    }
    pop() {
        return this.queue.pop();
    }
    push(item) {
        const temp = []
        while (this.queue.length) {
            temp.push(this.queue.pop())
        };
        temp.push(item)
        while (temp.length) {
            this.queue.push(temp.pop())
        }
    }
}
Copy the code

This is my solution to this question. If you have any questions or better solutions, please leave a comment and interact.