QUEUEs
Queue is a linear data structure that follows FIFO (First In First Out) Principle, so the first
element inserted is the first to be popped out.
FIFO Principle in Queue:
FIFO Principle states that the first element added to the Queue will be the first one to be
removed or processed. So, Queue is like a line of people waiting to purchase tickets, where
the first person in line is the first person served. (i.e. First Come First Serve).
Basic Terminologies of Queue
Front: Position of the entry in a queue ready to be served, that is, the first entry that
will be removed from the queue, is called the front of the queue. It is also referred as
the head of the queue.
Rear: Position of the last entry in the queue, that is, the one most recently added, is
called the rear of the queue. It is also referred as the tail of the queue.
Size: Size refers to the current number of elements in the queue.
Capacity: Capacity refers to the maximum number of elements the queue can hold.
Representation of Queue
Queue Operations
1. Enqueue: Adds an element to the end (rear) of the queue. If the queue is full, an
overflow error occurs.
2. Dequeue: Removes the element from the front of the queue. If the queue is empty, an
underflow error occurs.
3. Peek/Front: Returns the element at the front without removing it.
4. Size: Returns the number of elements in the queue.
5. isEmpty: Returns true if the queue is empty, otherwise false.
6. isFull: Returns true if the queue is full, otherwise false.
Types of Queues
Queue data structure can be classified into 4 types:
1. Simple Queue: Simple Queue simply follows FIFO Structure. We can only insert the
element at the back and remove the element from the front of the queue. A simple
queue is efficiently implemented either using a linked list or a circular array.
2. Double-Ended Queue (Deque): In a double-ended queue the insertion and deletion
operations, both can be performed from both ends. They are of two types:
Input Restricted Queue: This is a simple queue. In this type of queue, the input
can be taken from only one end but deletion can be done from any of the ends.
Output Restricted Queue: This is also a simple queue. In this type of queue,
the input can be taken from both ends but deletion can be done from only one
end.
3. Priority Queue: A priority queue is a special queue where the elements are accessed
based on the priority assigned to them. They are of two types:
Ascending Priority Queue: In Ascending Priority Queue, the elements are arranged in
increasing order of their priority values. Element with smallest priority value is
popped first.
Descending Priority Queue: In Descending Priority Queue, the elements are arranged
in decreasing order of their priority values. Element with largest priority is popped
first.
Applications of Queue Data Structure
Application of queue is common. In a computer system, there may be queues of tasks waiting
for the printer, for access to disk storage, or even in a time-sharing system, for use of the
CPU. Within a single program, there may be multiple requests to be kept in a queue, or one
task may create other tasks, which must be done in turn by keeping them in a queue.
A Queue is always used as a buffer when we have a speed mismatch between a
producer and consumer. For example keyboard and CPU.
Queue can be used where we have a single resource and multiple consumers like a
single CPU and multiple processes.
In a network, a queue is used in devices such as a router/switch and mail queue.
Queue can be used in various algorithm techniques like Breadth First Search,
Topological Sort, etc.
Queue using Array - Simple Implementation
The queue uses an array with a fixed capacity, referred to as capacity, and tracks the
current number of elements with a variable size.
The variable front is initialized to 0 and represents the index of the first element in the
array. In the dequeue operation, the element at this index is removed.
To implement a queue of size n using an array, the operations are as follows:
Enqueue: Adds new elements to the end of the queue. Checks if the queue has space
before insertion, then increments the size.
Dequeue: Removes the front element by shifting all remaining elements one position
to the left. Decrements the queue size after removal.
getFront: Returns the first element of the queue if it's not empty. Returns -1 if the
queue is empty.
Display: Iterates through the queue from the front to the current size and prints each
element.
#include <stdio.h>
#define MAX 5 // maximum size of queue
int queue[MAX];
int front = -1, rear = -1;
// Check if queue is full
int isFull() {
return (rear == MAX - 1);
}
// Check if queue is empty
int isEmpty() {
return (front == -1 || front > rear);
}
// Enqueue operation
void enqueue(int value) {
if (isFull()) {
printf("Queue Overflow! Cannot insert %d\n", value);
} else {
if (front == -1) front = 0; // first element
queue[++rear] = value;
printf("%d enqueued into queue.\n", value);
}
}
// Dequeue operation
void dequeue() {
if (isEmpty()) {
printf("Queue Underflow! Cannot dequeue.\n");
} else {
printf("%d dequeued from queue.\n", queue[front]);
front++;
}
}
// Display the queue
void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
} else {
printf("Queue elements: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
enqueue(40);
enqueue(50);
enqueue(60); // should show overflow
display();
return 0;
}
Circular Queue
A circular queue is a type of queue in which the last position is connected back to the first
position to make a circle. It is also known as a Ring Buffer. In a normal queue, once the
queue becomes full, we cannot insert the next element even if there is a space in front of the
queue. But using a circular queue, we can use the space to insert elements.
It is a linear data structure that follows the FIFO mechanism. The circular queue is a more
efficient way to implement a queue in a fixed size array. In a circular queue, the last element
points to the first element making a circular link.
Representation of Circular Queue
Following is the representation of a circular queue, where the front is the index of the first
element, and the rear is the index of the last element.
Operations on Circular Queue
There are mainly four operations that can be performed on a circular queue:
Enqueue: Insert an element into the circular queue.
Dequeue: Delete an element from the circular queue.
Front: Get the front element from the circular queue.
Rear: Get the last element from the circular queue.
Circular Queue using Array
Following is the implementation of a circular queue using an array:
Enqueue Operation on Circular Queue
Enqueue operation is used for inserting an element into the circular queue. The steps to
perform the enqueue operation are as follows:
Algorithm for Enqueue Operation
Following are the steps to perform the enqueue operation on a circular queue:
[Link] an array or any data structure to store the elements of the circular queue.
[Link] two variables front and rear.
[Link] if the circular queue is full.
[Link] it is not full, and if the front is -1, set the front to 0.
[Link] the rear by 1 and store it in the rear index.
[Link] the rear index using rear = (rear + 1) % SIZE.
Dequeue Operation on Circular Queue
Dequeue operation is used for deleting an element from the circular queue. The steps to
perform the dequeue operation are as follows:
Algorithm for Dequeue Operation
Following are the steps to perform the dequeue operation on a circular queue:
[Link] if the circular queue is empty.
[Link] the queue is not empty, store the element at the front index.
[Link] the front and rear are equal, set the front and rear to -1.
[Link], increase the front index by 1 using the formula front = (front + 1) % SIZE.
[Link] last print the deleted element.
Modulo capacity is the size of the data structure used as the modulus to ensure indices wrap
around to the beginning when they reach the end.
1️⃣ Circular Queue (most important)
If:
capacity = N
indices go from 0 to N − 1
Then index movement is done using:
(next index) = (current index + 1) % capacity
This ensures:
When index reaches N − 1, it moves back to 0
No shifting of elements is required
Code for Dequeue
#include <stdio.h>
#define MAX 5 // maximum size of queue
int queue[MAX];
int front = -1, rear = -1;
// Check if queue is full
int isFull() {
return ((front == 0 && rear == MAX - 1) || (front == rear + 1));
}
// Check if queue is empty
int isEmpty() {
return (front == -1);
}
// Enqueue operation
void enqueue(int value) {
if (isFull()) {
printf("Queue Overflow! Cannot insert %d\n", value);
return;
}
if (front == -1) { // first element
front = rear = 0;
} else {
rear = (rear + 1) % MAX; // circular increment
}
queue[rear] = value;
printf("%d enqueued into circular queue.\n", value);
}
// Dequeue operation
void dequeue() {
if (isEmpty()) {
printf("Queue Underflow! Cannot dequeue.\n");
return;
}
printf("%d dequeued from circular queue.\n", queue[front]);
if (front == rear) { // queue had only one element
front = rear = -1;
} else {
front = (front + 1) % MAX; // circular increment
}
}
// Display the queue
void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements: ");
int i = front;
while (1) {
printf("%d ", queue[i]);
if (i == rear)
break;
i = (i + 1) % MAX;
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
display();
dequeue();
dequeue();
display();
enqueue(50);
enqueue(60);
display();
enqueue(70); // should show overflow
return 0;
}
Front Operation on Circular Queue
Front operation is used to get the front element from the circular queue. The steps to perform
the front operation are as follows:
Algorithm for Front Operation
[Link] if the circular queue is empty.
[Link] not empty, print the front index element
Rear Operation on Circular Queue
Rear operation is used to get the last element from the circular queue. The steps to perform
the rear operation are as follows:
Algorithm for Rear Operation
[Link] if the circular queue is empty..
[Link] it is not empty, print the element at the rear index.
Time Complexity of Circular Queue
Following are the time complexities of the circular queue:
Enqueue Operation: The time complexity of the enQueue operation is O(1) as we
can insert an element at the rear end of the queue in constant time.
Dequeue Operation: The time complexity of the deQueue operation is O(1) as we
can delete an element from the front end of the queue in constant time.
Front Operation: The time complexity of the front operation is O(1) as we can get
the front element of the queue in constant time.
Rear Operation: The time complexity of the rear operation is O(1) as we can get the
rear element of the queue in constant time.
Applications of Circular Queue
Following are some of the applications of a circular queue:
Memory Management: Circular queues are used in memory management to manage
the memory efficiently. It is used to allocate memory to the processes when they are
in need of memory.
Buffer Management: These queues are also useful in buffer management. Consider a
situation where data is produced at a faster rate than it is consumed. In such cases, a
circular queue is used to store the data temporarily.
Operating System: Suppose your system has a lot of processes to execute. In such
cases, for the better management of processes, the operating system uses a circular
queue to allocate the CPU to the processes.
Traffic Management: Traffic singals are controlled by the circular queue. Let's say
there are three signals, red, yellow, and green. The signals are in a circular queue.
When the green signal is on, the next signal will be yellow, and then red. This process
will continue in a circular manner.
Multimedia Player: When we play songs in a multimedia player, the songs are
played in a circular manner. Once the last song is played, the first song will be played
next. This is done using a circular queue.
Priority Queue
Priority Queue is more specialized data structure than Queue. Like ordinary queue, priority
queue has same method but with a major difference. In Priority queue items are ordered by
key value so that item with the lowest value of key is at front and item with the highest value
of key is at rear or vice versa. So we're assigned priority to item based on its key value.
Lower the value, higher the priority. Following are the principal methods of a Priority Queue.
Basic Operations
insert / enqueue − add an item to the rear of the queue.
remove / dequeue − remove an item from the front of the queue.
Priority Queue Representation
There is few more operations supported by queue which are following.
Peek − get the element at front of the queue.
isFull − check if queue is full.
isEmpty − check if queue is empty.
Insert / Enqueue Operation
Whenever an element is inserted into queue, priority queue inserts the item according to its
order. Here we're assuming that data with high value has low priority.
void insert(int data){
int i = 0;
if(!isFull()){
// if queue is empty, insert the data
if(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
for(i = itemCount - 1; i >= 0; i-- ){
// if data is larger, shift existing item to right end
if(data > intArray[i]){
intArray[i+1] = intArray[i];
}else{
break;
}
}
// insert the data
intArray[i+1] = data;
itemCount++;
}
}
}
Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using item count.
Once element is removed. Item count is reduced by one.
int removeData()
{ return intArray[--itemCount]; }
Demo Program:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int itemCount = 0;
int peek(){
return intArray[itemCount - 1];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
int i = 0;
if(!isFull()){
// if queue is empty, insert the data
if(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
for(i = itemCount - 1; i >= 0; i-- ){
// if data is larger, shift existing item to right end
if(data > intArray[i]){
intArray[i+1] = intArray[i];
}else{
break;
}
}
// insert the data
intArray[i+1] = data;
itemCount++;
}
}
}
int removeData(){
return intArray[--itemCount];
}
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 12 9 5 3 1
insert(15);
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 15 12 9 5 3 1
if(isFull()){
printf("Queue is full!\n");
}
// remove one item
int num = removeData();
printf("Element removed: %d\n",num);
// ---------------------
// index : 0 1 2 3 4
// ---------------------
// queue : 15 12 9 5 3
// insert more items
insert(16);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 15 12 9 5 3
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 15 12 9 5 3
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty()){
int n = removeData();
printf("%d ",n);
}
}
Output:
Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 3 5 9 12 15 16