使用栈方法模拟队列
一种是用栈顶当队列的头,这样pop是O(1),push是O(n),这种比较好想。
/**
* (Two Stacks) Push - O(n)O(n) per operation, Pop - O(1)O(1) per operation.
*/
/**
* @constructor
*/
var Queue = function() {
this.data = [];
};
/**
* @param {number} x
* @returns {void}
*/
Queue.prototype.push = function(x) {
var temp = [];
while (this.data.length!==0) {
temp.push(this.data.pop());
}
this.data.push(x)
while (temp.length!==0) {
this.data.push(temp.pop());
}
};
/**
* @returns {void}
*/
Queue.prototype.pop = function() {
this.data.pop();
};
/**
* @returns {number}
*/
Queue.prototype.peek = function() {
return this.data[this.data.length-1];
};
/**
* @returns {boolean}
*/
Queue.prototype.empty = function() {
if (this.data.length===0)
return true;
else
return false;
};
还有一种是使用栈底当队列头,这样push是O(1),pop最好情况是O(1),最坏情况是O(n)
所以push的时候就相当于栈的push。
pop稍微有点复杂:
当第一次pop的时候,我们需要将栈1里的所有元素pop出来push到栈2中,pop出栈2的第一个。
以后pop的时候就直接取栈2的顶就好。此时如果有新的元素push进来还会push到栈1里,由于他们是后进的元素,不影响我们pop时取栈2的顶。栈2空了以后,我们就需要再把栈1里的元素倒到栈2里,再取栈2的顶。
peek:
这个我们设了一个标志位front,当栈1是空的的时候push进去的第一个元素我们把它赋给front,但当栈2非空时,它并不是真的队首,所以栈2空时返回front,非空时返回栈2顶。
/**
* (Two Stacks) Push - O(1)O(1) per operation, Pop - Amortized O(1)O(1) per operation.
*/
/**
* @constructor
*/
var Queue = function() {
this.stack1 = [];
this.stack2 = [];
this.front;
};
/**
* @param {number} x
* @returns {void}
*/
Queue.prototype.push = function(x) {
if (this.stack1.length===0)
this.front = x;
this.stack1.push(x);
};
/**
* @returns {void}
*/
Queue.prototype.pop = function() {
if (this.stack2.length!==0) {
return this.stack2.pop();
}
while (this.stack1.length!==0) {
this.stack2.push(this.stack1.pop());
}
return this.stack2.pop();
};
/**
* @returns {number}
*/
Queue.prototype.peek = function() {
if (this.stack2.length!==0)
return this.stack2[this.stack2.length-1];
return this.front;
};
/**
* @returns {boolean}
*/
Queue.prototype.empty = function() {
if ((this.stack1.length+this.stack2.length)===0)
return true;
else
return false;
};