A queue is a first-in, first-out linear list, usually implemented as a linked list or array. Queues can only insert elements at the end of the queue and delete elements at the beginning of the queue.

Queue diagram:

The data structure of the queue

This article uses an array to implement the structure of the queue, but you need to realize that you are creating a contiguous memory space for the queue.

The data structure of a queue consists of a queue head index, a queue tail index, queue length, and a data field.

/** * The data structure of the queue, which needs to be determined when initializing the queue *@param {Number} Length Indicates the queue capacity */
function Queue(length) {
  this.head = 0;
  this.tail = -1;
  this.data = [];
  this.length = length;
}
Copy the code

The basic algorithm of queues

There are few basic algorithms for queues, roughly as follows:

/** * join the team *@param {*} The queue queue *@param {*} Element A team element@returns* /
function push(queue, element) {
  // When the queue is full, tail is the index of the last element in the queue.
  if (queue.tail + 1 >= queue.length) {
    return false;
  }
  queue.tail++;
  queue.data[queue.tail] = element;
  return true;
}

/** * output queue, traversal queue *@param {*} The queue queue * /
function output(queue) {
  Queue traversal is the same as array traversal, from the head of the queue to the end of the queue
  for (let i = queue.head; i <= queue.tail; i++) {
    console.log(queue.data[i]); }}/** * get the first element *@param {*} The queue queue *@returns Team leader element */
function front(queue) {
  return queue.data[queue.head];
}

/** * remove the head element from the queue. Note that the head index is only moved back one bit, * because the head index is needed to traverse the queue and fetch the head element. * However, the old head still has data, which can be removed or not removed because it is no longer useful. *@param {*} The queue queue * /
function pop(queue) {
  queue.head++;
}

/** * Check whether the queue is empty. The head of the empty queue is 0 and tail is -1 *@param {*} The queue queue *@returns * /
function empty(queue) {
  return queue.head > queue.tail;
}
Copy the code

The data structure of the loop queue

A circular queue is formed by connecting the ends of ordinary straight lines to form a circle.

The data structure of a circular queue is similar to that of a normal queue, with an additional attribute that records the number of elements in the queue.

/** * The data structure of the loop queue *@param {Number} Length Indicates the queue capacity */
 function CircularQueue(length) {
  this.head = 0;
  this.tail = -1;
  this.data = [];
  this.length = length;
  // This attribute is used to store the number of elements in the loop queue
  this.count = 0;
}
Copy the code

The basic algorithm of circular queue

The basic algorithm for a circular queue is the same as for a normal queue, but the internal implementation is quite different, especially to understand the (I + 1) % queue.length modulo operation when moving a header and tail index.

/** * loop queue enqueue operation *@param {*} The queue queue *@param {*} Element A team element@returns* /
function push(queue, element) {
  // If the number of elements in the loop queue is full, it cannot join the queue
  if (queue.count >= queue.length) {
    return false;
  }
  // If the index is a circular queue, it cannot be incremented by 1
  // for example: length = 8, head = 1, tail = 7, tail = 7
  // then (tail + 1) % 8 = 0, and then (tail + 1) % 8 = 0
  // The element is also successfully enqueued, which is a feature of circular queues.
  queue.tail = (queue.tail + 1) % queue.length;
  queue.data[queue.tail] = element;
  queue.count++;
  return true;
}

/** * remove the first element from the queue, and note that the end of the queue is removed when the head is moved back. * For example, if length = 8, head = 7, count = 3, tail = 1, head + 1 needs to move to 0. *@param {*} The queue queue * /
 function pop(queue) {
  queue.head = (queue.head + 1) % queue.length;
  // Then subtract the number of elements by 1
  queue.count--;
}

/** * output queue, traversal queue *@param {*} The queue queue * /
function output(queue) {
  // Loop queue traversal is more complicated than normal queue, for example:
  // length = 8, head = 1, tail = 0, count = 7; Tail is smaller than head.
  // If we go from head to length, we will find that tail is not there, so we need to do some processing.
  
  // start at head
  let i = queue.head;
  while(i ! == queue.tail) {console.log(queue.data[i]);
    i = (i + 1) % queue.length;
    // The last loop outputs the last element of the queue
    if (i === queue.tail) {
      console.log(queue.data[i]); }}}/** * check whether the loop queue is empty by checking if count is 0 *@param {*} The queue queue *@returns * /
 function empty(queue) {
  return queue.count === 0;
}
Copy the code

Test the output loop queue

const queue = new CircularQueue(8);
for (let i = 1; i <= 8; i++) {
  push(queue, i);
}
pop(queue);
pop(queue);
pop(queue);
pop(queue);
push(queue, 9);
push(queue, 7);

console.log(queue);
output(queue);
Copy the code

The purpose of the queue is the message queue

For a more detailed introduction to message queues, please refer to the relevant resources. This article is a brief introduction.

Message queues are commonly referred to as MQ(Message Queue). Its main purpose is to decoupled dependencies between projects. It is also mainly used in back-end scenarios.

Since it’s a queue, there’s a party that’s putting data into it, and there’s a party that’s reading data from it. The party storing the data is called the producer and the party taking the data is called the consumer. The message queue has evolved into a centralized data access center. Each system communicates with the message queue service, either through RPC or otherwise, to save or read the data.