介绍

队列（Queue）是一种特殊的线性表，它的特殊之处在于它只允许在表的前端进行删除操作，在表的后端进行插入操作，与栈相同，它也是一种操作受限制的线性表，遵循 FIFO模式（先进先出）。

进行删除操作的一端为队首，进行插入操作的一端为队尾。

代码实现

顺序队列

使用数组来作为队列，数组的 push() 和 shift() 来作为队列的插入（入队）和删除（出队）操作。

function Queue() { 
    this.dataStore = []; 
    this.length = length; 
    this.enqueue = enqueue; // 入队
    this.dequeue = dequeue; // 出队
    this.front = front; // 队首
    this.back = back; // 队尾
    this.toString = toString; 
    this.empty = empty; 
} 
function enqueue(element) { 
    this.dataStore.push(element); 
} 
function dequeue() { 
    return this.dataStore.shift(); 
} 
function front() { 
    return this.dataStore[0] 
} 
function back() { 
    return this.dataStore[this.length() - 1]; 
} 
function empty() { 
    return this.length() ? true : false; 
} 
function toString() { 
    let str = ""; 
    this.dataStore.map(item => { 
        str += item + "\n" 
    }) 
    return str; 
} 
function length() { 
    return this.dataStore.length; 
}

链表队列

function Node(value) {
  this.value = value
  this.next = null
}
function LinkQueue() {
  this.first = null
  this.last = null
  this.size = 0
  this.enqueue = enqueue // 入队
  this.dequeue = dequeue // 出队
}

function enqueue(val) {
  var newNode = new Node(val)
  if (!this.first) {
    this.first = newNode
    this.last = newNode
  } else {
    this.last.next = newNode
    this.last = newNode
  }
  return ++this.size
}

function dequeue() {
  if (!this.first) return null

  var temp = this.first
  if (this.first === this.last) {
    this.last = null
  }
  this.first = this.first.next
  this.size--
  return temp.value
}

const quickQueue = new LinkQueue()

quickQueue.enqueue("value1")
quickQueue.enqueue("value2")
quickQueue.enqueue("value3")

console.log(quickQueue.first)
/* 
  Node {
    value: 'value1',
    next: Node { value: 'value2', next: Node { value: 'value3', next: null } }
  }
*/
console.log(quickQueue.last) // Node { value: 'value3, next: null }
console.log(quickQueue.size) // 3

quickQueue.enqueue("value4")
console.log(quickQueue.dequeue()) // value1

循环队列

function CircularQueue(len) {
  this.list = Array(len)
  this.size = 0 // 队列当前长度
  this.front = 0 // 队首位置
  this.rear = 0 // 队尾之后可插入元素位置
  this.max = len // 队可容纳长度

  this.enqueue = enqueue // 入队
  this.dequeue = dequeue // 出队
  this.first = first // 队首元素
  this.last = last // 队尾元素
  this.toString = toString // 按队列顺序打印元素
}

function enqueue(val) {
  if (this.size === this.max) {
    throw 'error full queue'
  } else {
    this.list[this.rear] = val
    this.rear = (this.rear + 1) % this.max
    this.size ++
    return true
  }
}

function dequeue() {
  if (this.size === 0) {
    throw 'error null queue'
  }
  const first = this.list[this.front]
  this.list[this.front] = null
  this.front = (this.front + 1) % this.max
  this.size --
  return first
}

function first() {
  if (this.size === 0) {
    throw 'error null queue'
  }
  return this.list[this.front]
}

function last() {
  if (this.size === 0) {
    throw 'error null queue'
  }
  const lastIdx = this.rear - 1 < 0 ? this.max - 1 : this.rear - 1
  return this.list[lastIdx]
}

function toString() {
  if (this.size === 0) {
    return ''
  }
  let front = this.front
  let ret = []
  while (front !== this.rear) {
    ret.push(this.list[front])
    front = (front + 1) % this.max
  }
  return ret.join(',')
}

const queue = new CircularQueue(4)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.dequeue()
queue.dequeue()
queue.enqueue(5)
console.log(queue.toString()) // 3,4,5
console.log(queue.first()) // 3
console.log(queue.last()) // 5