An quick look at the Queue data structure

A queue is a list based data structure where data is inserted at the end and removed from the top. There are many real world example of queues for example when you are lining up for some service e.g to use an ATM, to see the doctor, at the cafeteria e.t.c, the first person in the line will be the first to be attended to.

A queue is known as a First In - First Out(FIFO) data structure since it stores data in the order it occurs i.e whatever goes in first comes out first as well. A queue is helpful when you would like to maintain data in the same sequence in which it flows in.

Types of Queue

The following are the types of queues we might need to use when building applications:-

• The default queue - This is a simple FIFO queue in which the order is retained and data leaves in the same order in which it comes in

• Priority queue - Elements in the Priority Queue are given a predefined priority and elements with a high priority leave the queue before those with a lower priority

• Circular queue - A variation of the default queue in which the back of the queue is followed by the front of the queue

• Double ended queue (Dequeue) - Similar to the default queue but can add or remove elements from either the front or the back of the queue

Queue Operations

The main queue operations include :-

1. Enqueue - inserting a new element at the end of the queue
2. Dequeue - Removing an element from the top of the queue
3. Peek - viewing the element at the front of the queue without removing it

Other important operations of the queue can be determining whether the queue is empty, determining the length/size of the queue, clearing the Queue. We shall see this in action when implementing the Queue.

Implementing a Queue

Of all the queue types discussed above, we will implement the Default Queue and the Priority Queue. Lets see how we can go about implementing them in JavaScript

The Default Queue

We shall be using a factory function to implement the Queue based on the inbuilt JavaScript array as shown below.

Explanation of the code will be in the comments

function createQueue() {
  // to store the elements in our queue
  let queue = [];

  return {
    enqueue(item) {
      // add item at the end of the queue
      queue.push(item);
      // return the queue length
      return queue.length;
    },
    dequeue() {
      // remove the element at the front of the queue and return it
      return queue.shift();
    },
    peek() {
      // return the element at the front of the queue but don't remove it
      return queue[0];
    },
    clear() {
      // empty the queue
      queue = [];
    },
    // use a getter to make length a property of the queue and not a method
    get length() {
      // return the length of the queue
      return queue.length;
    },
    // use a getter to make isEmpty a property of the queue and not a method
    get isEmpty() {
      // determine whether the queue is empty or not
      return queue.length === 0;
    },
  };
}

// Testing our Queue
// create the queue
const queue = createQueue();

console.log('Queue is empty: ', queue.isEmpty); // Output => Queue is empty:  true
console.log('Adding some elements to the queue');
queue.enqueue('Wake Up');
queue.enqueue('Take a Shower');
queue.enqueue('Take Some coffee');
queue.enqueue('Go for work');

console.log('Queue is empty: ', queue.isEmpty); // Output => Queue is empty:  false
console.log('Next Item to remove: ', queue.peek()); // Output => Next Item to remove:  Wake Up
console.log('Length: ', queue.length); // Output => Length:  4
console.log('Removed: ', queue.dequeue()); // Output => Removed:  Wake Up
console.log('Next Item: ', queue.peek()); // Output => Next Item:  Take a Shower
console.log('Length: ', queue.length); // Output => Length:  3
console.log('Clearing The Queue');
queue.clear();
console.log('Queue is empty: ', queue.isEmpty); // Output => Queue is empty:  true
console.log('Length: ', queue.length); // Output => Length:  0

In the code block above we implemented the default Queue and tested it out. We used a factory function to create it as it helps us to hide the array we use as the queue from the outside world.

The Priority Queue

In the Priority Queue, items are added and removed based on priority. It can either be a minimum priority Queue where elements with lower priority are removed first or a maximum priority Queue where elements with a maximum priority are removed first.

A real world example of the priority Queue can be the boarding line at the airport where first class passengers get priority over business class or in some cases pregnant women and elderly people are given priority. There are various approaches we can take while implementing the priority queue, the approach we will take will be adding elements with high priority at the top of the queue. By doing this, we will only modify the add method but other methods will remain as they were implemented in the default queue. Let's see this in action.

function createPriorityQueue() {
  // to store the elements in our queue
  let queue = [];

  return {
    enqueue(item, priority) {      // create queue item      const newItem = { value: item, priority };      // a variable to keep help us know whether we have added an item in the queue      let newItemIsAdded = false;      // loop through all items in the queue      for (        let currentItemIndex = 0;        currentItemIndex < queue.length;        currentItemIndex += 1      ) {        // get the current item        let currentItem = queue[currentItemIndex];        // if priority of the current item is less than priority of the item to be added        if (currentItem.priority < newItem.priority) {          // insert the current item at the current index          queue.splice(currentItemIndex, 0, newItem);          // mark newItemIsAdded as true          newItemIsAdded = true;          // break out of the loop          break;        }      }      // if we haven't added the item      if (!newItemIsAdded) {        // add it to the end of the queue        queue.push(newItem);      }      // return queue length      return queue.length;    },    dequeue() {
      // remove the element at the front of the queue and return it
      return queue.shift();
    },
    peek() {
      // return the element at the front of the queue but don't remove it
      return queue[0];
    },
    clear() {
      // empty the queue
      queue = [];
    },
    // use a getter to make length a property of the queue and not a method
    get length() {
      // return the length of the queue
      return queue.length;
    },
    // use a getter to make isEmpty a property of the queue and not a method
    get isEmpty() {
      // determine whether the queue is empty or not
      return queue.length === 0;
    },
  };
}

// Testing our priority Queue
const priorityQueue = createPriorityQueue();
priorityQueue.enqueue('Dennis', 1);
priorityQueue.enqueue('John', 2);
priorityQueue.enqueue('Rain', 3);
priorityQueue.enqueue('Don', 2);

console.log(priorityQueue.peek()); // { value: 'Rain', priority: 3 }
console.log('Length: ', priorityQueue.length); // Length:  4
console.log('Is Empty: ', priorityQueue.isEmpty); // Is Empty:  false
console.log('Removing: ', priorityQueue.dequeue()); // Removing:  { value: 'Rain', priority: 3 }
console.log(priorityQueue.peek()); // { value: 'John', priority: 2 }
console.log('Clearing priority queue');
priorityQueue.clear();
console.log('Length: ', priorityQueue.length); // Length:  0
console.log('Is Empty: ', priorityQueue.isEmpty); // Is Empty:  true

The enqueue method is highlighted in the priority queue implementation since its the only method we have modified. Thanks you for reading this blog post this far. If there is anyway this can be made better, reach out to me on twitter.