225. Implement Stack using Queues

題目

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty.

Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

翻譯

使用queue來實做 stack。

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

注意:
你只能用標準的queue方法操作,這表示只有push到queue後端,peek/pop queueu前端的元素,size以及sEmpty這些方法是可以用的。

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

思路

LeetCode 232. Implement Queue using Stacks幾乎一樣,直接看code就可以。

解題

/**
 * 使用一個自製的簡易queue來實作stack
 * @constructor
 */
var Stack = function() {
    this.queue = new Queue();
};


/**
 * queue跟stack都是把x加到最後面
 * @param {number} x
 * @returns {void}
 */
Stack.prototype.push = function(x) {
    this.queue.push(x);
};

/**
 * @returns {void}
 */
Stack.prototype.top = function() {
     var element;
     var keep  = new Queue();
     while(!this.queue.isEmpty()){
        element = this.queue.pop();
        keep.push(element);
     }

     while(!keep.isEmpty()){
        this.queue.push(keep.pop());
     }
    return element;
};

/**
 * @returns {number}
 */
Stack.prototype.pop = function() {
     var element;
     var keep  = new Queue();
     while(!this.queue.isEmpty()){
        element = this.queue.pop();
        if(!this.queue.isEmpty()){
            keep.push(element);
        }
     }

     while(!keep.isEmpty()){
        this.queue.push(keep.pop());
     }
    return element;
};

/**
 * 跟判斷queue是否為空一樣
 * @returns {boolean}
 */
Stack.prototype.empty = function() {
    return this.queue.isEmpty();
};


/**
 * 用array實做一個簡單的Queue
 */
var Queue = function(){
    this.list = [];
}

/**
 *  push跟array的push一樣,加到最後
 */
Queue.prototype.push = function(x){
    this.list.push(x);
}

/**
 *  peek回傳第一筆資料但是不刪除
 */
Queue.prototype.peek = function(){
    return this.list[0];
}
/**
 *  pop拿出第一筆資料
 */
Queue.prototype.pop = function(){
    return this.list.shift();
}
/**
 *  判斷list裡面是不是沒東西 
 */
Queue.prototype.isEmpty = function(){
    return this.list.length == 0;
}

results matching ""

    No results matching ""