抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

队列实现栈结构

怎么用队列实现栈结构,核心精髓就是将栈顶对应队头(前端),栈底对应队尾(后端)

可以采取单队列或双队列实现

双队列

使用两个队列模仿入栈和出栈,队列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()
*/

用户交流区