Do you think IIT Guwahati certified course can help you in your career?
Introduction
A data structure is a method of managing data in a computer that can be used effectively. For example, we have linked lists, stacks, trees, and queues as some of the data structures that can organize data. Similarly, we can store a list of items having a similar data type using the array data structure.
What are Queues in C++?
A Queue is a linear data structure that follows the FIFO principle i.e., the First-In-First-Out method. The 2 ends of a queue are called Front and Rear. At the start, both Front and Rear are equal to -1 so the queue is empty. Insertion takes place at the Rear end, and the elements are removed or accessed from the Front.
Some applications of queues are :
Scheduling: Job Scheduling, CPU Scheduling.
Buffers: I/O Buffers.
Operations supported by Queues
Some operations performed on a queue are:
Operation
Description
enqueue()
Inserting a new element in the queue.
dequeue()
Removing an element from the front of the queue.
showfront()
Displaying the element at the front of the queue.
isempty()
Checking if the queue is empty.
Inserting elements in a queue
Let us take an example of a queue of size= 5.
To insert (enqueue) the element (suppose here 8) in the Queue, we will have to increment the Rear by one and insert 8 at the Rear.
When inserting we have to take care of two special cases:
When the Queue is empty, the initial value of Front and Rear will be -1, so we will make Front = 0 and increment Rear and insert the element at the Rear.
When the Queue is full, here, we cannot insert any elements in the Queue.
Implementation for Insertion
void enqueue(int element) {
// to check if queue is full or not
if (size == rear) {
cout << "Queue is full" << endl;
return;
}
// to insert an element at the rear of the queue
else {
cout << "Element inserted" << endl;
queue[rear] = element;
rear++;
}
return;
}
If the rear is equal to the size-1 then we will print the queue is full; else we will increment the rear index and store the new element at the rear index.
Deleting elements in a queue
If we have to remove the first element from the Queue, we will increment Front by one.
While removing (dequeue) elements from the Queue, we also have two exceptional cases:
The queue is empty - in that case, the Front and Rear will be equal to -1, and as there are no elements in the Queue, we cannot perform the dequeue operation.
The queue has only one element - in that case, the Front will be equal to the Rear, and we will make both equal to -1.
Implementation for Deletion
void dequeue() {
// to check if the queue is empty
if (front == rear) {
cout << "Queue is empty" << endl;
return;
} else {
for (int i = 0; i < rear - 1; i++) {
queue[i] = queue[i + 1];
}
cout << "Element deleted" << endl;
// decrement the rear
rear--;
}
return;
}
First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty. Else, we will shift all the elements from the start to end to the left by 1. Here we will ignore the element's value at index 0 because we have to remove the element at index 0.
Displaying the whole queue
void printQueue() {
// to check if queue is empty
if (front == rear) {
cout << "Queue is Empty" << endl;
return;
}
//traversing from front to rear to print the elements
cout << "The queue is: ";
for (int i = front; i < rear - 1; i++) {
cout << queue[i] << " <-- ";
}
cout << queue[rear - 1] << endl;
return;
}
You can also try this code with Online C++ Compiler
First, we will check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will simply print all the elements of the queue.
Displaying only the front element of the queue
void getFront() {
// to check if the queue is empty
if (front == rear) {
cout << "Queue is Empty" << endl;
return;
}
cout << "Front element is: " << queue[front] << endl;
return;
}
We will first check if the queue is empty or not. If the queue is empty then we will print that the queue is empty else we will just print the front element by using the front variable which is keeping the index of the front variable.
Code for implementation of queues using array
C++
C++
#include <bits/stdc++.h> using namespace std;
struct Queue { int front, rear, size; int* queue; Queue(int c) { front = rear = 0; size = c; queue = new int; }
~Queue() { delete[] queue; }
// to insert an element in the queue void enqueue(int element) { if (size == rear) { cout<<"Queue is full"<<endl; return; }
// function to delete an element from the queue void dequeue() { // to check if the queue is empty if (front == rear) { cout<<"Queue is empty"<<endl; return; }
// shift all the elements from index 1 till the last element to the left by 1 else { for (int i = 0; i < rear - 1; i++) { queue[i] = queue[i + 1]; } cout<<"Element deleted"<<endl; // decrement the rear rear--; } return; }
// function to print the elements of the queue void printQueue() { // to check if queue is empty if (front == rear) { cout<<"Queue is Empty"<<endl; return; }
// traverse front to rear and print elements cout<<"The queue is: "; for (int i = front; i < rear-1; i++) { cout<<queue[i]<<" <-- "; } cout<<queue[rear-1]<<endl; return; }
// print the front of the queue void getFront() { // to check if the queue is empty if (front == rear) { cout<<"The Queue is Empty"<<endl; return; }
cout<<"Front element is: "<< queue[front]<<endl; return; } };
// Driver code int main() { // To create a queue of size 5 Queue queue(5); // print the queue elements queue.printQueue(); // inserting elements in the queue queue.enqueue(7); queue.enqueue(4); queue.enqueue(9); queue.enqueue(6); // printing the queue elements queue.printQueue(); // inserting the element in the queue queue.enqueue(1); // printing the queue elements queue.printQueue(); // deleting the front element from the queue queue.dequeue(); // printing the queue elements queue.printQueue(); // deleting the front element from the queue queue.dequeue(); // print Queue elements queue.printQueue(); // print the front element of the queue queue.getFront(); return 0; }
You can also try this code with Online C++ Compiler
The Queue is Empty
Element inserted
Element inserted
Element inserted
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6
Element inserted
The queue is: 7 <-- 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 4 <-- 9 <-- 6 <-- 1
Element deleted
The queue is: 9 <-- 6 <-- 1
Front element is: 9
Dequeue a double-ended queue, or a data structure, where the elements can be deleted or inserted at both ends (FRONT and REAR).
Is Queue Better Than Array?
Queues and arrays serve different purposes. Queues are better for scenarios requiring First-In-First-Out (FIFO) operations, like task scheduling, while arrays excel in random access and static storage. The choice depends on the specific use case and operation requirements.
Name some applications of queue Data Structure.
To keep the playlist in media players (to add or remove the songs)
To reverse strings
To verify if delimiters (parenthesis, brackets etc.) are balanced in a computer program
To search the vertices of a graph.
What is the time complexity of push and pop functions of queues?
The time complexity of enqueue is O(1) and the time complexity of Dequeue is O(n).
What are Priority Queues?
A priority queue is a specialized queue in which the items are associated with a "priority" so that the highest key is always on the Front. So when you get an item from a priority queue, you always get the highest value.
Conclusion
Implementing a queue using arrays in C++ is an efficient way to understand the fundamentals of data structures and their operations. While arrays provide a simple and static approach, understanding their limitations, such as fixed size, helps in appreciating advanced implementations like circular queues or dynamic structures like linked lists.
85+ registered