232.用栈实现队列
尽管是很简单的一题, 但还是参考了题解, 一开始还在想,push的时候还得把输出栈倒回来效率好低
结果一看题解发现不用
//思路: 对对队列尾部操作时(push,empty), 对输入栈正常操作; 对队列头部操作时(peek,pop),全部弹出到输出栈中操作
//参考思路:需要注意的是, 不需要把输出栈的东西再弹回到输入栈;
var MyQueue = function() {
this.inStack = []
this.outStack = []
this.size = 0
};
MyQueue.prototype.inToOut = function(){
while(this.inStack.length>0){
this.outStack.push(this.inStack.pop())
}
}
/**
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
this.inStack.push(x)
this.size++
};
/**
* @return {number}
*/
MyQueue.prototype.pop = function() {
if(this.outStack.length==0){
this.inToOut()
}
this.size--
return this.outStack.pop()
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
if(this.outStack.length==0){
this.inToOut()
}
return this.outStack[this.outStack.length-1]
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
return this.size==0
};
/**
* Your MyQueue object will be instantiated and called as such:
* var obj = new MyQueue()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.peek()
* var param_4 = obj.empty()
*/
225. 用队列实现栈
又看题解了...不知道怎么,总感觉自己对所谓顺序和数据的存储有点没概念了
//一个显然效率很低的思路是, push时全部压入一个队列中,pop时让前面的全压入另一个队列,pop掉最后一个
//参考思路:一个改良思路是, 入栈操作时就设法把元素放到队头; 让元素顺序和栈相符;此时甚至只需要一个队列
var MyStack = function() {
this.queue1 = []
this.queue2 = []
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue2.push(x)
while(this.queue1.length!=0){
this.queue2.push(this.queue1.shift())
}
let tmp = this.queue1
this.queue1 = this.queue2
this.queue2 = tmp
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.queue1.shift()
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue1[0]
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return this.queue1.length==0
};
/**
* Your MyStack object will be instantiated and called as such:
* var obj = new MyStack()
* obj.push(x)
* var param_2 = obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.empty()
*/