Operations of Queue in Data Structure: Implementation & Applications

Introduction to Queue Data Structure

Queue is used to store and manage elements in a particular order. It operates on the First-In-First-Out (FIFO) principle, the element pushed first is to be popped from the queue. In this article, we will explore the various operations of a queue, how to implement queues, and some real-world applications of queues in data structures.

What are the Operations of a Queue?

Some of the basic operations of a queue are:

• Enqueue(): Adding an element to the end of the queue.
• Dequeue(): Removing an element from the front of the queue, adhering to the FIFO (First-In-First-Out) order.
• Peek(): This operation returns the element at the front of the queue without popping it.
• isEmpty: Checks whether the queue has any elements or if it is empty.
• isFull(): This method is used to check whether the queue is full.
• Size: This operation returns the number of elements currently in the queue.

Queue Implementation Techniques

There are various ways to implement queues, including:

• Implementation of Queue using Array
• Implementation of Queue using LinkedList
• Implementation of Queue using Pointers
• Implementation of Queue using Two Stacks
• Implementation of Queue using Structures

1. Implementation of Queue using Array

#include <iostream>
using namespace std;

#define MAX 5
class Queue {
    int arr[MAX];
    int front, rear;

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return front == -1;
    }

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

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is full!" << endl;
        } else {
            if (front == -1)
                front = 0;
            rear++;
            arr[rear] = value;
            cout << "Enqueued: " << value << endl;
        }
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            cout << "Dequeued: " << arr[front] << endl;
            front++;
            if (front > rear) {
                front = rear = -1;
            }
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            cout << "Queue elements: ";
            for (int i = front; i <= rear; i++) {
                cout << arr[i] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(5);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}

Output:

Enqueued: 1
Enqueued: 2
Enqueued: 5
Queue elements: 1 2 5
Dequeued: 1
Queue elements: 2 5

2. Implementation of Queue Using LinkedList

#include <iostream>
using namespace std;

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

class Queue {
    Node* front;
    Node* rear;

public:
    Queue() {
        front = rear = nullptr;
    }

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

    void enqueue(int value) {
        Node* temp = new Node();
        temp->data = value;
        temp->next = nullptr;
        if (isEmpty()) {
            front = rear = temp;
        } else {
            rear->next = temp;
            rear = temp;
        }
        cout << "Enqueued: " << value << endl;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;
            delete temp;
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            Node* temp = front;
            cout << "Queue elements: ";
            while (temp != nullptr) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(5);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}

Output:

Enqueued: 1
Enqueued: 2
Enqueued: 5
Queue elements: 1 2 5
Dequeued: 1
Queue elements: 2 5

3. Implementation Using Pointers

#include <iostream>
using namespace std;

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

class Queue {
    Node* front;
    Node* rear;

public:
    Queue() {
        front = rear = nullptr;
    }

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

    void enqueue(int value) {
        Node* temp = new Node();
        temp->data = value;
        temp->next = nullptr;
        if (isEmpty()) {
            front = rear = temp;
        } else {
            rear->next = temp;
            rear = temp;
        }
        cout << "Enqueued: " << value << endl;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            Node* temp = front;
            cout << "Dequeued: " << front->data << endl;
            front = front->next;
            delete temp;
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
        } else {
            Node* temp = front;
            cout << "Queue elements: ";
            while (temp != nullptr) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(5);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}

Output:

Enqueued: 1
Enqueued: 2
Enqueued: 5
Queue elements: 1 2 5
Dequeued: 1
Queue elements: 2 5

4. Implementation of Queue Using Two Stacks

#include <iostream>
#include <stack>
using namespace std;

class Queue {
    stack<int> s1, s2;

public:
    void enqueue(int value) {
        s1.push(value);
        cout << "Enqueued: " << value << endl;
    }

    void dequeue() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty!" << endl;
        } else {
            if (s2.empty()) {
                while (!s1.empty()) {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            cout << "Dequeued: " << s2.top() << endl;
            s2.pop();
        }
    }

    void display() {
        if (s1.empty() && s2.empty()) {
            cout << "Queue is empty!" << endl;
        } else {
            cout << "Queue elements: ";
            if (!s2.empty()) {
                stack<int> temp = s2;
                while (!temp.empty()) {
                    cout << temp.top() << " ";
                    temp.pop();
                }
            }
            stack<int> temp = s1;
            while (!temp.empty()) {
                cout << temp.top() << " ";
                temp.pop();
            }
            cout << endl;
        }
    }
};

int main() {
    Queue q;
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(5);
    q.display();
    q.dequeue();
    q.display();
    return 0;
}

Output:

Enqueued: 1
Enqueued: 2
Enqueued: 5
Queue elements: 5 2 1
Dequeued: 1
Queue elements: 2 5

5. Implementation of Queue Using Structures

#include <iostream>
using namespace std;

struct Queue {
    int front, rear, size;
    int capacity;
    int* array;

    Queue(int cap) {
        capacity = cap;
        front = size = 0;
        rear = capacity - 1;
        array = new int[capacity];
    }

    bool isFull() {
        return (size == capacity);
    }

    bool isEmpty() {
        return (size == 0);
    }

    void enqueue(int item) {
        if (isFull()) {
            cout << "Queue is full! Cannot enqueue." << endl;
            return;
        }
        rear = (rear + 1) % capacity;
        array[rear] = item;
        size++;
        cout << "Enqueued: " << item << endl;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty! Cannot dequeue." << endl;
            return -1;
        }
        int item = array[front];
        front = (front + 1) % capacity;
        size--;
        return item;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return array[front];
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return;
        }

        cout << "Queue: ";
        for (int i = 0; i < size; i++) {
            cout << array[(front + i) % capacity] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q(5);

    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(5);

    q.display();

    cout << "Front element is: " << q.peek() << endl;
    return 0;
}

Output:

Enqueued: 1
Enqueued: 2
Enqueued: 5
Queue: 1 2 5
Front element is: 1

Applications of Queue in Data Structures

Here are the applications of queues in data structures:

• Task Scheduling: Queues are commonly used to manage the scheduling of tasks, ensuring they are executed in a particular sequence based on their priority or the order of their arrival.
• Message Buffering: Queues temporarily store messages, allowing for efficient transmission.
• Resource Management: Queues play an essential role in allocating resources, such as CPU time, and printers, by managing the sequence in which resources are granted to different tasks or requests.
• Network Protocols: Network protocols like TCP and UDP employ queues to handle packets as they are transmitted over a network, ensuring they arrive in the correct sequence and within the appropriate rate.
• Breadth-First Search Algorithm: The breadth-first search (BFS) algorithm uses a queue to explore a graph level by level. Starting from an initial node, it adds neighboring nodes to the queue and processes them sequentially, ensuring an organized search process.

Conclusion

In conclusion, queues in data structures enable efficient management of elements in various real-world applications. The basic operations of a queue, including enqueue, dequeue, peek, and isEmpty, provide a simple way to handle tasks in a first-in, first-out (FIFO) manner. These operations are essential for ensuring the orderly processing of tasks and resource allocation in systems. By maintaining a well-structured queue, systems can achieve efficiency, and predictability in task execution, making queues indispensable in both computing and everyday applications.

Frequently Asked Questions

What is a circular queue?

A circular queue is a type of queue where the rear and front pointers circularly wrap around the way, effectively using all the available space without wasting it.

What is the difference between a queue and a stack?

A queue follows the FIFO principle, meaning the first element added is the first one removed. A stack, on the other hand, follows the LIFO principle, where the last element added is the first one removed.