by Jasleen Chhabra | Updated on 24 August 2024

Queues are a fundamental data structure in computer science, widely used for handling tasks in various applications. They operate on a First In, First Out (FIFO) principle, meaning the first element added to the queue will be the first one to be removed. This principle is akin to a real-world queue, such as a line of people waiting for a service, where the person who arrives first is served first.

What is a Queue?

A queue is an abstract data type that manages a collection of elements, providing two main operations:

1. Enqueue: Adds an element to the end of the queue.
2. Dequeue: Removes an element from the front of the queue.

These operations ensure that the oldest elements are removed first, maintaining the FIFO order.

Types of Queues

Queues come in various types, each suited to different scenarios:

1. Simple Queue: The basic queue structure where elements are added at the rear and removed from the front.
2. Circular Queue: The last position is connected back to the first position to make a circle. It overcomes the limitation of the simple queue, where the space is reused.
3. Priority Queue: Each element is associated with a priority, and elements are dequeued based on their priority rather than their order in the queue.
4. Double-ended Queue (Deque): Elements can be added or removed from both the front and the rear of the queue.

Applications of Queues

Queues are versatile and can be found in various applications, including:

1. Operating Systems: Managing processes in a multitasking system.
2. Networking: Handling data packets in routers and switches.
3. Printing Jobs: Managing print tasks in a printer's queue.
4. Breadth-First Search (BFS): Traversing graphs and trees.

Basic Operations on Queues

1. Enqueue: Adding an element to the end of the queue.
2. Dequeue: Removing an element from the front of the queue.
3. Peek/Front: Getting the element at the front of the queue without removing it.
4. IsEmpty: Checking if the queue is empty.
5. IsFull: Checking if the queue is full (applicable for fixed-size queues).

Algorithm for Enqueue Operation

Let's look at the step-by-step algorithm for adding an element to the queue (Enqueue):

1. Start
2. Check for Overflow: If the queue is full, print "Queue Overflow" and exit the operation.
3. Increment Rear: Move the rear index to the next position.
4. Add Element: Insert the new element at the rear position.
5. End

Algorithm for Dequeue Operation

Similarly, here’s the algorithm for removing an element from the queue (Dequeue):

1. Start
2. Check for Underflow: If the queue is empty, print "Queue Underflow" and exit the operation.
3. Retrieve Element: Get the element at the front position.
4. Increment Front: Move the front index to the next position.
5. End

Pseudocode for Queue Operations

Enqueue Operation:

Algorithm Enqueue(queue, element, rear, size):
    if rear == size - 1:
        print "Queue Overflow"
        return
    else:
        rear = rear + 1
        queue[rear] = element

Dequeue Operation:

Algorithm Dequeue(queue, front, rear):
    if front > rear:
        print "Queue Underflow"
        return None
    else:
        element = queue[front]
        front = front + 1
        return element

C++ Implementation of Queue

Here’s a simple implementation of a queue in C++ using an array:

#include <iostream>
#define MAX 1000

class Queue {
    int front, rear;
    int arr[MAX]; // Maximum size of Queue

public:
    Queue() { front = 0; rear = -1; }
    bool enqueue(int x);
    int dequeue();
    bool isEmpty();
    bool isFull();
    void printQueue();
};

bool Queue::isEmpty() {
    return (front > rear);
}

bool Queue::isFull() {
    return (rear == MAX - 1);
}

bool Queue::enqueue(int x) {
    if (isFull()) {
        std::cout << "Queue Overflow" << std::endl;
        return false;
    } else {
        arr[++rear] = x;
        std::cout << x << " added to queue" << std::endl;
        return true;
    }
}

int Queue::dequeue() {
    if (isEmpty()) {
        std::cout << "Queue Underflow" << std::endl;
        return -1;
    } else {
        return arr[front++];
    }
}

void Queue::printQueue() {
    for (int i = front; i <= rear; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    Queue queue;
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    queue.printQueue();

    std::cout << "Dequeued from queue: " << queue.dequeue() << std::endl;
    queue.printQueue();

    return 0;
}

Conclusion

Queues are a powerful data structure that efficiently handles tasks in various applications by maintaining a FIFO order. Understanding and implementing queue operations like enqueue and dequeue are fundamental to utilizing queues effectively. With their diverse types and applications, queues play a critical role in data structure management and algorithm design.

---