A queue is a linear data structure that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed, just like people waiting in a line (the first person in the line is the first to be served). Queues are commonly used in scenarios like process scheduling, handling requests in servers, and managing resources.
A queue supports the following fundamental operations:
Queues can be implemented using arrays, linked lists, or using the Standard Template Library (STL) queue class.
In a simple array-based queue, you need to maintain two indices: front (indicating where to remove elements) and rear (indicating where to add elements).
Array-based Queue Implementation:
#include <iostream>
using namespace std;
class Queue {
private:
int *arr;
int front, rear, capacity;
public:
// Constructor to initialize the queue
Queue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
}
// Enqueue operation
void enqueue(int x) {
if (rear == capacity - 1) {
cout << "Queue Overflow\n";
return;
}
arr[++rear] = x;
cout << x << " enqueued to queue\n";
}
// Dequeue operation
int dequeue() {
if (front > rear) {
cout << "Queue Underflow\n";
return -1;
}
int data = arr[front++];
return data;
}
// Front operation
int frontElement() {
if (front > rear) {
cout << "Queue is empty\n";
return -1;
}
return arr[front];
}
// Check if the queue is empty
bool isEmpty() {
return front > rear;
}
// Destructor to deallocate memory
~Queue() {
delete[] arr;
}
};
int main() {
Queue q(5); // Create a queue of size 5
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
cout << "Front element: " << q.frontElement() << endl; // Should print 10
cout << "Dequeued element: " << q.dequeue() << endl; // Should print 10
cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << endl; // Should print No
return 0;
}
Alternatively, a queue can be implemented using a linked list where each node represents an element. The front pointer will point to the front element, and the rear pointer will point to the last element.
Linked List-based Queue Implementation:
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class Queue {
private:
Node* front;
Node* rear;
public:
// Constructor to initialize the queue
Queue() {
front = rear = nullptr;
}
// Enqueue operation
void enqueue(int x) {
Node* newNode = new Node();
newNode->data = x;
newNode->next = nullptr;
if (rear == nullptr) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
// Dequeue operation
int dequeue() {
if (front == nullptr) {
cout << "Queue Underflow\n";
return -1;
}
Node* temp = front;
int data = front->data;
front = front->next;
// If the queue becomes empty, make rear null as well
if (front == nullptr) {
rear = nullptr;
}
delete temp;
return data;
}
// Front operation
int frontElement() {
if (front == nullptr) {
cout << "Queue is empty\n";
return -1;
}
return front->data;
}
// Check if the queue is empty
bool isEmpty() {
return front == nullptr;
}
// Destructor to free memory
~Queue() {
while (front != nullptr) {
dequeue();
}
}
};
int main() {
Queue q;
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
cout << "Front element: " << q.frontElement() << endl; // Should print 10
cout << "Dequeued element: " << q.dequeue() << endl; // Should print 10
cout << "Is queue empty? " << (q.isEmpty() ? "Yes" : "No") << endl; // Should print No
return 0;
}
C++ provides a built-in queue container in the Standard Template Library (STL) that makes working with queues much easier. It follows the FIFO order and provides efficient access to the front and rear elements.
Using STL Queue:
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
q.push(10); // Enqueue operation
q.push(20);
q.push(30);
cout << "Front element: " << q.front() << endl; // Should print 10
q.pop(); // Dequeue operation
cout << "Dequeued element: " << q.front() << endl; // Should print 20
cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl; // Should print No
return 0;
}
The STL queue provides:
push(x): Adds element x to the rear of the queue.pop(): Removes the element from the front.front(): Returns the front element without removing it.back(): Returns the rear element.empty(): Checks if the queue is empty.size(): Returns the number of elements in the queue.Process Scheduling: Queues are used in operating systems for task scheduling. For example, in a CPU scheduling algorithm, processes are managed in a queue where the process that enters first gets executed first.
Breadth-First Search (BFS): Queues are used in graph traversal algorithms like BFS to explore nodes level by level, ensuring that nodes are visited in the order they are discovered.
Print Queue: In printers, print jobs are managed using a queue. The job that enters the queue first is printed first.
Event Handling: In event-driven systems, queues are used to store and handle incoming events in the order they are received.
Data Buffering: Queues are used in networking and multimedia systems for buffering data packets and streaming data to ensure smooth delivery and processing.
For both array-based and linked list-based queues:
Advantages:
Disadvantages:
Queues are an essential data structure in computer science that follow the FIFO principle. They are widely used in various applications, including process scheduling, BFS, and event handling. C++ provides several ways to implement queues, from manual implementations using arrays and linked lists to using the powerful STL queue class. Understanding how queues work and their practical applications will help you solve
Open this section to load past papers