This article is about queue in data structures with details of Basic Operations, working, implementation, and limitations of the queue in data structures and algorithms.
The queue is another data structure that can be used to store data. But, this is quite different from the stack. Stack works on the principle of last in first out but queue works on the principle of first in first out. So first, we need to understand what is First in First Out Principle.
As we all have seen how people stand at the railway ticket counter for taking tickets. And after getting the ticket, they go away. We observe a pattern here that the person who entered first in the queue will go away the first. And, the person who entered the queue last will go away last from the queue. This principle is called the first in first out principle.
The same thing happens in the queue. The element that is inserted first in the queue, leaves the queue first.
Now, we will understand this thing diagrammatically –
So, this way the elements are inserted and removed from the queue.
Basic Operations on Queue in Data Structures
Below listed are some of the basic operations that can be performed on the queue to make it useful –
Enqueue – Adding an element to the end of the queue is called enqueue.
Dequeue – Removing an element from the front of the queue.
IsEmpty – This function is used to check whether the queue is empty or not.
IsFull – This operation is used to check whether the queue is full or not.
Peek – This is used to check the top value of the queue without removing the top element.
Working on the queue in Data Structures
Two pointers ‘front’ and ‘rear’ are initiated and made to point to the top and last of the queue. Initially, both are set to the value -1.
For enqueue operation, First, the queue is checked whether it is full or not. If it is full, then we cannot insert a new element, and else the value of the front is set to 0, and increase the rear index by 1. And, a new element is inserted into the position pointed by the rear.
For the dequeue operation, first, we need to check whether the queue is empty or not. If the queue is empty, return the value pointed by the front. And increase the front index by 1. For the last elements, reset the values of the front and rear to -1.
Now, we will learn the coding for these operations and the
Implementation of the queue data structure –
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
return false;
}
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full";
} else {
if (front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front >= rear) {
front = -1;
rear = -1;
}
else {
front++;
}
cout << endl
<< "Deleted -> " << element << endl;
return (element);
}
}
void display() {
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << endl
<< "Front index-> " << front;
cout << endl
<< "Items -> ";
for (i = front; i <= rear; i++)
cout << items[i] << " ";
cout << endl
<< "Rear index-> " << rear << endl;
}
}
};
int main() {
Queue q;
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
q.enQueue(6);
q.display();
q.deQueue();
q.display();
return 0;
}
Limitations of the Queue in Data Structures
The queue is one of the very useful data structures, but it has some limitations too –
- The operations such as insertion and deletion of elements from the middle are time-consuming.
- Limited Space.
- In a classical queue, a new element can only be inserted when the existing elements are deleted from the queue.
- Searching for an element takes O(N) time.
So, in this article, we learned about a queue data structure that is quite useful for handling real-time problems such as CPU scheduling, Call center phone systems, and In many more real-time places.
Try these quizzes
