LeetCode Problem 232: Implementing queues with stacks

Dry:

You can implement a first-in, first-out queue using only two stacks. Queues should support all the operations that queues normally support (push, POP, peek, empty) :

Implement MyQueue class:

• Void push(int x) pushes element X to the end of the queue
• Int pop() removes and returns the element from the beginning of the queue
• Int peek() returns the element at the beginning of the queue
• Boolean empty() Returns true if the queue is empty; Otherwise, return false

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:

Without further discussion, queues are fifo, stacks are fifO, and the element that comes in is at the top of the stack. We can use this feature to define two stacks, S1 and S2, and at each push, s2 is emptied, s1 is pushed to S1, and S1 is pushed to S2, thus the element at the bottom of the stack is pushed to the top of the queue.

Then when we pop the queue head, we remove the top of s2, which is equivalent to removing the head of s2. But at the same time we need to clear s1, because we need to keep the two stacks in sync, and then we need to push S2 to S1, so we keep S1 invariant.

Code implementation:

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

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}* /
MyQueue.prototype.push = function (x) {
    this.stack2 = []
    this.stack1.push(x);
    for (let i = this.stack1.length - 1; i >= 0; i--) {
        this.stack2.push(this.stack1[i])
    }
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}* /
MyQueue.prototype.pop = function () {
    let pop=this.stack2.pop();
    this.stack1=[]
    for (let i = this.stack2.length - 1; i >= 0; i--) {
        this.stack1.push(this.stack2[i])
    }
    console.log(this.stack1)
    return pop;
};

/**
 * Get the front element.
 * @return {number}* /
MyQueue.prototype.peek = function () {
    return this.stack2[this.stack2.length - 1]};/**
 * Returns whether the queue is empty.
 * @return {boolean}* /
MyQueue.prototype.empty = function () {
    return this.stack2.length == 0 ? true : false
};

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