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;
}