队列及算法题

队列结构，先进先出

• 用数组实现-顺序队列

  function ArrayQueue(len){
    this.items = new Array(len)
    this.n = len
    this.head = 0
    this.tail = 0
  }
  ArrayQueue.prototype.enqueue = function(item){
    if(this.tail === this.n){// tail后没有空余空间
      if(head === 0) return false// 判断是否队列前方有已经出队的位置
      // 有则将整个队列向前移动
      for(let i = head;i<this.tail;i++){
        this.items[i-head] = this.items[i]
      }
      this.tail = this.tail-this.head
      this.head = 0
    }
    this.items[this.tail] = item
    this.tail ++
    return true
  }
  ArrayQueue.prototype.dequeue = function(){
    if(this.head === this.tail) return null
    this.head ++ 
    return this.items.shift()
  }

• !循环队列

  // 避免了顺序队列中的数据搬移操作
  function CircularQueue(len){
    this.items = new Array(len)
    this.n = len
    this.head = 0
    this.tail = 0
  }
  CircularQueue.prototype = {
    enqueue:function(item){
      if((this.tail+1)%n===this.head) return false
      this.items[this.tail] = item
      this.tail = (this.tail+1)%n
      return true
    },
    dequeue:function(){
      if(this.head===this.tail) return null
      const ret = this.items[head]
      this.head = (this.head+1)%n
      return ret
    }
  }

• 用链表实现-链式队列

  function Node(val){
    this.val = val
    this.next = null
  }
  function LinkedListQueue(len){
    this.head = null
    this.tail = null
    this.curLen = 0
    this.maxLen = len
  }
  LinkedListQueue.prototype = {
    enqueue: function(node){
      if(this.head===null){
        this.head = node
        this.tail = node
        this.curLen = 1
        return true
      }
      if(this.curLen >= this.len) return false
      let cur = this.head
      // 循环到链表末尾
      while(cur.next){
        cur = cur.next
      }
      cur.next = node
      this.tail = node
      this.curLen ++
      return true
    },
    dequeue : function(){
      let cur = this.head
      // 删除表头
      this.head = cur.next
      this.curLen --
      return cur
    }
  }