队列实现栈结构
怎么用队列实现栈结构,核心精髓就是将栈顶对应队头(前端),栈底对应队尾(后端)
可以采取单队列或双队列实现
双队列
使用两个队列模仿入栈和出栈,队列2用于辅助
- 入栈操作时,首先将元素入队到队2
- 然后将队1的全部元素依次出队,并入队到队2
- 此时,队列2的前端元素即为新入栈的元素,再将队1,队2交换
- 队1的元素为栈内元素,其前端和后端分别对应栈顶和栈底
var MyStack = function() {
this.queue1 = []
this.queue2 = []
this.topValue = null
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
this.queue2.push(x)
this.topValue = x
while(this.queue1.length) {
this.queue2.push(this.queue1.shift())
}
let temp = this.queue1
this.queue1 = this.queue2
this.queue2 = temp
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
let n = this.queue1.shift()
if(this.queue1.length) {
this.topValue = this.queue1[0]
} else {
this.topValue = undefined
}
return n
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
return this.topValue
};
/**
* @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()
*/
单队列
- 入栈操作时,首先获得入栈前的元素个数 n
- 然后将元素入队到队列
- 再将队列中的前 n 个元素(即除了新入栈的元素之外的全部元素)依次出队并入队到队列
- 此时队列的前端的元素即为新入栈的元素,且队列的前端和后端分别对应栈顶和栈底。
var MyStack = function() {
this.queue = []
};
/**
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
let n = this.queue.length
this.queue.push(x)
for(let i = 0;i < n;i++) {
this.queue.push(this.queue.shift())
}
};
/**
* @return {number}
*/
MyStack.prototype.pop = function() {
return this.queue.shift()
};
/**
* @return {number}
*/
MyStack.prototype.top = function() {
return this.queue[0]
};
/**
* @return {boolean}
*/
MyStack.prototype.empty = function() {
return this.queue.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()
*/