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

Queue in Data Structures

Queue in Data Structures is a type of non-primitive, linear, and dynamic data structure. It works according to the FIFO principle. This principle is widely used in various applications of Queue in data structures, such as task scheduling, buffering, and handling asynchronous data. There are different types of queues in data structures, including simple queues, circular queues, and priority queues. To implement queues in data structures, arrays, and linked lists are commonly used, with array queues in data structures being one of the fundamental implementations.

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, FIFOor 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, and a 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 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()The 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

There are 4 types of queues in data structures:

1. Simple or Linear Queue

• As we mentioned above, a Simple queue follows the First-In-First-Out (FIFO) principle.
• In this, Items are taken out of the front and put in the back.
• It is necessary to remove outdated elements in order to add new ones.

2. Circular Queue

• A circular queue is similar to a simple queue, but the last element is connected to the first element which creates a circular structure.
• This allows for efficient use of memory.
• It is also known as a Ring Buffer.

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.

4. Dequeue (Double-Ended Queue)

• In this, the elements can be added or removed from both endsfront and rear of the queue.
• Dequeue allows insertion and deletion at both front and rear ends.
• It provides flexibility in managing data with operations from both ends.

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>
#include <climits>
using namespace std;

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

public:
    Queue(unsigned capacity);
    ~Queue();
    bool isFull();
    bool isEmpty();
    void enqueue(int item);
    int dequeue();
    int getFront();
    int getRear();
};

Queue::Queue(unsigned capacity) {
    this->capacity = capacity;
    this->front = this->size = 0;
    this->rear = capacity - 1;
    this->array = new int[capacity];
}

Queue::~Queue() {
    delete[] array;
}

bool Queue::isFull() {
    return (this->size == this->capacity);
}

bool Queue::isEmpty() {
    return (this->size == 0);
}

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

int Queue::dequeue() {
    if (isEmpty())
        return INT_MIN;
    int item = this->array[this->front];
    this->front = (this->front + 1) % this->capacity;
    this->size = this->size - 1;
    return item;
}

int Queue::getFront() {
    if (isEmpty())
        return INT_MIN;
    return this->array[this->front];
}

int Queue::getRear() {
    if (isEmpty())
        return INT_MIN;
    return this->array[this->rear];
}

int 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
    cout << queue.dequeue() << " dequeued from queue\n";
    cout << queue.dequeue() << " dequeued from queue\n";
    cout << queue.dequeue() << " dequeued from queue\n";

    // Display the front and rear elements of the queue
    cout << "Front item is " << queue.getFront() << endl;
    cout << "Rear item is " << queue.getRear() << endl;

    return 0;
}
    

  
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Define the Queue structure
typedef struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
} Queue;

// Function to create a queue of given capacity.
// It initializes size of queue as 0
Queue* createQueue(unsigned capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

// Queue is full when size becomes equal to the capacity
int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

// Queue is empty when size is 0
int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

// Function to add an item to the queue.
// It changes rear and size
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;
    printf("%d enqueued to queue\n", item);
}

// Function to remove an item from queue.
// It changes front and size
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 front of queue
int getFront(Queue* queue) {
    if (isEmpty(queue)) {
        return INT_MIN;
    }
    return queue->array[queue->front];
}

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

// Main function to test the above functions
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
    printf("%d dequeued from queue\n", dequeue(queue));
    printf("%d dequeued from queue\n", dequeue(queue));
    printf("%d dequeued from queue\n", dequeue(queue));

    // Display the front and rear elements of the queue
    printf("Front item is %d\n", getFront(queue));
    printf("Rear item is %d\n", getRear(queue));

    // Free allocated memory
    free(queue->array);
    free(queue);

    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 Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class Queue {
    constructor() {
        this.front = this.rear = null;
        this.size = 0;
    }

    enqueue(data) {
        const newNode = new Node(data);
        if (!this.rear) {
            this.front = this.rear = newNode;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
        }
        this.size++;
    }

    dequeue() {
        if (!this.front) {
            console.log("Queue is empty");
            return;
        }
        const temp = this.front;
        this.front = this.front.next;
        if (!this.front) {
            this.rear = null;
        }
        this.size--;
        return temp.data;
    }

    peek() {
        return this.front ? this.front.data : null;
    }

    isEmpty() {
        return this.size === 0;
    }
}

// Example usage
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.peek()); // 20

    

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

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

    def enqueue(self, data):
        new_node = Node(data)
        if not self.rear:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1

    def dequeue(self):
        if not self.front:
            print("Queue is empty")
            return None
        temp = self.front
        self.front = self.front.next
        if not self.front:
            self.rear = None
        self.size -= 1
        return temp.data

    def peek(self):
        return self.front.data if self.front else None

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

# Example usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
print(queue.dequeue())  # 10
print(queue.peek())  # 20
    

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

class Queue {
private:
    Node* front;
    Node* rear;
    int size;

public:
    Queue() : front(nullptr), rear(nullptr), size(0) {}

    void enqueue(int data) {
        Node* newNode = new Node(data);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
        size++;
    }

    int dequeue() {
        if (front == nullptr) {
            cout << "Queue is empty" << endl;
            return -1;
        }
        Node* temp = front;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        int data = temp->data;
        delete temp;
        size--;
        return data;
    }

    int peek() {
        return (front != nullptr) ? front->data : -1;
    }

    bool isEmpty() {
        return front == nullptr;
    }

    ~Queue() {
        while (!isEmpty()) {
            dequeue();
        }
    }
};

// Example usage
int main() {
    Queue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    cout << queue.dequeue() << " dequeued from queue" << endl;
    cout << "Front item is " << queue.peek() << endl;
    return 0;
}

    

  
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

void enqueue(Queue* queue, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}

int dequeue(Queue* queue) {
    if (queue->front == NULL) {
        printf("Queue is empty\n");
        return -1;
    }
    Node* temp = queue->front;
    queue->front = queue->front->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    int data = temp->data;
    free(temp);
    return data;
}

int peek(Queue* queue) {
    return (queue->front != NULL) ? queue->front->data : -1;
}

int isEmpty(Queue* queue) {
    return queue->front == NULL;
}

int main() {
    Queue* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    printf("%d dequeued from queue\n", dequeue(queue));
    printf("Front item is %d\n", peek(queue));
    return 0;
}
    

Output

 10
 20  

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.