Introduction to Queues (using ES6)

In my previous article, “Data Structure Basics: Stack Introduction (using ES6),” I introduced you to what a data structure is and what a stack is and how to implement it. In this article, I introduce you to what a queue is and how to implement it.

This article will be introduced from the following aspects:

• What is a queue
• How do you implement queues in code
• What is a double-endian queue
• How to implement a double-endian queue in code
• Practical Application Examples

The reading time for this article is expected to be 10 minutes.

What is a queue

A queue is an ordered collection that follows a first-in, first-out (FIFO) principle, as opposed to a stack. The end that allows insertion is called the tail, and the end that allows deletion is called the head. Suppose the queue is q=(A1,a2,…… So A1 is the head of the team and an is the end of the team. When we delete, we delete from a1, and when we insert, we can only insert after an.

Queues are just like queues in our life. For example, we need to queue up to register at the hospital, queue up to enter the cinema, queue up to pay for shopping at the supermarket, queue up to answer customer service calls and so on.

Is one of the most common example is the printer in computer print queue tasks, suppose we want to print at five different documents, we need to open each document in turn, in turn, click the “print” button, each printed instructions will be sent to the print queue tasks, first press the print button in the document the first to be printed, completed until all documents are printed.

How do you implement queues in code

Create an initialization statement. First we will queue class, implementation code is as follows:

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

First, we create a data structure to store the queue elements. We declare the count variable so that we can count the queue size. We declare the lowestCount variable to mark the head of the queue so that we can delete the elements. Next we declare the following methods to implement a complete queue:

• Enqueue (Element) : This method is used to add elements to the end of the queue.
• Dequeue (): This method is used to delete the header element of a queue.
• Peek (): This method is used on the header element of the queue.
• IsEmpty (): this method is used to determine whether the queue isEmpty, returning True if it is, False if it is not.
• Size (): This method returns the size of the queue, similar to the array length property.
• Clear (): clears all elements of the queue.
• ToString () : Prints the elements in the queue.

enqueue(element)

This method is mainly implemented to add new elements to the end of the queue, the key is to “end of the queue” to add elements, the implementation code is as follows:

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

Since the items property of the queue is an object, we use count as the property of the object, and count increments by 1 when the element is added to the queue.

dequeue()

This method is mainly used to delete queue elements. Since the queue follows the first-in-first-out principle, we need to remove the “queue head” element of the queue. The code implementation is as follows:

dequeue() {
  if (this.isEmpty()) {
    return undefined;
  }
  const result = this.items[this.lowestCount]; 
  delete this.items[this.lowestCount];
  this.lowestCount++;
  return result; 
}Copy the code

First we need to verify that the queue is empty or undefined if not. If the queue is not empty, we first get the “head” element, then delete it using the delete method, incrementing the lowestCount variable of the header element by one, and then return the deleted head element.

peek()

Now let’s implement some helper methods. For example, if we want to look at the “team head” element, we use the peek() method and use the lowestCount variable to get it.

peek() {
  if (this.isEmpty()) {
    return undefined;
  }
  return this.items[this.lowestCount];
} Copy the code

The size () and isEmpty ()

To get the length of the queue, we can use the count variable to subtract lowestCount from lowestCount. If our count attribute is 2 and lowestCount is 0, that means the queue has two elements. Next we remove an element from the queue, update lowestCount to 1, keep count unchanged, so the length of the queue is 1, and so on. So the code for the size() method is as follows:

size() {
  return this.count - this.lowestCount;
} Copy the code

IsEmpty () is easier to implement, just check whether size() returns 0. The code is as follows:

isEmpty() {
  return this.size() === 0;
}Copy the code

clear()

To clear the queue, we can call the dequeue() method until we return undefined or reset each variable to its initial value. We use the reset initialization method as follows:

clear() {
  this.items = {};
  this.count = 0;
  this.lowestCount = 0;
}Copy the code

toString()

Next we implement the last method, which prints all the elements of the queue, as shown in the following example:

toString() {
  if (this.isEmpty()) {
    return ' ';
  }
  let objString = `${this.items[this.lowestCount]}`;
  for (let i = this.lowestCount + 1; i < this.count; i++) {
    objString = `${objString}.${this.items[i]}`;
  }
  return objString;
} Copy the code

Finally, the complete queue class

export default class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  isEmpty() {
    return this.size() === 0;
  }

  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  toString() {
    if (this.isEmpty()) {
      return ' ';
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}.${this.items[i]}`;
    }
    returnobjString; }}Copy the code

How to use the Queue class

We first import our Queue, then initialize our Queue, verify that it is empty, and then add and remove elements as follows:

const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue('John');
queue.enqueue('Jack');
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John,Jack,Camila
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove John
queue.dequeue(); // remove Jack
console.log(queue.toString()); // CamilaCopy the code

The following illustration illustrates the implementation of the above code:

What is a double-endian queue

Double-ended queues are a special, more flexible queue where we can add and remove elements at the “head” or “tail” of the queue. Since the two-endided queue implements the two principles of FIFO and LIFO, it can also be said to be a combination of queue and stack structure.

In our life, for example, when queuing for a ticket, some people are in a hurry or under special circumstances and come directly to the front of the queue, while some people leave from the back of the queue because they cannot wait too long for other things.

How to implement a double-endian queue in code

First, we declare the initialization of a double-ended queue. The code is similar to the structure of the queue, as shown in the following code:

class Deque {
  constructor() { this.count = 0; this.lowestCount = 0; this.items = {}; }}Copy the code

Since the structure of a double-ended queue is similar to that of a queue, except that insertion and deletion are more flexible, the isEmpty(), clear(), size() and toString() methods remain the same, and the following related methods need to be added:

• AddFront (Element) : This method is used to add elements to the “head” of a double-ended queue.
• AddBack (Element) : This method is used to add elements to the “tail” of a two-ended queue.
• RemoveFront () : This method is used to remove the “queue head” element of a two-end queue.
• RemoveBack () : This method is used to remove the “tail” element of a two-end queue.
• PeekFront () : This method is used to return the “queue head” element of a two-ended queue
• PeekBack () : This method is used to return the “tail” element of a two-ended queue

addFront(element)

Adding elements from the “head” of a double-ended queue is a bit more complicated, and the implementation code looks like this:

addFront(element) {
  if (this.isEmpty()) {
    this.addBack(element);
  } else if (this.lowestCount > 0) {
    this.lowestCount--;
    this.items[this.lowestCount] = element;
  } else {
    for (leti = this.count; i > 0; i--) { this.items[i] = this.items[i - 1]; } this.count++; this.lowestCount = 0; this.items[0] = element; }}Copy the code

As we can see from the above code, if the double-ended queue is empty, we reuse the addBack() method to avoid writing duplicate code; If lowestCount is greater than 0, we decrement the variable and assign the newly added element to the header element; If the lowestCount variable is 0, to avoid negative values, we reassign the queue element by moving it back 1 bit, leaving the 0 position of the queue header index for the newly added element.

The final implementation of Deque class

Due to the limited space of the article, other methods are very similar, not one by one, the complete code is as follows:

export default class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  addFront(element) {
    if (this.isEmpty()) {
      this.addBack(element);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.items[0] = element;
    }
  }

  addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }

  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  isEmpty() {
    return this.size() === 0;
  }

  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  toString() {
    if (this.isEmpty()) {
      return ' ';
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}.${this.items[i]}`;
    }
    returnobjString; }}Copy the code

How to use the Deque class

Next we verify our Deque class, first introduce the Deque class file, the code is as follows:

const deque = new Deque();
console.log(deque.isEmpty()); // outputs true
deque.addBack('John');
deque.addBack('Jack');
console.log(deque.toString()); // John,Jack
deque.addBack('Camila');
console.log(deque.toString()); // John,Jack,Camila
console.log(deque.size()); // outputs 3
console.log(deque.isEmpty()); // outputs false
deque.removeFront(); // remove John
console.log(deque.toString()); // Jack,Camila
deque.removeBack(); // Camila decides to leave
console.log(deque.toString()); // Jack
deque.addFront('John'); // John comes back forinformation console.log(deque.toString()); / / John, Jack"Copy the code

Example 1: Drum passing flowers

I do not know that we have played the drum spread flower, the author is most afraid to play this, DO not know is the point back is still how, this flower ball sum I have fate, itself is tone-deaf also want to perform, people can lose big. A few or dozens of people sit in a circle, and one of them takes the flowers (or a small object); Another person behind everyone or blindfolded drum (table, blackboard or other objects that can make sound), when the drum rang, everyone began to pass flowers in turn, until the drum stopped. At this point in the hands of the flower (or in front of its seat), who will perform on stage (mostly singing, dancing, telling jokes; Or answer questions, solve puzzles, act according to the instructions on paper, etc.); Occasionally, if the flower is in two hands, the two can decide the loser by guessing or other means.

Today we’re going to implement the game in a queue, with the slight difference that the person with the flower ball has to step out of the queue until the last person with the flower ball wins. Assume that the drummer is told a number (starting from 0), and that everyone present is told to stop beating until the last person is there.

Are you dying to see how the code works? The code looks like this:

function hotFlower(elementsList, num) {
  const queue = new Queue(); 
  const elimitatedList = [];

  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[i]); 
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue()); 
    }
    elimitatedList.push(queue.dequeue()); 
  }

  return {
    eliminated: elimitatedList,
    winner: queue.dequeue() 
  };
}Copy the code

From the above code we can see:

• We declare a queue and an array elimitatedList.
• The given object elementsList is iteratively populated and assigned to the queue.
• Then, under the given variable num, the first element of the queue is continuously deleted and inserted into the end of the queue, rather keeping the number of queues unchanged, and moving the queue in turn. (Circular queue)
• When num is reached, delete the head element of the current queue and add the head elimitatedList to the array.
• Until the element of the queue is 1, the function prints elimitatedList and winner.

Next, let’s verify whether this algorithm is correct. The verification code is as follows:

const names = ['John'.'Jack'.'Camila'.'Ingrid'.'Carl'];
const result = hotFlower(names, 7);

result.eliminated.forEach(name => {
  console.log(`${name} was eliminated from the Hot Flower game.`);
});

console.log(`The winner is: ${result.winner}`);Copy the code

The above code will print:

Camila was eliminated from the Hot Flower game.
Jack was eliminated from the Hot Flower game.
Carl was eliminated from the Hot Flower game.
Ingrid was eliminated from the Hot Flower game.
The winner is: JohnCopy the code

When the code runs, the queue looks like this:

Example 2: Verify English palindromes

Many English words have exactly the same form and meaning whether read backwards or backwards: dad, noon, level, etc. The simplest way to do this is to reverse the string to see if it is equal to the original string. From the point of view of the data structure, we can use the stack structure to achieve, but it is also very simple to use the structure of the double-ended queue, the example code is as follows:

function palindromeChecker(aString) {
    if(aString === undefined || aString === null || (aString ! == null && aString.length === 0)) {return false;
    }
    const deque = new Deque(); 
    const lowerString = aString.toLocaleLowerCase().split(' ').join(' '); 
    let isEqual = true;
    let firstChar, lastChar;

    for (let i = 0; i < lowerString.length; i++) {
        deque.addBack(lowerString.charAt(i));
    }

    while (deque.size() > 1 && isEqual) { 
        firstChar = deque.removeFront();
        lastChar = deque.removeBack(); 
        if(firstChar ! == lastChar) { isEqual =false; }}return isEqual;
}Copy the code

From the above code we can see:

• First we need to verify that the input string is valid.
• Declare to instantiate a two-ended queue.
• Converts the input string to lowercase and removes Spaces.
• The string is then broken up into characters and added to a double-ended queue
• The two exit methods of removeFront() and deque.removeback () are then compared and the Fasle exit method is returned as long as they are not equal.
• Returns the Boolean variable isEqual, True is palindrome, fasle

Next, let’s verify whether our algorithm is correct:

console.log('a', palindromeChecker('a'));
console.log('aa', palindromeChecker('aa'));
console.log('kayak', palindromeChecker('kayak'));
console.log('level', palindromeChecker('level'));
console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car or a cat I saw'));
console.log('Step on no pets', palindromeChecker('Step on no pets'));Copy the code

The above code all returns true.

section

That’s all for today’s introduction to queues. We’ve learned what queues and double-endian queues are and how to implement them in code. And the use of circular queue mechanism to achieve the drum pass flowers of the game, at the same time using the structure of double – end queue to achieve palindrome verification. In fact, queues are widely used in our actual business scenarios, such as the message push mechanism of a queue, the time loop mechanism of our JS event loop, and the page rendering mechanism of the browser. I hope that the content of this article will be helpful to you. In practice, we can only use the mechanism of queues to solve more practical problems.