This article is a continuation of the Series on Data Structures and carries the discussion on different types of data structures and their implementation. The aim of this series is to provide easy and practical examples that anyone can understand. In our previous article, we have seen how to implement the stack data structure using the Linked List. In this article, we will see Queue in C Programming – Data Structures Part 4.
Queue in C Programming
What is Queue in general?
In real life, Queue is a line or sequence of people or vehicles or any objects awaiting their turn to be attended to or to proceed. Let’s consider the below real-time examples.
- A queue of people waiting for their turn to come to take money from the ATM machine,
- A queue of vehicles waiting for the traffic signal to turn green,
- A queue of people waiting to buy tickets in a railway station or movie theater.
- etc.
The above gif image explains a funny scenario that everyone faced even one time in our life. Okay, let’s start our original topic.
What is Queue in C programming language?
A queue is a linear data structure that follows the FIFO (First In First Out) principle in deletion and insertion operations. That means the item that was inserted first should be removed first.
Unlike a stack, a queue is open at both ends called as Rear and Front. One end is provided for the insertion of the data and the other end is for the deletion of the data.
Refer to the below image.
Types of Queues
There are four different types of queues:
- Simple Queue
- Circular Queue
- Priority Queue
- Double Ended Queue
Note: In this post, we will focus on the simple queue and its implementation.
Ways to implement the Queue
There are two ways of implementing the Queue:
- Queue Implementation using an array
- Queue Implementation using Linked list
In this article, we will be implementing the queue using an array.
We will have to maintain two pointers that are used to track the FRONT and REAR end.
FRONT is used to track the first element of the queue. REAR is used to track the last element of the queue. Initially, set the value of FRONT and REAR to -1.
Operations on Queue
A queue allows the following operations:
We will see them one by one.
Enqueue
This method is used to add the element to the queue. As we have two ends (Front end, Rear end) in the queue, this addition will happen at the Rear end.
- First, check whether the Queue is Full or not.
- If it is full, then we cannot add the new element to it. This is overflow. So exit.
- If it is not full, and if this is the very first element, make the
FRONTto 0. - The increase the
REARindex by 1. - Finally, add the new element in the position pointed to by
REAR.
The below flow chart may help you to understand the logic.
Example
void enQueue()
{
if( isFull() == true )
{
printf("ERROR: Queue is Overflow!!!\n");
}
else
{
if( FRONT == -1 )
{
FRONT = 0;
}
REAR++;
int value;
printf("Enter a value to be add: ");
scanf("%d",&value);
queue[REAR] = value;
printf("%d is added to the Queue\n", value);
}
}
Dequeue
This method is used to remove the element from the queue. As we have two ends (Front end, Rear end) in the queue, this removal will happen at the Front end.
- First, check whether the Queue is empty or not.
- If that is empty, we cannot remove the element as no elements are present. So exit from there.
- If it is not empty, then return the value which is pointing to FRONT.
- Increment the FRONT.
The below flow chart may help you to understand the logic.
Example
void deQueue()
{
if( isEmpty() == true )
{
printf("ERROR: Queue is Underflow!!!\n");
}
else
{
printf("%d is deleted\r\n", queue[FRONT]);
FRONT++;
/* Reset it, if we reached the end */
if(FRONT > REAR)
{
FRONT = REAR = -1;
}
}
}
IsEmpty
This is used to check whether the queue is empty or not.
bool isEmpty()
{
bool isQueueEmpty = false;
if( FRONT == -1 )
{
isQueueEmpty = true;
}
return (isQueueEmpty);
}
IsFull
This is used to check whether the queue is full or not.
bool isFull()
{
bool isQueueFull = false;
if( REAR == MAX-1 )
{
isQueueFull = true;
}
return (isQueueFull);
}
Peek
This function is used to see the element in the front of the queue. This operation will not remove the element.
void peek()
{
if( isEmpty() == true )
{
printf("Queue is Empty!!!\n");
}
else
{
printf("Top Element is %d\n", queue[FRONT]);
}
}
Implementation of the queue in C using an array
Before writing a code, you should keep the below points in your mind.
- A pointer called FRONT and
REARis used to keep track of the first and last element in the queue. So, initialize it with -1. If the value of the FRONT is -1, then the queue is empty. If the value of the REAR is equal toMAX-1, then the queue is full. - Whenever you enqueue the element to the queue, you have to check whether the queue is full or not. If it is full, then you should not add the elements as the queue will overflow. If it is not full, then add the element.
- When you want to dequeue the element from the queue, you have to check whether the queue is empty or not. If it is empty, you should not remove the element as the queue is an underflow. You can remove it if the queue is not empty.
Source Code (Queue in C program)
#include<stdio.h>
#include<stdbool.h>
#define MAX 3 // Queue's maximum size
//Function declaration
void enQueue(void);
void deQueue(void);
bool isEmpty(void);
void display(void);
bool isFull(void);
void peek(void);
int queue[MAX];
int REAR = -1;
int FRONT = -1;
int main()
{
int choice;
printf("*** Queue Implementation using Array***");
while(1)
{
printf("\n1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display all the Elements\n");
printf("4. Peek Top element\n");
printf("Enter the Choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
//Inserting the element into the queue
enQueue();
break;
}
case 2:
{
//Removing the element from the queue
deQueue();
break;
}
case 3:
{
//Displaying all the elements in the queue
display();
break;
}
case 4:
{
//Displaying the element which is in the front of the queue
peek();
break;
}
default:
{
printf ("\nPlease Enter a Valid Choice: ");
break;
}
}
}
}
bool isFull()
{
bool isQueueFull = false;
if( REAR == MAX-1 )
{
isQueueFull = true;
}
return (isQueueFull);
}
bool isEmpty()
{
bool isQueueEmpty = false;
if( FRONT == -1 )
{
isQueueEmpty = true;
}
return (isQueueEmpty);
}
void enQueue()
{
if( isFull() == true )
{
printf("ERROR: Queue is Overflow!!!\n");
}
else
{
if( FRONT == -1 )
{
FRONT = 0;
}
REAR++;
int value;
printf("Enter a value to be add: ");
scanf("%d",&value);
queue[REAR] = value;
printf("%d is added to the Queue\n", value);
}
}
void deQueue()
{
if( isEmpty() == true )
{
printf("ERROR: Queue is Underflow!!!\n");
}
else
{
printf("%d is deleted\r\n", queue[FRONT]);
FRONT++;
/* Reset it, if we reached the end */
if (FRONT > REAR)
{
FRONT = REAR = -1;
}
}
}
void display()
{
if( isEmpty() == true )
{
printf("Queue is Empty!!!\n");
}
else
{
int i;
printf("Queue elements are:\n");
for (i = FRONT; i <= REAR; i++)
{
printf("%d ", queue[i]);
}
printf("\n");
}
}
void peek()
{
if( isEmpty() == true )
{
printf("Queue is Empty!!!\n");
}
else
{
printf("Top Element is %d\n", queue[FRONT]);
}
}
Output
*** Queue Implementation using Array*** 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 3 Queue is Empty!!! 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 1 Enter a value to be add: 10 10 is added to the Queue 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 1 Enter a value to be add: 20 20 is added to the Queue 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 1 Enter a value to be add: 30 30 is added to the Queue 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 1 ERROR: Queue is Overflow!!! 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 3 Queue elements are: 10 20 30 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 2 10 is deleted 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 2 20 is deleted 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 2 30 is deleted 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 1 Enter a value to be add: 15 15 is added to the Queue 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 4 Top Element is 15 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice: 3 Queue elements are: 15 1. Enqueue 2. Dequeue 3. Display all the Elements 4. Peek Top element Enter the Choice:
Drawback of array implementation
- The main problem is Limited memory. You cannot change the size of the queue while running(dynamically).
- Unfilled space will not be utilized as the front pointer of the queue would have moved ahead. This has been explained in the next section.
Limitations of Queue
If you take the above method, let’s assume the queue is full. It is having data of 10, 20, and 30 like below.
Now, you are doing two dequeue operations. So, the FRONT and REAR will be pointing to the last element. Now the queue looks like below.
Now two elements are free. If you try to add any new element, it will throw you an overflow. Yes, We have the free space. But, those spaces can’t be used as we can’t traverse them again. If you dequeue 30, then the FRONT and REAR will be reset to -1. Now you can able to add a new element. We can rectify this problem by using the Circular Queue.
The complexity of the Queue
The complexity of enqueue and dequeue operations in a queue using an array is O(1).
Applications of Queue
- Breadth-first search (BFS) algorithm.
- It is used to handle interrupts in real-time systems.
- Job Scheduling, to maintain a queue of processes in operating systems (FIFO order).
- The queue of packets in data communication.
- CPU scheduling, Disk Scheduling.
- When data is transferred asynchronously between two processes, the queue is used for synchronization. For example IO Buffers, pipes, file IO, etc.
- Call Center phone systems use Queues to hold people calling them in order.
- Handling website traffic.
- Routers and switches in networking.
- Maintaining the playlist in media players.
In our next tutorial, we will implement a Queue data structure using a Linked List in C programming.
You can also read the below topics.
Credits:
Embedded Software | Firmware | Linux Devic Deriver | RTOS
Hi, I’m SLR. I am a tech blogger and an Embedded Engineer. I am always eager to learn and explore tech-related concepts. And also, I wanted to share my knowledge with everyone in a more straightforward way with easy practical examples. I strongly believe that learning by doing is more powerful than just learning by reading. I love to do experiments. If you want to help or support me on my journey, consider sharing my articles, or Buy me a Coffee! Thank you for reading my blog! Happy learning!
