隊列實作棧，棧實作隊列，你學廢了嗎？

隊列與棧

相關概念

• 隊列是先進先出，棧是先進後出。
• 以棧為例，如圖所示。

例題1：用棧實作隊列

題目連結：[232.用棧實作隊列](​​232. 用棧實作隊列 - 力扣（LeetCode） (leetcode-cn.com)​​)

分析：

• 需要使用兩個棧實作，一個為輸入棧，一個為彈出棧。
• 由于隊列的輸出順序剛好是和棧相反的，是以當輸出棧為空時，就講輸入棧裡面彈出，放入輸出棧，這個時候輸出棧的輸出順序就和隊列的輸出順序一緻。

MyQueue.prototype.pop = function() {
    if(this.stackOut.length === 0) {
        while(this.stackIn.length > 0){
            this.stackOut.push(this.stackIn.pop());
        }
    }
    return this.stackOut.pop();
};      

• 當需要擷取最上面的元素（隊列首部元素）時，其實也就是輸出棧輸出的第一個元素，可将其輸出擷取到值以後再将其壓入棧。

MyQueue.prototype.peek = function() {
    const x = this.pop();
    this.stackOut.push(x);
    return x;
};      

解答

var MyQueue = function() {
    this.stackIn = [];
    this.stackOut = [];
};

MyQueue.prototype.push = function(x) {
    this.stackIn.push(x);
};

MyQueue.prototype.pop = function() {
    if(this.stackOut.length === 0) {
        while(this.stackIn.length > 0){
            this.stackOut.push(this.stackIn.pop());
        }
    }
    return this.stackOut.pop();
};

MyQueue.prototype.peek = function() {
    const x = this.pop();
    this.stackOut.push(x);
    return x;
};

MyQueue.prototype.empty = function() {
    return !this.stackIn.length && !this.stackOut.length;
};      

例題2：用隊列實作棧

題目連結：[225.用隊列實作棧](​​225. 用隊列實作棧 - 力扣（LeetCode） (leetcode-cn.com)​​)

分析：

• 不同于用棧實作隊列，這裡可以不需要兩個隊列實作棧，隻需要一個隊列即可。
• 一個隊列實作方法(針對于pop()方法的實作)

• 隻需要将隊列的前length - 1個元素移到隊列後面即可。
• 直接shift()取出的第一個元素就是我們要的結果。

MyStack.prototype.pop = function() {
    let k = this.queue.length - 1;
    while(k-- > 0){
        this.queue.push(this.queue.shift());
    }
    return this.queue.shift();
};      

• 兩個隊列實作方法(針對于pop()方法的實作)

• 使用一個輔助隊列，當輔助隊列裡的元素為空時我們将另外一個隊列與輔助隊列交換。
• 将輔助隊列的元素出隊放到另外一個隊列中，剩下一個元素即可，這裡可以采用while循環，控制隊列長度為1。
• 最後直接将輔助隊列剩下的元素取出即可，shift()。

MyStack.prototype.pop = function() {
    if(!this.queue1.length){
        [this.queue1, this.queue2] = [this.queue2, this.queue1];
    }
    while(this.queue1.length > 1){
        this.queue2.push(this.queue1.shift());
    }
    return this.queue1.shift();
};      

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

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

MyStack.prototype.pop = function() {
    let k = this.queue.length - 1;
    while(k-- > 0){
        this.queue.push(this.queue.shift());
    }
    return this.queue.shift();
};

MyStack.prototype.top = function() {
    const x = this.pop();
    this.queue.push(x);
    return x;
};

MyStack.prototype.empty = function() {
    return !this.queue.length;
};      

var MyStack = function() {
    this.queue1 = []; // 輔助隊列1
    this.queue2 = [];
};

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

MyStack.prototype.pop = function() {
    if(!this.queue1.length){
        [this.queue1, this.queue2] = [this.queue2, this.queue1];
    }
    while(this.queue1.length > 1){
        this.queue2.push(this.queue1.shift());
    }
    return this.queue1.shift();
};

MyStack.prototype.top = function() {
    const x = this.pop();
    this.queue2.push(x);
    return x;
};

MyStack.prototype.empty = function() {
    return !this.queue2.length;
};