队列

算法
留言

队列

队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用链表实现的叫链式队列。

特别是长得像一个环的循环队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。
801336-20200502092159003-1561337601

队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。

用数组实现队列

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(value) {
    this.items.push(value);
  }

  dequeue() {
    return this.items.shift();
  }

  print() {
    console.log(this.items.toString());
  }
}

var queue = new Queue();
queue.enqueue("Jack");
queue.enqueue("Mike");
queue.enqueue("Candy");
queue.print(); // Jack,Mike,Candy
queue.dequeue();
queue.print(); // Mike,Candy

基于链表实现的队列

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class QueueBasedOnLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  enqueue(value) {
    if (this.head === null) {
      this.head = new Node(value);
      this.tail = this.head;
    } else {
      this.tail.next = new Node(value);
      this.tail = this.tail.next;
    }
  }

  dequeue() {
    if (this.head !== null) {
      const value = this.head.element;
      this.head = this.head.next;
      return value;
    } else {
      return -1;
    }
  }
}
// Test
const newQueue = new QueueBasedOnLinkedList();
// 插入元素
newQueue.enqueue(1);
newQueue.enqueue(2);
newQueue.enqueue(3);
// 获取元素
let res = 0;
console.log("-------获取dequeue元素------");
while (res !== -1) {
  res = newQueue.dequeue();
  console.log(res);
}

阻塞队列和并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队