225. 232. 队列、堆栈相互模拟实现

首先我们看看两者的特性，队列是「先进先出」，堆栈是「先进后出」，如果使用其中一个数据结构来实现另一个数据结构的效果，可以采取两个该数据结构来实现。如：使用两个「堆栈」来模拟「队列」效果。

用队列模拟实现堆栈效果
实现如下功能：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

思路：申明两个「队列」queue1和queue2。一开始如果都为空就把数据push到queue1中，然后如果要查看「堆栈」。然后如果pop()就把两个队列中，不为空的那个「队列」依次弹出元素丢到另一个为空的「队列」中，直到长度为1, 这剩下的一个就是pop()所要的结果。

代码如下：

/**
 * 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.queue1.length === 0 && this.queue2.length === 0) {
        //  最开始如果都没有数据，就直接放在queue1中
        this.queue1.push(x);
    } else {
        //  之后有了数据还要push，就把数据丢到那个长度不为0的「队列」中
        if(this.queue1.length === 0) {
            this.queue2.push(x);
        } else {
            this.queue1.push(x);
        }
    }
};

/**
 * Removes the element on top of the stack and returns that element.
 * @return {number}
 */
MyStack.prototype.pop = function() {
    if(this.queue1.length === 0) {
        while(this.queue2.length !== 1) {
            this.queue1.push(this.queue2.shift());
        }
        return this.queue2.shift();
    } else {
        while(this.queue1.length !== 1) {
            this.queue2.push(this.queue1.shift());
        }
        return this.queue1.shift();
    }
};

/**
 * Get the top element.
 * @return {number}
 */
MyStack.prototype.top = function() {
    if(this.queue1.length === 0) {
        return this.queue2[this.queue2.length - 1]
    } else {
        return this.queue1[this.queue1.length - 1]
    }
};

/**
 * Returns whether the stack is empty.
 * @return {boolean}
 */
MyStack.prototype.empty = function() {
    if(this.queue1.length === 0 && this.queue2.length === 0) {
        return true;
    }
    return false;
};

/** 
 * Your MyStack object will be instantiated and called as such:
 * var obj = Object.create(MyStack).createNew()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

用「堆栈」模拟实现「队列」

实现如下功能：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

思路：申明两个「堆栈」stack1和stack2，然后此处就直接定一个「输入栈」（stack1）和一个「输出栈」（stack2）。push操作都把元素丢入stack1，然后在pop操作的时候，把stack1中的元素依次弹出到stack2，然后把stack2最上面的元素pop出，就是pop操作的结果，然后还要把剩下的元素，依次弹出到stack1中。（注意：在用「队列」模拟实现「堆栈」的pop操作中，在得到pop的结果后无后续操作，使得两个「队列」可以相互调用，即无规定哪个「队列」来作「输入队列」或者「输出队列」，在此处会规定）

/**
 * 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) {
    //  规定stack1「堆栈」为「输入栈」
    this.stack1.push(x);
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    let temp;
    while(this.stack1.length !== 0) {
        //  把「输入栈」中的元素全部弹出到stack2「输出栈」中，然后pop弹出stack2中的元素即
        //  为所要的结果
        this.stack2.push(this.stack1.pop());
    }

    //  将结果用temp变量先记录下来
    temp = this.stack2.pop();

    //  后续操作：将「输出栈」中剩余的所有元素弹出到「输入栈」中
    while(this.stack2.length !== 0) {
        this.stack1.push(this.stack2.pop());
    }

     return temp;

};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    return this.stack1[0];
};

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

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = Object.create(MyQueue).createNew()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */