Queue in C\C++ (FIFO) – How Queues are Implemented with Arrays & Linked List

After learning the concept of Stacks (LIFO), it’s time to discuss Queue in C/C++. The concept of Queue follows the FIFO rule, which means First in First Out. Don’t get confused between Stacks and Queues in C and C++. Here, we will clear all your doubts with examples.

In this article, we will cover the implementation of queues with array and linked list and circular queue in C/C++ with syntax and examples.

So, what are you waiting for? Let’s dive in.

1. What is a Queue in C/C++?

In contrast to a stack, a queue is nothing but a linear data structure that follows the FIFO rule (First In First Out). Insertion is done from the back (the rear end) and deletion is done from the front. In order to better understand the concept of queues in C, we can say that it follows the rule of “First Come First Serve”. Let us consider a simple scenario to help you get a clear picture of queues.

Learn More about Structures in C Language

Suppose you want to purchase a movie ticket. For that, you need to stand in a queue and wait for your turn, that is, you have to stand at the rear end of the queue. You can’t simply stand in the middle of the queue or occupy the front position.

From the above discussion, it is pretty obvious that insertion in a queue takes place from the back and deletion takes place from the front as the first person to enter the queue would be the first to get his job done and leave.

We can implement a queue in 2 ways:

1. Statically: Array implementation of queues allows the static memory allocation of its data elements. It is important to note that in this method, the queue acquires all the features of an array.
2. Dynamically: Linked list implementation of queues follow the dynamic memory allocation of its data elements. It is important to note that in this method, the queue inherits all the characteristics of a linked list.

Key takeaway: Both stacks and queues can be static or dynamic according to the way they are implemented.

It’s the right time to uncover the secrete of  Arrays in C and C++

2. Array Implementation of Queue in C/C++

As we already discussed, arrays support the static memory allocation of the data elements of the queue. Therefore, it is important to determine the size of the queue prior to the program run.

The queue functions basically include:

2.1 Insertion

Insertion of elements into the queue takes place from the rear end and hence would force the elements to shift forward. Inserting an element into the queue is also called enqueue.

Here is a diagrammatic representation of how elements are inserted into a queue:

Insert elements into a queue in C

void insert()
{
int element;
if (rear == LIMIT - 1)
printf("Queue Overflow\n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}

Insert elements into a queue in C++

void insert()
{
int element;
if (rear == LIMIT - 1)
cout<<"Queue Overflow\n";
else
{
if (front == - 1)
front = 0;
cout<<"Enter the element to be inserted in the queue: ";
cin>>element;
rear++;
queue[rear] = element;
}
}

Unveil the Important Concepts of Multi-dimensional Arrays in C/C++ (2D & 3D Arrays)

2.2 Deletion

In a queue, the deletion of data elements is done from the front. Deleting the element from the queue is also called dequeue.

Here is a diagrammatic representation of how elements are deleted from a queue:

Delete elements from the queue in C

void delet()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}

Delete elements from the queue in C++

void delet()
{
if (front == - 1 || front > rear)
{
cout<<"Queue Underflow \n";
}
else
{
cout<<"The deleted element in the queue is: " << queue[front] <<endl;
front++;
}
}

Key takeaway: It is important to note that we used the function name “delet” instead of “delete” because “delete” is a keyword.

2.3 Display

The stack data elements are displayed in the queue according to the FIFO rule.

Display all the elements in the queue in C

void display()
{
int i;
if (front == - 1)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the queue are:\n");
for (i = front; i <= rear; i++)
printf("%d\n", queue[i]);
}
}

Display all the elements in the queue in C++

void display()
{
int i;
if (front == - 1)
{
cout<<"Queue underflow\n";
}
else
{
cout<<"The elements of the queue are:\n";
for (i = front; i <= rear; i++)
cout<<queue[i];
}
}

Similarly, in queues, apart from these 3 main functions, it is necessary to check the overflow and underflow conditions to avoid unfavorable situations.

Example of Array Implementation of Queues in C

#include <stdio.h>
#include <stdlib.h>
#define LIMIT 100 // Specifying the maximum limit of the queue

/* Global declaration of variables */

int queue[LIMIT]; // Array implementation of queue
int front, rear; // To insert and delete the data elements in the queue respectively
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void insert(); // Function used to insert the element into the queue
void delet(); // Function used to delete the elememt from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION OF QUEUES\n\n");
front = rear = -1; // Initialzing front and rear to -1 indicates that it is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
int element;
if (rear == LIMIT - 1)
printf("Queue Overflow\n");
else
{
if (front == - 1)
front = 0;
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}

void delet()
{
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}

void display()
{
int i;
if (front == - 1)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the queue are:\n");
for (i = front; i <= rear; i++)
printf("%d\n", queue[i]);
}
}

Output-

Example of Array Implementation of Queues in C++

#include <iostream>
#include <stdlib.h> 
#define LIMIT 100 // Specifying the maximum limit of the queue
using namespace std;
 
/* Global declaration of variables */

int queue[LIMIT]; // Array implementation of queue
int front, rear; // To insert and delete the data elements in the queue respectively
int i; // To traverse the loop to while displaying the stack
int choice; // To choose either of the 3 stack operations

void insert(); // Function used to insert an element into the queue
void delet(); // Function used to delete an element from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule
 
int main()
{

cout<<"Welcome to DataFlair tutorials!"<<endl<<endl;

cout<< "ARRAY IMPLEMENTATION OF QUEUES "<<endl<<endl;;
front = rear = -1; // Initializing front and rear to -1 indicates that it is empty
do
{
                                                                                                                                                                                                         
cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n\n";
cout<<"Enter your choice: ";
cin>>choice;
 
switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0; 
}

void insert()
{
int element;
if (rear == LIMIT - 1)
cout<<"Queue Overflow\n";
else
{
if (front == - 1)
front = 0;
cout<<"Enter the element to be inserted in the queue: ";
cin>>element;
rear++;
queue[rear] = element;
}
} 

void delet()
{
if (front == - 1 || front > rear)
{
cout<<"Queue Underflow \n";
}
else
{
cout<<"The deleted element in the queue is: "<< queue[front]<<endl;
front++;
}
} 

void display()
{
int i;
if (front == - 1)
{
cout<<"Queue underflow\n";
}
else
{
cout<<"The elements of the queue are:\n"<<endl;
for (i = front; i <= rear; i++)
cout<< queue[i] <<endl;
}
}

Output-

Do you know how the Linked list works in C and C++?

3. Linked List Implementation of Queue in C/C++

As we already discussed, linked lists support the dynamic memory allocation of the data elements of the queue. Therefore, the size of the queue is allocated during the program run and needn’t be specified beforehand.

The 3 basic operations of Insertion, Deletion, and Display follow a similar trend as we saw in the array implementation of queues.

It is important to note that the condition of queue overflow does not exist in the linked list implementation of queues and the size of the stack is not pre-determined. But, the queue underflow condition still holds true.

3.1 Insertion

Insert elements into the queue in C

void insert()
{
struct node *temp;

temp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}

Insert elements into the queue in C++

(Here we have used classes to implement linked lists)

// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Queue
{
node *rear,*front;
public:
Queue()
{
rear = NULL;
front = NULL;
}
void insert();
};
// Member function definition
void Queue :: insert()
{
node *temp;
temp = new node;
cout<<"Enter the element to be inserted: ";
cin>> temp -> data;
temp -> next = NULL;
if(rear == NULL)
{
rear = temp;
front=temp;
}
else
{
rear -> next = temp;
rear = temp;
}
}

3.2 Deletion

Delete elements in a queue in C

void delet()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("Queue underflow\n");
front = rear = NULL;
}
else
{
printf("The deleted element from the queue is: %d\n", front->data);
front = front->link;
free(temp);
}
}

Delete elements in a queue in C++

// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Queue
{
node *rear,*front;
public:
Queue()
{
rear = NULL;
front = NULL;
}
void delet();
};
// Member function definition
void Queue :: delet()
{
if(front != NULL)
{
node *temp = front;
cout<< “The deleted element is: ” <<front -> data <<endl;
front = front -> next;
delete temp;
if(front == NULL)
rear = NULL;
}
else
cout<<"Queue Underflow!.";
}

3.3 Display

Display elements in the queue in C

void display()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}

Display elements in the queue in C++

// Structure definition
struct node
{
int data;
node *next;
};
// Class definition
class Queue
{
node *rear,*front;
public:
Queue()
{
rear = NULL;
front = NULL;
}
void display();
};
// Member function definition
void Queue :: display()
{
node *temp = front;
while(temp != NULL)
{
cout<< temp -> data <<endl;
temp = temp -> next;
}
}

Example of linked list implementation of queues in C

#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *link;
}*front, *rear;

void insert(); // Function used to insert the element into the queue
void delet(); // Function used to delete the elememt from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

int choice;
printf ("LINKED LIST IMPLEMENTATION OF QUEUES\n\n");
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
struct node *temp;

temp = (struct node*)malloc(sizeof(struct node));
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &temp->data);
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}

void delet()
{
struct node *temp;
temp = front;
if (front == NULL)
{
printf("Queue underflow\n");
front = rear = NULL;
}
else
{
printf("The deleted element from the queue is: %d\n", front->data);
front = front->link;
free(temp);
}
}

void display()
{
struct node *temp;
temp = front;
int cnt = 0;
if (front == NULL)
{
printf("Queue underflow\n");
}
else
{
printf("The elements of the stack are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}

Output-

Example of linked list implementation of queues in C++

#include <iostream>
using namespace std;

struct node
{
int data;
node *next;
};

class Queue
{
node *rear,*front;
public:
Queue()
{ 
rear = NULL;
front = NULL;
}
void insert(); // Function used to insert an element into the queue
void delet(); // Function used to delete an element from the queue
void display(); // Function used to display all the elements in the queue according to FIFO rule
};

void Queue :: insert()
{
node *temp;
temp = new node;
cout<<"Enter the element to be inserted: ";
cin>> temp -> data;
temp -> next = NULL;
if(rear == NULL)
{
rear = temp;
front = temp;
}
else
{
rear -> next = temp;
rear = temp;
}
}

void Queue :: delet()
{
if(front != NULL)
{
node *temp = front;
cout<< "The deleted element is: " << front -> data <<endl;
front = front -> next;
delete temp;
if(front == NULL)
rear= NULL;
}
else
cout<<"Queue Underflow!"<<endl;
}

void Queue :: display()
{
node *temp=front;
while(temp!=NULL)
{
cout<< temp -> data <<endl;
temp = temp -> next;
}
}


int main()
{

cout<<"Welcome to DataFlair tutorials!"<<endl<<endl;

Queue q;
int choice;
cout<<"LINKED LIST IMPLEMENTATION OF QUEUES\n\n";
do
{

cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n\n";
cout<<"Enter your choice:";
cin>>choice;

switch(choice)
{
case 1:
q.insert();
break;
case 2:
q.delet();
break;
case 3:
q.display();
break;
case 4:
exit(0);
break;
default:
cout<<"Sorry, invalid choice!\n";
break;
}
} while(choice!=4);
return 0;
}

Output-

4. Circular Queue in C/C++

The role of a circular queue comes into play when we wish to avoid the loss of computer memory using arrays. It is based on the principle that the rear end of the queue becomes equal to its front end.

Here is a diagrammatic representation of how a circular queue looks like:

The circular queue operations are the same as that of a linear queue, that is, insertion, deletion and display and checking of boundary conditions such as overflow and underflow.

We have discussed the 3 basic operations in detail:

4.1 Insertion

Insert elements in the circular queue in C

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
}
if (front == -1) //If queue is empty
{
front = rear = 0;
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
if(rear == LIMIT-1) // When rear is at the last position of the queue
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

Insert elements in the circular queue in C++

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
cout<<"Queue Overflow\n";
}
if (front == -1)  // If the queue is empty 
{
front = rear = 0;
}
else
{

cout<<"Enter the element to be inserted in queue: ";
cin>>item);
if(rear == LIMIT-1) // When rear is at the last position of the queue 
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

4.2 Delete

Delete elements in a circular queue in C

void delet()
{
if (front == -1)
{
printf("Queue Underflow\n");
}
printf("Element deleted from queue is : %d\n",cqueue[front]);
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

Delete elements in a circular queue in C++

void delet()
{
if (front == -1)
{
cout<<"Queue Underflow\n";
}
cout<<"Element deleted from queue is: "<< cqueue[front] << endl;
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{	
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

4.3 Display

Display elements in the circular queue in C

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
printf("Queue underflow\n");
}
printf("The elements of the queue are:\n");
if( front_position <= rear_position )
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
}
}

Display elements in the circular queue in C++

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
cout<<"Queue underflow\n";
}
cout<<"The elements of the queue are:\n";
if( front_position <= rear_position )
while(front_position <= rear_position)
{
cout<<cqueue[front_position]<<endl;
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
cout<<cqueue[front_position];
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
cout<<cqueue[front_position]<<endl;
front_position++;
}
}
}

The example of implementation of a circular queue in C

#include<stdio.h>
#include<stdlib.h>
#define LIMIT 10

/* Global declaration of variables */
int cqueue[LIMIT];
int choice, item;
int front, rear; 

void insert(); // Function to insert the element in the queue
void delet(); // Function to delete the element in the queue
void display(); // Function to display the element in the queue

int main()
{

printf("Welcome to DataFlair tutorials!\n\n");

printf ("ARRAY IMPLEMENTATION OF QUEUES\n\n");

front = rear = -1; // It indicates the queue is empty
do
{

printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n\n");
printf("Enter your choice:");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("Sorry, invalid choice!\n");
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
}
if (front == -1)  //If the queue is empty 
{
front = rear = 0;
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
if(rear == LIMIT-1) // When rear is at the last position of the queue 
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

void delet()
{
if (front == -1)
{
printf("Queue Underflow\n");
}
if(front!= -1)
printf("Element deleted from queue is : %d\n",cqueue[front]);
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{	
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
printf("Queue underflow\n");
}
if(front!= -1)
printf("The elements of the queue are:\n");
if( front_position <= rear_position )
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
printf("%d\n",cqueue[front_position]);
front_position++;
}
}
}

Output-

The example of implementation of a circular queue in C++

#include <iostream>
#include <stdlib.h>
#define LIMIT 10
using namespace std;

/* Global declaration of variables */
int cqueue[LIMIT];
int choice, item;
int front, rear; 

void insert(); // Function to insert the element in the queue
void delet(); // Function to delete the element in the queue
void display(); // Function to display the element in the queue

int main()
{

cout<<"Welcome to DataFlair tutorials!"<<endl<<endl;

cout<<"ARRAY IMPLEMENTATION OF QUEUES\n\n";

front = rear = -1; // It indicates the queue is empty
do
{

cout<<"1. Insert\n2. Delete\n3. Display\n4. Exit\n\n";
cout<<"Enter your choice:";
cin>>choice;

switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
cout<<"Sorry, invalid choice!\n";
break;
}
} while(choice!=4);
return 0;
}

void insert()
{
if((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
cout<<"Queue Overflow\n";
}
if (front == -1)  //If the queue is empty 
{
front = rear = 0;
}
else
{
cout<<"Enter the element to be inserted in queue: ";
cin>>item;
if(rear == LIMIT-1) // When rear is at the last position of the queue 
{
rear = 0;
}
else
{
rear++;
}
}
cqueue[rear] = item ;
}

void delet()
{
if (front == -1)
{
cout<<"Queue Underflow\n";
}
if(front!= -1)
cout<<"Element deleted from queue is :"<< cqueue[front] <<endl;
if(front == rear) /* queue has only one element */
{
front = rear = -1;
}
else
{	
if(front == LIMIT-1)
{
front = 0;
}
else
front++;
}
}

void display()
{
int front_position = front;
int rear_position = rear;
if(front == -1)
{
cout<<"Queue underflow\n";
}
if(front!= -1)
cout<<"The elements of the queue are: "<<endl;
if( front_position <= rear_position )
while(front_position <= rear_position)
{
cout<<cqueue[front_position]<<endl;
front_position++;
}
else
{
while(front_position <= LIMIT-1)
{
cout<<cqueue[front_position];
front_position++;
}
front_position = 0;
while(front_position <= rear_position)
{
cout<<cqueue[front_position];
front_position++;
}
}
}

Output-

5. Applications of Queue in C/C++

The principle FIFO followed by queues gives birth to the various applications of queues. Some of the most popular applications of queues are:

• Round robin algorithm: The concept of queues finds a striking application in the round-robin algorithm done in MBA.
• CPU Scheduling: In a queue, the data is not processed instantly, but processed according to the FIFO rule. Therefore, this feature of queues helps in the sharing of resources among multiple users at the same time.
• Input-Output Buffers: It helps in the transmission of asynchronous data (A condition where the retrieval of multiple data takes place at the user end at different rates) by converting it into synchronous data.

6. Quiz on Stacks and Queues in C/C++

7. Summary

Data Structures are an important concept of every programming language. Stacks and Queues in C/C++ are one of the important data structures, which can be understood by real-time examples.

Circular Queue in C/C++ is not a new concept, it is similar to linear queues. Hope, you liked the explanation and can easily implement queues with arrays and linked list.

If you have any queries regarding this topic, feel free to let us know your responses in the comment section below!

Build your Coding skills with these basic C Programs.