Queue data structure

May 7, 2023

This is a first article of the series of data structure and algorithms, were a talk and implemented of basic and complexes data structure and algorithms in JavaScript Python perhaps in Rust and C++.

In this article we let's talk about a data structure called queue you have probably already seen.

Queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. Wikipedia

Basically queue is a equal of queue in real life, example in super market, the first person to arrive is the first to be served, but how to implement that in code and which ?

The queues is used in implementation of search algorithms as BFS (Breadth First Search) that we’ll see in over time, but an example is in CPU or printers...

In system of multitasking equal of CPU it’s need choose witch process it must run next, using a queue of process cpu can select the next process with your position in a queue.

Said that, let's see in code…

1class Queue {
2  constructor() {
3    this.elements = [];
4  }
5}

We create a class called Queue and in constructor we created elements properties, in properties we'll add entities, start with simple method called enqueue this method will add an entities in front of the queue:

1class Queue {
2  constructor() {
4  }
5
6  enqueue(element) {
7    this.elements.push(element);
8  }
9}

method enqueue receive a element and use a method array push for add element in position 0 .

This is easy right?

Now let's implemented method dequeue, this method it will remove the first element inqueue

1class Queue {
2  constructor() {
4  }
5  enqueue(element) {
7  }
8
9  dequeue() {
10    return this.elements.shift();
11  }
12}

basically we used a method shift for remove the first element and return it.

now we need get a element that are in front (first element)

1class Queue {
2  constructor() {
4  }
5  enqueue(element) {
7  }
8  dequeue() {
10  }
11
12  front() {
13    return this.elements[0];
14  }
15}

We created a method front that return a element that been in position 0 , also we need a last element and in JavaScript the last element in array its are in -1 position.

We can use this syntax:

1back() {
2  return this.elements[-1];
3}

but there is better way of doing, like that:

1back() {
2 return this.elements.at(-1);
3}

We also have a method size it will return size of queue, and its very sample, see:

1size() {
2  return this.elements.length;
3}

and to finish we have a method isEmpty we use for verify if method is empty or no

1isEmpty() {
2  return this.elements.length === 0;
3}

We just checked if size is equal a 0 if it’s return true if is different it’s will return false

Checked the complete code:

1class Queue {
28}

Now let’s go to run the test:

1const queue = new Queue();
2
3queue.isEmpty(); // true
4queue.size(); // 0
5
6queue.enqueue(1); // [1]
7queue.enqueue(2); // [1, 2]
8queue.enqueue(3); // [1, 2, 3]
9queue.enqueue(4); // [1, 2, 3, 4]
10queue.enqueue(5); // [1, 2, 3, 4, 5]
11
12queue.isEmpty(); // false
13queue.size(); // 5;
14queue.front(); // 1;
15queue.back(); // 5;
16
17queue.items; // [1, 2, 3, 4, 5];
18
19queue.dequeue(); // [2, 3, 4, 5];
20queue.dequeue(); // [3, 4, 5];
21queue.dequeue(); // [4, 5];
22queue.dequeue(); // [5];
23queue.isEmpty(); // false
24queue.dequeue(); // []
25queue.isEmpty(); // true
26queue.size(); // 0;

in line 1 we create a instance of queue

  • before we verify is empty, this method should return true because we not add a element in queue.
  • method size should return 0 our queue have a 0 element, etc…