What Is Queue Data Structure Used For?

Queue is a fundamental data structure used in computer science and programming. It is an ordered collection of elements where an element is inserted at one end, called the rear, and removed from the other end, called the front.

This mechanism follows the principle of First-In-First-Out (FIFO). In simpler terms, the element that enters the queue first will be the first one to leave.

Why Use Queue Data Structure?

Queues are versatile data structures that find applications in various domains. Let’s explore some of their common uses:

1. Job Scheduling

In operating systems, queues are extensively used for scheduling tasks or processes. Each process is added to a queue and executed in the order they were received. This ensures fairness and avoids starvation of processes.

2. Print Spooling

In printer management systems, queues are used to handle multiple print requests efficiently. The print spooler organizes incoming print jobs into a queue and processes them sequentially.

3. Breadth-First Search (BFS) Algorithm

BFS is a graph traversal algorithm that explores all vertices of a graph in breadth-first order starting from a given source vertex. A queue data structure is used to maintain the order of traversal by storing adjacent vertices.

4. Event Handling

In graphical user interfaces (GUI) or event-driven programming, queues are employed to manage events such as mouse clicks or keyboard inputs. Events are placed in a queue and processed one by one as they occur.

Implementing Queue Data Structure

To implement a queue data structure, you can use arrays or linked lists in programming languages like C++, Java, Python, etc.

1. Array Implementation

In the array implementation of a queue, a fixed-size array is used to store elements. Two pointers, ‘front’ and ‘rear’, are maintained to keep track of the queue’s boundaries. When an element is enqueued, it is added at the rear position, and when an element is dequeued, it is removed from the front position.

Here’s a simple example of enqueue and dequeue operations on a queue implemented using an array:

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int queue[MAX_SIZE];
int front = -1;
int rear = -1;

void enqueue(int element) {
    if (rear == MAX_SIZE - 1) {
        cout << "Queue Overflow!";
        return;
    }
    if (front == -1)
        front = 0;
    rear++;
    queue[rear] = element;
}

void dequeue() {
    if (front == -1 || front > rear) {
        cout << "Queue Underflow!";
        return;
    }
    cout << "Dequeued: " << queue[front] << endl;
    front++;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    
    dequeue();
    
    return 0;
}

2. Linked List Implementation

In the linked list implementation of a queue, each element is stored as a node with a pointer to the next node. The 'front' pointer points to the first element, and the 'rear' pointer points to the last element.

Here's an example of enqueue and dequeue operations on a queue implemented using linked lists:

class Node {
    public:
        int data;
        Node* next;
};

class Queue {
    private:
        Node* front;
        Node* rear;
    
    public:
        Queue() {
            front = nullptr;
            rear = nullptr;
        }
        
        void enqueue(int element) {
            Node* newNode = new Node();
            newNode->data = element;
            newNode->next = nullptr;
            
            if (rear == nullptr) {
                front = rear = newNode;
                return;
            }
            
            rear->next = newNode;
            rear = newNode;
        }
        
        void dequeue() {
            if (front == nullptr) {
                cout << "Queue Underflow!";
                return;
            }
            
            Node* temp = front;
            
            cout << "Dequeued: " << temp->data << endl;

            front = front->next;

            if (front == nullptr)
                rear = nullptr;

            delete(temp);
        }
};

int main() {
    Queue queue;

    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);

    queue.dequeue();
    
    return 0;
}

Conclusion

Queues are an essential data structure used in various fields of computer science and programming. They provide an efficient way to manage elements in a sequential manner, following the FIFO principle. Whether it's job scheduling, print spooling, graph algorithms, or event handling, queues play a crucial role in many applications.

By understanding the concept and implementation of queues, you can enhance your problem-solving skills and develop more efficient algorithms.