【数据结构与算法】力扣 225. 用队列实现栈-分析解答

时间:2024-04-29 08:29:27

需要实现:

image.png

正常队列(先进先出):

  1. push
  2. peek / pop
  3. size
  4. is empty

image.png

var MyStack = function() {
    this.arr1 = [];
    this.arr2 = [];
};

MyStack.prototype.push = function(x) {
    this.arr2.push(x);
};

MyStack.prototype.pop = function() {
    if (this.arr2.length !== 0) {
        while (this.arr2.length > 1) {
            this.arr1.push(this.arr2.shift());
        }
        return this.arr2.shift();
    }
    while (this.arr1.length > 1) {
        this.arr2.push(this.arr1.shift());
    }
    return this.arr1.shift();
};

MyStack.prototype.top = function() {
    let topElement;
    if (this.arr2.length !== 0) {
        while (this.arr2.length > 1) {
            this.arr1.push(this.arr2.shift());
        }
        topElement = this.arr2[0];
        this.arr1.push(this.arr2.shift());
    } else {
        while (this.arr1.length > 1) {
            this.arr2.push(this.arr1.shift());
        }
        topElement = this.arr1[0];
        this.arr2.push(this.arr1.shift());
    }
    return topElement;
};

MyStack.prototype.empty = function() {
    return this.arr2.length === 0 && this.arr1.length === 0;
};


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

和之前做的用栈实现队列,基本思路差不多。都是根据不同数据结构的特性控制元素的移动。