理论知识点：
队列：先进先出
栈：后进先出
image.png
用栈实现队列
力扣题目
思路：
需要两个栈
关键：pop的实现
代码：
var MyQueue = function() {
this.stackIn = [];//输入栈：主要负责push
this.stackOut = [];//输出栈：主要负责pop
};
/**
* @param {number} x
* @return {void}
*/
// 往输入栈做push
MyQueue.prototype.push = function(x) {
this.stackIn.push(x)
};
/**
* @return {number}
*/
// 在输出栈做pop，pop时如果输出栈数据为空，需要将输入栈全部数据导入；如果非空，则可直接使用
MyQueue.prototype.pop = function() {
if(this.stackOut.length){
return this.stackOut.pop()
}
while(this.stackIn.length){
this.stackOut.push(this.stackIn.pop())
}
return this.stackOut.pop()
};
/**
* @return {number}
*/
MyQueue.prototype.peek = function() {
let res = this.pop()
this.stackOut.push(res)
return res
};
/**
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
if(!this.stackOut.length && !this.stackIn.length){
return true
}
return false
};
/**
* 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()
*/
用队列实现栈
力扣题目
自己的想法：想到了要交换一下队列的元素。队列1 的元素如何控制只有一个的时候不交换。。结果是用queue的长度！
本题关键点：pop的实现,empty的写法：两个queue判空
//js用list数组模拟队列操作
var MyStack = function() {
this.queue1 = [];
this.queue2 = [];
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue1.push(x)
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
//当queue1为空时，交换两个队列
if(!this.queue1.length){
[this.queue1,this.queue2] = [this.queue2,this.queue1]
}
//将queue1除最后一个元素外，放入queue2
while(this.queue1.length>1){
this.queue2.push(this.queue1.shift())
}
return this.queue1.shift()
};
/**
* @return {number}
*/
//注意善用写好的函数
MyStack.prototype.top = function() {
const item = this.pop()
this.queue1.push(item)
return item
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return !this.queue1.length && !this.queue2.length
};
/**
* 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()
*/
进阶：如何用一个队列实现栈？
思路：pop的时候，将除首部元素放入尾部
//js用list数组模拟队列操作
var MyStack = function() {
this.queue = [];
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue.push(x)
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
let n= this.queue.length
n--
while(n--){
this.queue.push(this.queue.shift())
}
return this.queue.shift()
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
const item = this.pop()
this.queue.push(item)
return item
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return !this.queue.length
};
/**
* 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()
*/
