Queue in Data Structures - Types & Algorithm (With Example)

Queue in Data Structures: An Overview

Queue in Data Structures is a type of non-primitive, linear, and dynamic data structure. It works according to the FIFO principle. In this DSA tutorial, we will see queue data structure in detail i.e. its features, working, implementation, etc. To further enhance your understanding and application of queue concepts, consider enrolling in the Dsa Course, where you can gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is a Queue in Data Structures?

A queue is an ordered list in which insertion is done at one end called REAR and deletion at another end called FRONT. The first inserted element is available first for the operations to be performed and is the first one to be deleted. Hence, it is known as First In First Out, FIFO, or Last In Last Out, LILO.

Real-life examples of queues are a ticket queue outside a ticket counter, students standing in a queue for assembly prayer on the school grounds, queue of persons standing outside the booking counter of a theatre. In all these examples, the person standing first in the line is the first one for access.

Representation of a Queue in Data Structures

We know that a queue can be accessed from both sides i.e. at the front for deletion and back or rear for insertion.

Before moving forward, make sure that you are thorough with the concept of pointers. If not refer to the Pointers in C++ tutorial and come back.

Standard Operations on Queue in Data Structures

1. Insertion: enqueue()

The enqueue() operation is used to insert an element at the back of a queue or to the end of a queue or the rear end of the queue.

Algorithm

Step 1: START
Step 2: Check if the queue is full.
Step 3: If the queue is full, produce an overflow error and exit.
Step 4: If the queue is not full, increment the rear pointer to point to the next space.
Step 5: Add a data element to the queue location, where the rear is pointing.
Step 6: End the process and exit.

2. Deletion: dequeue()

The dequeue() operation is used to remove and return the element from the front of a queue.

Algorithm

Step 1: START
Step 2: Check if the queue is empty.
Step 3: If the queue is empty, print underflow and exit.
Step 4: If the queue is not empty, access the data where the front is pointing.
Step 5: Increment the front pointer to point to the next available data element.
Step 6: Set the front and rear as -1 for the last element.
Step 7: End the process and exit.

3. peek()

The peek() operation returns the value at the front end of the queue without removing it.

Algorithm

Step 1: START
Step 2: Check if the Queue is empty.
Step 3: Return the element at the front of the queue
Step 4: End the process and exit.

4. isFull()

The isFull() operation is used to determine if the queue is full or not. A queue is said to be full if it has reached its maximum capacity and there is no more space to add new elements to it.

Algorithm

Step 1: START
Step 2: If the count of queue elements equals the queue size, return true.
Step 3: Otherwise, return false
Step 4: End the process and exit.

5. isEmpty()

The isEmpty() operation is used to check if the queue is empty or not. It returns a boolean value, true when the queue is empty, otherwise false.

Algorithm

Step 1: START
Step 2: If the count of queue elements equals zero, return true.
Step 3: Otherwise, return false
Step 4: End the process and exit.

Read More - DSA Interview Questions and Answers

Working of Queue in Data Structures

Queue operations work as follows:

• Two pointers are there denoting two ends, FRONT and REAR.
• FRONT tracks the first element of the queue.
• REAR tracks the last element of the queue.
• Initially, set the value of FRONT and REAR to -1.
• Afterward, follow the above-given algorithms for the basic operations.

Types of Queues in Data Structures

1. Simple Queue/Linear Queue: Here, elements are inserted from one end i.e. rear end, and removed from the other end i.e. front. It follows the FIFO (First In First Out) order.
2. Circular Queue: It is similar to a simple queue, but the last element is connected to the first element, creating a circular structure. This allows for efficient use of memory.
3. Priority Queue: It is a special type of queue in which each element has a priority assigned to it. The element with the highest priority is removed first. This is useful in situations where certain elements need to be processed before others.

   Read More: Priority Queue in Data Structures

4. Dequeue (Double-Ended Queue): In this, the elements can be added or removed from both ends, front and rear of the queue.

Implementation of Queue in Different Programming Languages

There are three ways to implement Queues in Data Structures, using a 1D Array, a Single Linked List, and vectors. We will look at array and linked list implementation in detail.

1. Implementation of Queue Using a 1D Array

It is the simplest implementation of a Queue in Data Structures. We usually use arrays to implement queues in Java and C++. In the case of Python, we use lists.

The time complexity of all the operations is the same i.e. O(1) here.

class Queue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.front = self.size = 0
        self.rear = capacity - 1
        self.array = [0] * self.capacity

    def is_full(self):
        return self.size == self.capacity

    def is_empty(self):
        return self.size == 0

    def enqueue(self, item):
        if self.is_full():
            return
        self.rear = (self.rear + 1) % self.capacity
        self.array[self.rear] = item
        self.size += 1
        print(f"{item} enqueued to queue")

    def dequeue(self):
        if self.is_empty():
            return float('-inf')
        item = self.array[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

    def get_front(self):
        return self.array[self.front] if not self.is_empty() else float('-inf')

    def get_rear(self):
        return self.array[self.rear] if not self.is_empty() else float('-inf')

if __name__ == "__main__":
    # Create a queue with a capacity of 100
    queue = Queue(100)

    # Enqueue elements into the queue
    queue.enqueue(10)
    queue.enqueue(15)
    queue.enqueue(20)
    queue.enqueue(25)
    queue.enqueue(30)

    # Dequeue elements from the queue
    print(f"{queue.dequeue()} dequeued from queue")
    print(f"{queue.dequeue()} dequeued from queue")
    print(f"{queue.dequeue()} dequeued from queue")

    # Display the front and rear elements of the queue
    print("Front item is", queue.get_front())
    print("Rear item is", queue.get_rear())
    

public class Queue {
    int front, rear, size;
    int capacity;
    int[] array;

    // Function to create a queue of given capacity
    public Queue(int capacity) {
        this.capacity = capacity;
        this.front = this.size = 0;
        this.rear = capacity - 1;
        this.array = new int[this.capacity];
    }

    // Function to check if the queue is full
    boolean isFull() {
        return (this.size == this.capacity);
    }

    // Function to check if the queue is empty
    boolean isEmpty() {
        return (this.size == 0);
    }

    // Function to enqueue an item
    void enqueue(int item) {
        if (isFull())
            return;
        this.rear = (this.rear + 1) % this.capacity;
        this.array[this.rear] = item;
        this.size = this.size + 1;
        System.out.println(item + " enqueued to queue");
    }

    // Function to dequeue an item
    int dequeue() {
        if (isEmpty())
            return Integer.MIN_VALUE;
        int item = this.array[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size = this.size - 1;
        return item;
    }

    // Function to get the front item of the queue
    int front() {
        if (isEmpty())
            return Integer.MIN_VALUE;
        return this.array[this.front];
    }

    // Function to get the rear item of the queue
    int rear() {
        if (isEmpty())
            return Integer.MIN_VALUE;
        return this.array[this.rear];
    }

    public static void main(String[] args) {
        // Create a queue with a capacity of 100
        Queue queue = new Queue(100);

        // Enqueue elements into the queue
        queue.enqueue(10);
        queue.enqueue(15);
        queue.enqueue(20);
        queue.enqueue(25);
        queue.enqueue(30);

        // Dequeue elements from the queue
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println(queue.dequeue() + " dequeued from queue");
        System.out.println(queue.dequeue() + " dequeued from queue");

        // Display the front and rear elements of the queue
        System.out.println("Front item is " + queue.front());
        System.out.println("Rear item is " + queue.rear());
    }
}
    

#include <iostream>
using namespace std;

class Queue {
public:
    int front, rear, size;
    unsigned capacity;
    int* array;
};

// Function to create a queue of given capacity
Queue* createQueue(unsigned capacity) {
    Queue* queue = new Queue();
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = new int[queue->capacity];
    return queue;
}

// Function to check if the queue is full
int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

// Function to check if the queue is empty
int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

// Function to enqueue an item
void enqueue(Queue* queue, int item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    cout << item << " enqueued to queue\n";
}

// Function to dequeue an item
int dequeue(Queue* queue) {
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function to get the front item of the queue
int front(Queue* queue) {
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}

// Function to get the rear item of the queue
int rear(Queue* queue) {
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}

int main() {
        // Create a queue with a capacity of 100
    Queue* queue = createQueue(100);

    // Enqueue elements into the queue
    enqueue(queue, 10);
    enqueue(queue, 15);
    enqueue(queue, 20);
    enqueue(queue, 25);
    enqueue(queue, 30);
    
    // Dequeue elements from the queue
    cout << dequeue(queue) << " dequeued from queue\n";
    cout << dequeue(queue) << " dequeued from queue\n";
    cout << dequeue(queue) << " dequeued from queue\n";
    
    // Display the front and rear elements of the queue
    cout << "Front item is " << front(queue) << endl;
    cout << "Rear item is " << rear(queue) << endl;

    return 0;
}
    

Output

10 enqueued to queue
15 enqueued to queue
20 enqueued to queue
25 enqueued to queue
30 enqueued to queue
10 dequeued from queue
15 dequeued from queue
20 dequeued from queue
Front item is 25
Rear item is 30   

Advantages of Array Implementation

• Easy to implement.
• A large amount of data can be managed efficiently with ease.
• Operations such as insertion and deletion can be performed with ease as a queue follows the FIFO rule.

Limitations of Array Implementation

• The maximum size of the queue must be defined beforehand.
• The size of the array cannot be changed during the run time because it is not dynamic.
• If the queue has a large number of enqueue and dequeue operations, at some point (in case of linear increment of front and rear indexes) it may happen that we may not be able to insert elements in the queue even if the queue is empty.

2. Implementation of a Queue Using a Linked List

We discussed the disadvantages of array implementation above. Due to this, the array cannot be used for large-scale applications of queues. One of the solutions to overcome this limitation is linked list implementation of queues in data structures

The storage requirement of the linked representation of a queue with n elements is O(n). The time complexity of all the operations is the same i.e. O(1) here.

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory. There are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.

Example of Queue Implementation in Different Languages Using a Linked List

class QNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = self.rear = None

    def enQueue(self, x):
        temp = QNode(x)

        if self.rear is None:
            self.front = self.rear = temp
            return

        self.rear.next = temp
        self.rear = temp

    def deQueue(self):
        if self.front is None:
            return

        temp = self.front
        self.front = self.front.next

        if self.front is None:
            self.rear = None

        del temp

if __name__ == "__main__":
    q = Queue()
    q.enQueue(10)
    q.enQueue(15)
    q.enQueue(20)
    q.enQueue(25)
    q.enQueue(30)

    q.deQueue()
    q.deQueue()
    q.deQueue()

    q.enQueue(35)
    q.enQueue(40)
    q.enQueue(45)
    q.deQueue()

    print("Front element is:", q.front.data if q.front is not None else -1)
    print("Rear element is:", q.rear.data if q.rear is not None else -1)
    

class QNode {
    int data;
    QNode next;

    public QNode(int d) {
        data = d;
        next = null;
    }
}

class Queue {
    QNode front, rear;

    public Queue() {
        front = rear = null;
    }

    void enQueue(int x) {
        QNode temp = new QNode(x);

        if (rear == null) {
            front = rear = temp;
            return;
        }

        rear.next = temp;
        rear = temp;
    }

    void deQueue() {
        if (front == null)
            return;

        QNode temp = front;
        front = front.next;

        if (front == null)
            rear = null;

        // free up the memory
        temp = null;
    }
}

class Main {
    public static void main(String[] args) {
        Queue q = new Queue();
        q.enQueue(10);
        q.enQueue(15);
        q.enQueue(20);
        q.enQueue(25);
        q.enQueue(30);

        q.deQueue();
        q.deQueue();
        q.deQueue();

        q.enQueue(35);
        q.enQueue(40);
        q.enQueue(45);
        q.deQueue();

        System.out.println("Front element is: " + ((q.front != null) ? q.front.data : -1));
        System.out.println("Rear element is : " + ((q.rear != null) ? q.rear.data : -1));
    }
}
    

#include <iostream>
using namespace std;

struct QNode {
    int data;
    QNode* next;
    QNode(int d)
    {
        data = d;
        next = NULL;
    }
};

struct Queue {
    QNode* front, * rear;
    Queue() { front = rear = NULL; }

    void enQueue(int x)
    {
        QNode* temp = new QNode(x);

        if (rear == NULL) {
            front = rear = temp;
            return;
        }

        rear->next = temp;
        rear = temp;
    }

    void deQueue()
    {
        if (front == NULL)
            return;

        QNode* temp = front;
        front = front->next;

        if (front == NULL)
            rear = NULL;

        delete (temp);
    }
};

int main()
{
    Queue q;
    q.enQueue(10);
    q.enQueue(15);
    q.enQueue(20);
    q.enQueue(25);
    q.enQueue(30);

    q.deQueue();
    q.deQueue();
    q.deQueue();

    q.enQueue(35);
    q.enQueue(40);
    q.enQueue(45);
    q.deQueue();

    cout << "Front element is: " << ((q.front != NULL) ? (q.front)->data : -1) << endl;
    cout << "Rear element is : " << ((q.rear != NULL) ? (q.rear)->data : -1);

    return 0;
}
    

Output

Front element is: 30
Rear element is : 45   

If you are facing any difficulty in understanding the linked list implementation of the queue in data structures refer to the previous tutorial, Linked Lists in Data Structures.

Complexity Analysis of Queue Operations

Stack Vs Queue

Applications of Queue

1. Multi-programming: It is essential to organize the multiple programs running in the main memory so they are organized as queues.
2. Network: In a network, a queue is used in devices such as a router or a switch.
3. Job Scheduling: The computer has a task to execute a particular number of jobs that are scheduled to be executed one after another. These jobs are assigned to the processor one by one which is organized using a queue. E.g. CPU scheduling, Disk Scheduling
4. Synchronization: The queue is used for synchronization when data is transferred asynchronously between two processes. E.g. IO Buffers, pipes, file IO, etc
5. Interrupts: Handling of interrupts in real-time systems.
6. Shared resources: Queues are used as waiting lists for a single shared resource.
7. Operation on data structures: Certain operations like BFS (Breadth First Search), and tree traversal use Queue. The sequence of traversal of inputs is set using queues.

Advantages of Queue

1. Efficient data processing: A queue can be used to efficiently process data in the order it was received. For example, in a computer system, a queue can be used to schedule processes in the order they were submitted.
2. Resource management: A queue can be used to manage resources that are shared among multiple processes or threads. For example, a printer can use a queue to manage print jobs.
3. Buffering: A queue can be used to buffer incoming data so that it can be processed at a later time. For example, a network device can use a queue to buffer incoming data packets before forwarding them to their destination.
4. Memory management: A queue can be used to manage memory by allocating and deallocating memory blocks in sequential order.

Disadvantages of Queue

1. Limited flexibility: Queues follow a strict FIFO order, meaning the element that enters first is the first one to be removed. This lack of flexibility can be a disadvantage in some use cases where other priorities or requirements must be considered.
2. No random access: Unlike arrays or linked lists, queues do not allow random access to the elements. The user can only access the first element in the queue, and to access any other element, they need to remove all the elements that come before it. This can be a disadvantage when the user needs to access an element in the middle of the queue.
3. Overhead: Queues require extra overhead to maintain the order of elements. Whenever an element is added or removed from the queue, all the other elements must be shifted accordingly, which can be time-consuming for large queues.
4. Limited size: In some implementations, queues have a limited size, which can be a disadvantage when dealing with large amounts of data. Once the queue reaches its maximum size, it can no longer accept new elements.
5. No search operation: Queues do not provide a search operation. The user cannot search for a specific element in the queue they can only remove the elements in the order they were added and hope to find the element they are looking for.

Summary

So, here we saw every aspect of a queue in data structures. You might have got at least some idea regarding queues and their applications. I know it's quite difficult to understand the whole topic in a single go. Therefore, refer to it again and again till you get thorough with the queue in data structures. To test your knowledge of queue, enroll in our Best Data Structures And Algorithms Course.