Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Hello, I’m Yang Chenggong.

In the last few articles, we looked at two data structures — arrays and stacks. Today’s data structure is called a queue. Queues are very similar to stacks, except that stacks follow the “last in, first out” principle, while queues, on the other hand, can only be “first in, first out”.

What is a queue

A queue is an ordered collection that follows a first-in, first-out (FIFO, also known as first come, first served) principle. Queues, like stacks, are essentially arrays.

Queues add new elements to the tail and remove the nearest element from the top. Newly added elements must be at the end of the queue, and elements must be read from the front of the queue. Add and read can be carried out simultaneously without affecting each other.

In our life, the most common and typical example is queuing. Everyone is familiar with the queue. The first person in line gets to work first and can leave as soon as he is done. The person at the end of the line has to wait until the person at the front is done. This is the “first come, first served” principle.

Of course, there are also unruly people who cut in line, which will be condemned or even beaten by everyone. The queue also does not allow you to cut in line, you must follow the order, so the queue is an “orderly collection”.

One of the things we hear a lot about in programming is “task columns”. A task column is a set of computer tasks queued up for the CPU to execute. New tasks are added to the queue from the bottom and fetched from the top by the CPU as it executes. It’s fair to add tasks on one end and perform tasks on the other.

Implementing a queue

Again, we implement a queue based on objects in JavaScript.

class Queue {
  constructor() {
    this.start = 0;
    this.end = 0;
    this.items = {}; }}Copy the code

The above code declares a class called Queue, where the Items property is the object that stores the Queue elements. We’re basically going to operate on this object with the queue.

It’s actually easier to do it with an array. But as we said in the stack article, when arrays are very large, data manipulation performance becomes very low. So in order to achieve a more efficient data structure, we implement it directly with objects.

The other two properties have the following meanings:

  • start: represents the key of the first element in the queue
  • end: represents the key of the last element in the queue

Once we have the attributes, we also need to create methods in this class that specify add/remove operations to the queue in accordance with FIFO rules. Specific methods are as follows:

  • enqueue(): Adds a new element to the end of the queue
  • dequeue(): Removes the first item in the queue
  • peek(): returns the first element of the queue
  • isEmpty(): Checks if there are any elements in the queue, and returns true if there are none
  • clear(): Clears all elements in the queue
  • size(): Returns the number of elements in the queue

Let’s start by adding elements to a queue (column) :

enqueue(item) {
  this.items[this.end] = item;
  this.end++;
}
Copy the code

Since the element is added at the end, we use the end attribute as the key of the Items object, assign it to the passed parameter item, and finally increment the value of the end attribute.

The end attribute is modeled after the array’s.length attribute, but in a queue, the end attribute does not change when an element is removed from the queue, meaning that end is always incremented whenever a new element is added to the queue.

Now look at how to remove an element from a queue:

dequeue() {
  if(this.isEmpty()) {
    return undefind;
  }
  let item = this.items[this.start]
  delete this.items[this.start]
  this.start++;
  return item;
}
Copy the code

This code is easy to understand, first nullates, then retrieves the first element, deletes it, not forgetting to increment the start attribute by one, and finally returns the deleted element.

So the start and end attributes are incremented by one when the queue is dequeued and enqueued, respectively.

With this in mind, the remaining methods are relatively simple:

size() {
  return this.end - this.start;
}
isEmpty() {
  return this.end - this.start === 0;
}
peek() {
  if(this.isEmpty()) {
    return undefind;
  }
  return this.items[this.start]
}
clear() {
  this.items = {}
  this.start = 0
  this.end = 0
}
Copy the code

You also need a toString method. Because the value of an object converted to a string is [Object object], we want something like an array, where all elements are printed as a comma-separated string.

Let’s see how:

toString() {
  let arr = Object.values(this.items)
  return arr.toString();
}
Copy the code

The final code is as follows:

class Queue {
  constructor() {
    this.start = 0;
    this.end = 0;
    this.items = {};
  }
  enqueue(item) {
    this.items[this.end] = item;
    this.end++;
  }
  dequeue() {
    if(this.isEmpty()) {
      return undefind;
    }
    let item = this.items[this.start]
    delete this.items[this.start]
    this.start++;
    return item;
  }
  size() {
    return this.end - this.start;
  }
  isEmpty() {
    return this.end - this.start === 0;
  }
  peek() {
    if(this.isEmpty()) {
      return undefind;
    }
    return this.items[this.start]
  }
  clear() {
    this.items = {}
    this.start = 0
    this.end = 0
  }
  toString() {
    let arr = Object.values(this.items)
    returnarr.toString(); }}Copy the code

Using the queue

A queue class is used to create a queue.

var queue = new Queue();
console.log(queue.isEmpty()) // true
Copy the code

First perform the column operation, add Beijing, Shanghai two elements.

queue.enqueue('Beijing')
queue.enqueue('Shanghai')
console.log(queue.size()) / / 2
console.log(queue.toString()) // 'Beijing, Shanghai'
Copy the code

According to the printed results, it is completely in line with expectations. Let’s see the column operation again:

console.log(queue.dequeue()) / / Beijing
console.log(queue.dequeue()) / / Shanghai
console.log(queue.dequeue()) // undefined
console.log(queue.size()) / / 0
console.log(queue.toString()) / /"
Copy the code

The previous steps start at the head of the queue and gradually move the elements out until the queue is empty. We can see that the queue does follow the first-in, first-out principle.

That’s it. Did you learn? In the next article, we will introduce two – ended queues

Join a study group

This article source public number: programmer success. This is the sixth chapter of learning JavaScript data structures and algorithms, this series will be updated for a month, welcome to pay attention to the public account, click “add group” to join our learning team ~