大家好，我是 17。
和 优先队列 不同,顺序队列没有特权，所有元素都是平等的，先进的先出。
代码
class Node { constructor(val) { this.val = val this.next = null } } class Queen { constructor() { this.length = 0 const node = new Node() this.head = node this.tail = node } push(val) { const node = new Node(val) this.tail.next = node this.tail = node this.length++ } pop() { if (this.length <= 0) return undefined let val = this.head.next.val this.head = this.head.next this.length-- return val } peekHead() { if (this.length <= 0) return undefined else return this.head.next.val } peekTail(){ if (this.length <= 0) return undefined else return this.tail.val } } 复制代码
方法命名参照数组的命名。push 是在队尾入队元素，pop 是在队首出队元素。length 是队列的长度。我在所有相关 线性表 的方法命名上都会参考数组命名，这样的好处是不用记。
入队和出队一个元素的时间复杂度都是 O(1),这是用链表的好处。如果用数组来实现的话，出队或入队将为 O(n)。还有一种实现方式是用 hash 表的方式，用连续的数字做 key，好处是可以查询到任意位置的元素，坏处是数字可能遇到上限。
所以如果只是从队尾入，从队首出的话，链表是最好的选择。
应用
顺序队列的一个应用是缓存数据。在生产者和消费者之间建立一个缓冲，以缓解生产和消费速度不一致的矛盾。
在实际应用中，可能生产者在某段时间的能力特别强，会导致队列过大，所以还得加个限制。
class Queen { constructor(max = Infinity) { this.max = max this.length = 0 const node = new Node() this.head = node this.tail = node } push(val) { const node = new Node(val) this.tail.next = node this.tail = node this.length++ if (this.length > this.max) { this.pop() } } pop() { if (this.length <= 0) return undefined let val = this.head.next.val this.head = this.head.next this.length-- return val } peek() { if (this.length <= 0) return undefined else return this.head.next.val } } 复制代码
加上 max 参数，最大长度限度，相当于是一个保险。如果超过长度，新元素入队，老元素出队，操持最大长度。
