LeetCodeの問題:232.スタックを使って列を実現し、二つのスタックを使って入隊します.O(1)、出隊-O(n)、JavaScript、詳細な注釈
ソースリンク:https://leetcode-cn.com/problems/implement-queue-using-stacks/
問題解決の考え方:すべての要素はs 1が存在します.同時に最初の入隊要素をキャッシュします. 隊を出る時、まずチームの先頭以外の要素をs 2にキャッシュして、s 1の残りの要素をpopします. popが完了したら、s 2キャッシュの要素を順次s 1に戻す.
問題解決の考え方:
/**
* Initialize your data structure here.
*/
var MyQueue = function () {
this.s1 = []; //
this.s2 = []; // pop
this.top = null; //
};
/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
//
if (!this.s1.length) {
this.top = x;
}
//
this.s1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
// s1 1 , , ,
if (this.s1.length <= 1) {
this.top = null;
}
// s1 s2
while (this.s1.length > 1) {
this.top = this.s1.pop();
this.s2.push(this.top);
}
//
const pop = this.s1.pop();
// s2 s1,
while (this.s2.length) {
this.s1.push(this.s2.pop());
}
return pop;
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function () {
return this.top;
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
return !this.s1.length;
};