Queue Data Structure - Types, Applications, JavaScript Implementation

Think of a queue at the cinema theatre counter. The person standing first in the queue gets the ticket and leaves the group, while a new person joins at the back end of the queue.

Queue Data Structure - Types, Applications, JavaScript Implementation

What is Queue Data Structure?

A queue is a linear data structure that contains elements in an ordered sequence. It is an abstract data type, pretty similar to a stack.

But unlike stacks, we can perform operations at both ends of a queue.

We insert data at one end of the queue and remove data from the other end.

Think of a queue at the cinema theatre counter. The person standing first in the queue gets the ticket and leaves the group, while a new person joins at the back end of the queue.

This is at the center of the working of a queue, known as the First In First Out principle.

(Remember, stack uses the First In Last Out principle)

First in first out principle in queue data structure
First In First Out Principle

Basic Operations of a Queue

We can perform the following operations on a queue-

  • Enqueue() – This is the process of adding or storing an element to the rear end(back-end) of a queue.
  • Dequeue() – It refers to removing or accessing an element from the front-end of a queue.
  • peek() – This function brings the asked element to the front-end of the queue without removing it.
  • isEmpty() – It checks if the queue is empty.
  • isFull() – It checks if the queue is full.

By now you would have understood, that we need two pointers for two different functions in a queue. The front pointer is used to access or Dequeue an element, while the rear pointer points to the new element that is added.

How does Queue work?

Here’s how a queue’s operations work-

  • The front pointer points to the first element of the queue
  • The rear pointer points to the last element
  • In an empty stack, we set values of Front and Rear to -1.

Enqueue Operation

  • Check if the queue is full
  • Set the value of Front to 0
  • Shift the Rear pointer to 1
  • Add the new element where the Rear is pointing.

Dequeue Operation

  • Check if the queue is empty
  • Return the element that is in the Front position
  • Increase the Front index by 1, and the Rear stays the same.

In this way, we can continue the Dequeue Operation one by one till we reset both the pointers at -1, making it an empty queue

Enqueue and Dequeue operations
Enqueue and Dequeue Operations

Implemention of Queue Data Structure

We can implement a queue in the following two ways-

Sequential allocation – It can be implemented using an array. In this implementation, the queue can only store a limited number of elements.

Linked list allocationA queue implemented using a linked list can store/organize an unlimited number of elements.

JavaScript Program to implement a queue using an array.

class Queue {
    constructor() {
        this.items = [];
    }

    // add element to the queue
    enqueue(element) {
        return this.items.push(element);
    }

    remove element from the queue
    dequeue() {
        if(this.items.length > 0) {
            return this.items.shift();
        }
    }

    // view the last element
    peek() {
        return this.items[this.items.length - 1];
    }

    // check if the queue is empty
    isEmpty(){
       return this.items.length == 0;
    }

    // the size of the queue
    size(){
        return this.items.length;
    }

    // empty the queue
    clear(){
        this.items = [];
    }
}

Types of Queue

Following are the different types of queues:

Simple Queue

It’s the basic queue in which insertion happens at the tail-end, and deletion happens at the front end of the queue.

Circular Queue

In a circular node, the first node is connected to the last node, thus making it a circle. It follows the FIFO principle. We also know it as ‘Ring Buffer’ as all ends are connected to another end.

These are a few primary use cases for a circular Queue –

  • Memory Management
  • CPU scheduling

Priority Queue

It is a unique type of queue in which the nodes are organized on a priority basis.

The least prior element would be the first one to be removed from the queue. Insertion happens in the order of arrival of the nodes.

A few primary use cases for Priority Queue are –

  • Dijkstra’s shortest path algorithm
  • Prim’s algorithm
  • Data Compression Techniques

(Learn more about priority queue)

Double-ended Queue

As the name suggests, this type of queue allows both insertion and deletion at both ends of the queue.

In other words, we can add elements at both rear and front ends, and similarly remove them from both ends.

A case where a double-ended queue (Deque) is used is the work-stealing algorithms

Difference between Stack and Queue

Despite both being linear data structures and abstract data types, a stack and a queue have major differences. Let’s have a look-

Stack
Queue
Elements are inserted and removed at the same end.Elements are inserted and removed from different ends.
Stack follows the Last In First Out principle.Queue follows the First In First Out principle.
Stack uses only one pointer which points to the top of the stack.Queue follows two pointers- Front and Rear.
A stack can be seen as a vertical structure.A queue can be seen as a horizontal structure.
Basic operations in a stack are – Push and PopBasic operations in a queue are- Enqueue and Dequeue
A collection of books over each other is the perfect example of a stack.People standing in a line outside the ticket counter is the perfect example of a queue.
Stack vs Queue

Applications of Queue Data Structure

As a queue data structure is an ordered list and yet open at both ends, it has multifold applications in the real world. Let’s look at a few of them –

Job scheduling

The most important application of a queue is CPU scheduling. The tasks that a computer executes are scheduled in the processor/CPU using a queue. That’s how the computer executes these tasks one by one based on the order.

Other single shared resources such as disks and printers also use queues as waiting lists.

Asynchronous transfer of data

Queues are used in asynchronous data transfer. Asynchronous here means the process where data is not being transferred at the same rate between two processes. For example – IO buffers, pipes, file IO, etc.

Traffic System 

In a computer-controlled traffic system, we use circular queues to switch on the different lights one by one periodically (at regular time intervals).

We also use queues in the handling of website traffic and real-time system interrupts.

In Networks:

  • In routers
  • Queues in mail scheduling

We hope you now have a better understanding of queue data structure.

If you want to learn full-stack web development and get job offers from top tech companies, check out these part-time and full-time web development courses. We provide training on the latest industry tools and technologies at zero upfront fee and craft students from any educational background into professional full-stack developers.

Take action and crush your goals.