Data Structure: Queue

Summary

Data Structure Name	Queue
Type	Linear Data Structure
Tagline	FIFO – First In First Out
Operations	Enqueue Dequeue
Use cases
Implementations

Definition

Queue follows the FIFO – First In First Out principle, so the item which is inserted at first, will go out first. Elements are added to the back of the queue and pulled out from the front of the queue.

NOTE

Check the link below to check the details of Linked List and Singly Linked List-

Queue Details

Use Cases

Queue data structures are created for maintaining a queue of tasks or processes, so that we can we can maintain the sequence of the items and process those one by one. First-in-First-out is used for processing a queue.

We can implement a Queue in Javascript using the Linked List data structure, or by simply using an array. However, using the array implementation is not recommended as it can cause performance issues for long queues.

Let’s check the implementation processes of a Queue in JavaScript-

Implementation #1: Queue using Linked List

A Singly Linked List case be used to implement a Queue. We need to consider the following-

• We consider the head of the list as the “Front” of the queue.
• We consider the tail of the list as the “Rear” of the Queue.
• To enqueue an item we add/push it to the end of the queue.
• To dequeue we just need to shift items from the front.

Step #1: Node(Queue item) Class

We need a node class to store the queue items. This stores data, and info of the next node.

Step #2: Queue Class

Queue class is responsible for storing information about the front, rear, and handling operations.

Step #3: Enqueue

To enqueue we need to add the item at the end/rear of the queue.

Step #4: Dequeue

To dequeue, we will shift nodes from the front of the list-

Full Implementation Code

Here is the full implementation, with all the functionality.

Demo

Here is the demo code for using the implemented functionality of Queue-

Output:

Output of the demo code will look like below-

----------- Queue - Enqueue example -----------

Enqueue - "Big" | Result: size =  1
Enqueue - "Box" | Result: size =  2
Enqueue - "Code" | Result: size =  3


----------- Queue - Dequeue example -----------

Dequeue | Result:  Big
Dequeue | Result:  Box
Dequeue | Result:  Code
Dequeue | Result:  null

Tests

Let’s test the functionality using automated testing. Use the following code for testing.

Time Complexity

The time complexity of operation on a Queue implementation using a linked list is as below-

Implementation #2: Queue using Array (not recommended)

We can store the full queue information in an array. Just declare it an array, and use that as a queue-

• Enqueue items by pushing/adding items at the end.
• Dequeue by shifting array element from the starting of the array.

Enqueue

Let’s enqueue items to the declared array-

• Declare an array. We have declared “queueItems” variable and initialized it as with an empty array.
• We can use the push() method of the array – Array.prototype.push(), to add an item at the end of the array.

let queueItems = [];

// Let's enqueue some items at the end of the array
// We can use Array.prototype.push() function for that
queueItems.push("Big");
queueItems.push("Box");
queueItems.push("Code");

Dequeue

To dequeue we can just shift items from the start of the array-

• Use the shift() method to shift items from the front- Array.prototype.shift().
• This returns the item from the start of the array, and removes it from the array.

// Let's dequeue item one by one 
// We can use Array.prototype.shift() for that
let popItem = queueItems.shift();

console.log("popItem: ", popItem);

popItem = queueItems.shift();

console.log("popItem: ", popItem);

popItem = queueItems.shift();

console.log("popItem: ", popItem);

popItem = queueItems.shift();

console.log("popItem: ", popItem);

Output:

popItem:  Big

popItem:  Box

popItem:  Code

popItem:  undefined

Wrap it in a Class

We can wrap it in class, and expose only the required functionality. This way, no one will exploit the array directly.

class Queue {
    construct() {
        this.queueItems = [];
    }

    enqueue(data) {
        queueItems.push(data);

        return queueItems.length;
    }

    dequeue() {
        return queueItems.shift();
    }
}

Let’s check the implementation.

const bigboxQueue = new Queue();

// Let's enqueue some items
bigboxQueue.enqueue("Big");
bigboxQueue.enqueue("Box");
bigboxQueue.enqueue("Code");

// Let's dequeue item one by one
let dequeueItem = bigboxQueue.dequeue();

console.log("dequeueItem: ", dequeueItem);

dequeueItem = bigboxQueue.dequeue();

console.log("dequeueItem: ", dequeueItem);

dequeueItem = bigboxQueue.dequeue();

console.log("dequeueItem: ", dequeueItem);

dequeueItem = bigboxQueue.dequeue();

console.log("dequeueItem: ", dequeueItem);

Output:

dequeueItem:  Big

dequeueItem:  Box

dequeueItem:  Code

dequeueItem:  undefined

Problem with this approach

Problem with this approach is in the dequeue process-

Every time we shift an item from the start of the array, the rest of the items need to be reindexed. The bigger the array, the more time it takes to reindex.

This increases the time complexity of this approach. That is why this approach is not recommended for large queues.

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Singly Linked List	Singly Linked List Detail

Other Code Implementations

Use the following links to check the Queue implementation in other programming languages-