題目
在組內(nèi)面試反饋的郵件中看到了用棧實(shí)現(xiàn)隊(duì)列這樣一道題目宠蚂，覺得自己如果面試遇到這個(gè)題目還是有點(diǎn)懵的式撼，所以特地上網(wǎng)上找了一下，在Leetcode上找到了這道題目LeetCode 232 用棧實(shí)現(xiàn)隊(duì)列求厕。
題目是這樣的：使用棧實(shí)現(xiàn)隊(duì)列的下列操作：
-
push(x)-- 將一個(gè)元素放入隊(duì)列的尾部著隆。 -
pop()-- 從隊(duì)列首部移除元素。 -
peek()-- 返回隊(duì)列首部的元素呀癣。 -
empty()-- 返回隊(duì)列是否為空美浦。
注意：只能使用標(biāo)準(zhǔn)的棧操作，也就是只有push to top项栏，peek/pop from top浦辨， size和is empty操作。
實(shí)例：
const queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
分析
之所以對這道題目有點(diǎn)懵沼沈，是因?yàn)樽约簩：完?duì)列的特點(diǎn)不太了解
- 棧是先進(jìn)后出的流酬，隊(duì)列是先進(jìn)先出的
- 標(biāo)準(zhǔn)的棧只有
push/pop/size幾個(gè)方法
因?yàn)镴avaScript中的數(shù)組實(shí)際上比隊(duì)列和棧是更加靈活的，要用棧來模擬隊(duì)列庆冕，實(shí)際上可以用數(shù)組先模擬棧康吵，然后在模擬隊(duì)列。也可以直接使用數(shù)組來模擬隊(duì)列访递，但是只使用數(shù)組的push和pop方法晦嵌。
關(guān)鍵是棧和隊(duì)列的操作順序如何實(shí)現(xiàn)，我的思路是使用了兩個(gè)棧（數(shù)組）來模擬拷姿，一個(gè)主棧一個(gè)輔棧惭载，當(dāng)移除的時(shí)候，棧移除的是棧底的元素响巢，而隊(duì)列要移除的是隊(duì)首的元素描滔，所以將主棧的元素都添加到輔棧中，然后再pop輔棧棧底的元素踪古，就是隊(duì)列要移除的隊(duì)首的元素含长。實(shí)際上和我們玩過的漢諾塔的操作過程券腔。
添加的時(shí)候可以直接添加，但是要注意輔棧中是否有元素拘泞，如果有的話需要先將輔棧的元素移動會主棧纷纫，在進(jìn)行添加。
實(shí)現(xiàn)
function MyQueue() {
// 主棧
this.queue1 = [];
// 輔棧
this.queue2 = [];
}
MyQueue.prototype.push = function (x) {
while (this.queue2.length !== 0) {
this.queue1.push(this.queue2.pop())
}
this.queue1.push(x);
};
MyQueue.prototype.pop = function () {
if (this.empty()) {
return;
}
while (this.queue1.length !== 0) {
this.queue2.push(this.queue1.pop())
}
return this.queue2.pop();
};
MyQueue.prototype.peek = function () {
if (this.empty()) {
return;
}
while (this.queue1.length !== 0) {
this.queue2.push(this.queue1.pop())
}
const temp = this.queue2.pop();
this.queue2.push(temp);
return temp;
};
MyQueue.prototype.empty = function () {
return this.queue1.length === 0 && this.queue2.length === 0
};
