LeetCode 232. Implement Queue using Stacks

題目

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. 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).

翻譯

使用stacks來實做queue。

• push(x) -- 將一個元素x放入queue最後
• pop() -- 移除queue最前面的元素
• peek() -- 取得queue最前面的元素(不刪除)
• empty() -- 檢查queue是否是空的

注意：
你只能用標準的stack方法操作，這表示只有push到stack頂端， peek/pop stack頂端的元素， size， isEmpty這些方法是可以用的。

有些語言可能沒有支援stack，你可以使用類似的結構，例如list或deque, 只要你的操作符合上述的標準stack方法。可以假設全部的操作都是合法的(例如說當queue是empty的時候，不會執行pop這樣的操作)。

思路

用javascrip來做這題其實頗簡單的，array本身的特定就跟stack差不多

1. push --> list.push(x)的特性跟queue一樣，都是把x加到最後面
2. empty --> 判斷queue是否empty跟判斷stack一樣，都是判斷裡面的array.length是不是0，不過題目限定只能用標準的stack方法，因此我們只能用stack.size() == 0來判斷。
3. pop --> 這比較麻煩，因為只能用stack.pop()來實做，這邊用一個keep stack來保存stack裡面拿出來的東西，在拿出stack最後一筆資料時再倒回去。
4. peek --> 跟pop類似，直接看下面程式碼差異的部分就可以

解題

/**
 * @constructor
 */
var Queue = function() {
    this.stack = [];
};


// 自己在 array裡面加上stack的size方法
Array.prototype.size = function () {
  return this.length;
};


/**
 * @param {number} x
 * @returns {void}
 */
Queue.prototype.push = function(x) {
    this.stack.push(x);
};

/**
 * queue的pop()是拿出最底下一筆，stack的pop()是拿出最上面一筆
 * 因此stack不斷的pop()值到最後一筆才是我們要的資料
 * 使用另外一個stack來保存之前拿出的資料，取出之後將keep裡面的資料倒回我們的queue
 * @returns {void}
 */
Queue.prototype.pop = function() {

    var keep = [];     // 儲存從stack拿出來的資料
    var element ;      // 要回傳的資料

    // 從stack裡面不斷的倒資料到keep，直到最後一筆
    while(this.stack.size() > 1){
        keep.push(this.stack.pop());
    }

    // 最後一筆是我們要回傳的資料，而且他不會回到stack中了
    var element = this.stack.pop();

    // 把keep的資料倒回stack
    while(keep.size() > 0){
        this.stack.push(keep.pop());
    }

    return element;
};

/**
 * @returns {number}
 */
Queue.prototype.peek = function() {
    var keep = [];
    var element ;

    while(this.stack.size() > 1){
        keep.push(this.stack.pop());
    }

    var element = this.stack.pop();

    // 跟pop不同的是，最後一筆要回到stack中
    keep.push(element);

    while(keep.size() > 0){
        this.stack.push(keep.pop());
    }
    return element;
}

/**
 * @returns {boolean}
 */
Queue.prototype.empty = function() {
    return this.stack.size() == 0;
};