Hello, I’m 17.

Unlike priority queues, sequential queues have no privileges, and all elements are equal, first-in, first-out.

code

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
  }
}
Copy the code

Method names refer to array names. Push is at the end of the team element, pop is at the beginning of the team element. Length is the length of the queue. I’m going to refer to array names for all of the methods on the related linear tables, so it’s nice not to remember.

The time complexity of each element is O(1), which is the advantage of using linked lists. If implemented as an array, the outgoing or incoming queue will be O(n). Another way to implement this is to use a hash table, where sequential numbers are used as keys. The advantage is that you can query elements in any position, but the disadvantage is that the number may encounter an upper limit.

So if you just start at the end of the team and start at the end of the team, a linked list is the best choice.

application

One application of sequential queuing is to cache data. Create a buffer between producers and consumers to alleviate the contradictions of inconsistent production and consumption rates.

In practical applications, it may be that the producers are particularly strong at a certain time, resulting in a large queue, so a limit has to be added.

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
  }
}
Copy the code

Add the Max parameter, the maximum length limit, and it is a kind of insurance. If the length is exceeded, the new element enters the team, and the old element leaves the team, holding the maximum length.