題目描述
用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列.隊(duì)列的聲明如下,請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ,分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能.(若隊(duì)列中沒有元素,deleteHead 操作返回 -1 )
題目分析
- 兩個(gè)棧實(shí)現(xiàn)隊(duì)列
- 實(shí)現(xiàn)兩個(gè)隊(duì)列操作函數(shù)
參數(shù)說明
// appendTail 函數(shù)
/**
* @param {number} value
* @return {void}
*/
// deleteHead函數(shù)
/**
* @return {number}
*/
//調(diào)用方式
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/
題解及實(shí)現(xiàn)
1.倒騰法
一個(gè)棧用于 push,當(dāng)需要 delete 的時(shí)候,將這個(gè)棧所有元素放在另一個(gè)棧內(nèi),再取另一個(gè)棧的棧棧頂元素,取完后再將元素全部放回來
var CQueue = function () {
this.appendArr = []; //放元素的棧
this.deleteArr = []; //刪除元素的棧
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function (value) {
return this.appendArr.push(value) && null;
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function () {
let result;
while (this.appendArr.length) this.deleteArr.push(this.appendArr.pop()); //元素放過去
result = this.deleteArr.pop();
while (this.deleteArr.length) this.appendArr.push(this.deleteArr.pop()); //元素放回來
return result || -1;
};
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/
- 資源使用情況
- 執(zhí)行用時(shí)：516 ms, 在所有 JavaScript 提交中擊敗了 36.77%的用戶
- 內(nèi)存消耗：50.6 MB, 在所有 JavaScript 提交中擊敗了 5.06%的用戶
問題:每次調(diào)用都倒騰浪費(fèi)時(shí)間
2.懶人法
容易知道,每倒騰一次,用于刪除元素的棧的元素順序就是按照老-新(棧頂?shù)綏５?順序擺放的,只要沒取完,又沒有新的倒騰,刪除元素的時(shí)候直接取棧頂就好了,等實(shí)在取完沒得取了再將放置元素的棧的元素再倒騰過來
var CQueue = function () {
this.appendArr = [];
this.deleteArr = [];
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function (value) {
this.appendArr.push(value);
return null;
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function () {
if (!this.deleteArr.length)
while (this.appendArr.length) this.deleteArr.push(this.appendArr.pop());
return this.deleteArr.pop() || -1;
};
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/
- 資源使用情況
- 執(zhí)行用時(shí)：400 ms, 在所有 JavaScript 提交中擊敗了97.42%的用戶
- 內(nèi)存消耗：50.3 MB, 在所有 JavaScript 提交中擊敗了5.06%的用戶
