-
Notifications
You must be signed in to change notification settings - Fork 86
Open
Description
原题链接:https://leetcode-cn.com/problems/implement-queue-using-stacks/
解题思路:
参考了官方题解中的方法二(使用两个栈 入队 - O(1)O(1),出队 - 摊还复杂度 O(1)O(1))。
- 使用两个栈,s1中存储的是后入队的元素,s2中存储的是先入队的元素
- 入队时,元素默认存储在s1。
- 出队时,默认从s2进行出栈操作,如果s2为空,则将s1中元素转移到s2。
- 如果s2有值,则队首在s2的栈顶。否则,队首在top。
- 由于s1的元素只有在pop时才会转移到s2,因此只有两个栈都为空时,队列才为空。
/**
* Initialize your data structure here.
*/
var MyQueue = function () {
this.s1 = []; // s1中存储的是后入队的元素
this.s2 = []; // s2中存储的是先入队的元素
this.top = null; // 储存队首,如果s2中有元素,则s2的栈顶为队首
};
/**
* 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;
}
// 后入队的元素都保存在s1
this.s1.push(x);
};
/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
// s2中保存的是先入队的元素,因此要先出队
if (this.s2.length) {
return this.s2.pop();
}
// 如果s2为空,将s1中元素存入s2,进行出队操作
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
// 因为将s1元素存入s2,所以队首始终在在s2的栈顶
return this.s2.pop();
};
/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function () {
// 如果s2中有元素,则栈顶即为队首
if (this.s2.length) {
return this.s2[this.s2.length - 1];
}
// s2中无元素,则此时队首在top
return this.top;
};
/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
// 由于s1的元素只有在pop时才会转移到s2,因此判空时要两个栈一起判断
return !this.s1.length && !this.s2.length;
};
Metadata
Metadata
Assignees
Labels
No labels