In computer science, a queue is a collection of elements that follows the FIFO (First-In, First-Out) principle. It can be visualized as a line of people waiting to take an action, where the person who arrived first is served first.
A queue data structure typically provides two primary operations:
- Enqueue: Add an element to the end of the queue.
- Dequeue: Remove and retrieve the element from the front of the queue.
In this blog post, we will explore different queue algorithms and their implementations in C++.
1. Standard Queue Implementation
C++ provides a built-in queue container in the <queue> library. This container encapsulates the queue data structure and provides various methods to manipulate the queue. Let’s see an example:
#include <iostream>
#include <queue>
int main() {
std::queue<int> myQueue;
myQueue.push(5);
myQueue.push(10);
myQueue.push(15);
std::cout << "Front element: " << myQueue.front() << std::endl;
std::cout << "Queue size: " << myQueue.size() << std::endl;
while (!myQueue.empty()) {
std::cout << myQueue.front() << " ";
myQueue.pop();
}
return 0;
}
In the above example, we include the necessary header files and create a queue using std::queue of integer type. We push elements into the queue using push() method and access the front element using front().
The empty() method checks if the queue is empty, and pop() removes the element from the front of the queue.
2. Circular Queue Implementation
A circular queue is a variation of a queue in which the end is connected back to the front, forming a circle. It overcomes the drawback of the standard queue where the space is consumed continuously at the front, making it inefficient.
#include <iostream>
#define SIZE 5
class CircularQueue {
int arr[SIZE];
int front;
int rear;
public:
CircularQueue() {
front = rear = -1;
}
bool isFull() {
if (front == 0 && rear == SIZE - 1)
return true;
if (front == rear + 1)
return true;
return false;
}
bool isEmpty() {
if (front == -1)
return true;
return false;
}
void enqueue(int item) {
if (isFull()) {
std::cout << "Queue is full." << std::endl;
return;
}
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
arr[rear] = item;
std::cout << item << " enqueued to the queue." << std::endl;
}
void dequeue() {
if (isEmpty()) {
std::cout << "Queue is empty." << std::endl;
return;
}
std::cout << arr[front] << " dequeued from the queue." << std::endl;
if (front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
}
void display() {
if (isEmpty()) {
std::cout << "Queue is empty." << std::endl;
return;
}
std::cout << "Elements in the queue are: ";
int i = front;
while (i != rear) {
std::cout << arr[i] << " ";
i = (i + 1) % SIZE;
}
std::cout << arr[rear] << std::endl;
}
};
int main() {
CircularQueue cqueue;
cqueue.enqueue(1);
cqueue.enqueue(2);
cqueue.enqueue(3);
cqueue.enqueue(4);
cqueue.display();
cqueue.dequeue();
cqueue.dequeue();
cqueue.display();
cqueue.enqueue(5);
cqueue.enqueue(6);
cqueue.enqueue(7);
cqueue.display();
return 0;
}
In the above example, we create a class called CircularQueue that represents the circular queue. It includes methods like isFull(), isEmpty(), enqueue(), dequeue(), and display().
The circular nature of the queue is implemented using modulo arithmetic to wrap around the index when it reaches the end.
Conclusion
In this blog post, we explored both the standard queue implementation and circular queue implementation in C++. Understanding the queue data structure and its algorithms is essential for many real-life applications, such as process scheduling, network packet handling, and more.
Using the built-in std::queue or implementing a custom queue, you can efficiently manage elements with the FIFO principle.
#tech #C++