Noran Saber Abdelfattah · Follow
19 min read · Jun 19, 2023
--
A queue is a linear data structure in the C language that adheres to the FIFO (First In, First Out) rule. Arrays or linked lists can be used to implement it statically or dynamically. In the array implementation, items are added to the back of the queue and removed from the front. Both the insertion and deletion operations look for overflow and underflow circ*mstances, respectively. The queue’s components can also be printed via a display operation. Memory is dynamically allocated for each entry in the linked list implementation, and the insertion and deletion operations have a similar course. However, there is no queue overflow condition for linked lists. Data processing is made efficient by knowing how queues are implemented in C.
- Consider yourself in a queue to purchase a movie ticket. The way the queue is set up is known as the queue. The person who comes first in this queue gets to purchase their ticket first. This indicates that the person in front of the queue will receive service first.
- A queue in C is nothing more than a linear data structure that adheres to the FIFO principle (First In, First Out). The front is used for deletion, and the back is used for insertion.
- Let’s now compare this queue idea to a C computer language data structure. Similar to the queue for movie tickets, a queue in C is a mechanism to arrange data components. The same as the wait for movie tickets, it adheres to the “First In, First Out” (FIFO) principle.
- An element moves to the rear of the queue when you add it to the queue. Technically speaking, this is referred to as insertion, and it takes place towards the back of the queue. An element is taken from the front of the queue when it is removed from the queue. The first person to join the line will also be the first to depart, which is the basic tenet of deletion.
- In C, a queue is a linear data structure that works similarly to a ticket queue in that you may add components from the rear and remove them from the front. It’s an easy method for processing data in a certain order.
- Statically: The construction of queues as arrays enables the allocation of their data components to static memory. It is significant to notice that the queue obtains all of the characteristics of an array using this way.
- Dynamically: Queues are implemented as linked lists that use dynamic memory allocation for their data components. It’s crucial to remember that the queue in this technique acquires all the traits of a linked list.
- Key learnings: In C, queues and stacks can both be static or dynamic depending on how they are implemented.
- Prior to the program running, it is crucial to ascertain the queue’s size.
Insertion
Insertion of elements into the queue takes place from the rear end. Inserting an element into the queue is also called enqueue.
Example
#include <stdio.h>
#define LIMIT 100void insert() {
int element;
if (rear == LIMIT - 1) {
printf("Queue Overflow\n");
} else {
if (front == -1) {
front = 0;
}
See AlsoQueue Data Structure - GeeksforGeeksQueue in C - GeeksforGeeksCreating a Queue in C | DigitalOceanC Program to Implement Queue using Array - GeeksforGeeks printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
rear++;
queue[rear] = element;
}
}
The “element” variable is first declared in the method to hold the value that will be added to the queue.
The program examines if the variable “rear” equals the value of the constant “LIMIT — 1”. Check if the queue is full of elements and you can’t add more.
If the condition is satisfied, no further components can be added to the queue because it is already full. In this instance, the queue is full and no insertions are permitted, thus the code shows the message “Queue Overflow” to highlight this.
If the condition in step 2 is false, the queue is not full, and the code moves on to the “else” loop.
The code examines if the variable “front” is equal to -1 inside the “else” clause. To determine whether the queue is empty, apply this condition. If the condition is satisfied, the queue will be empty and this element will be added first. The code then sets the value of “front” to 0 in that situation. The front index of the queue must be initialised in this phase.
The function asks the user to input the element to be added into the queue after initialising the front index (if necessary). On the screen, it says, “Enter the element to be inserted in the queue: “
The “scanf” function is used in the code to read user input and save it in the variable “element”.
The rear index is then moved to the following open spot in the queue by incrementing the value of “rear” by 1.
The updated “rear” index is used to determine where in the queue the value “element” should be assigned. The element is essentially added to the queue in this stage.
The act of eliminating data components in a queue is done from the front. Dequeue is a frequent name for this process. When an element is dequeued from a queue, the item at the front of the queue is removed to make a place for the element that is next in line to be accessed or deleted.
Example
void delet()
{
if (front == - 1 || front > rear)
{
printf("Stack Underflow");
}
else
{
printf("The deleted element in the queue is: %d\n", queue[front]);
front++;
}
}
The first test determines if the variable front is bigger than the rear or equal to -1.
When the front has a value of -1, the queue is usually empty,
when the front exceeds the rear, all elements have been removed from the queue. There are no entries in the queue to remove if either of these conditions is true.
The function outputs “Queue Underflow” in certain circ*mstances to show that the queue is empty and the deletion cannot be completed.
The else block is reached if the first condition is false (the queue is not empty). When there are items in the queue, this block is carried out.
The line front++; increases the value of front by 1 after printing the element.
By pushing the front pointer one place ahead, this action essentially removes the element from the queue.
To sum up, the delet() method determines whether or not the queue is empty. In the event that it is not empty, it deletes the element at the head of the queue and advances the front pointer. A “Queue Underflow” notice indicates that no elements may be removed if the queue is empty.
Display
The display according to FIFO😎 for men it’s FIFO, not FIFA😂😂
Example
void display()
{
int i; if (front == -1)
{
printf("Queue Underflow");
}
else
{
printf("The elements of the queue are:\n");
for (i = 0; i < rear; i++)
{
printf("%d\n", queue[i]);
}
}
}
print “Queue underflow” if the queue is empty and we check this condition by front -1.
The code moves on to the else block if the queue is not empty (i.e., the front is not -1). When there are items in the queue, this block is carried out. The message “The elements of the queue are:n” is simply shown with the line printf(“The elements of the queue are:n”);.
The queue members are iterated over in the for loop for (i = front; i = rear; i++) starting from the front and going all the way to the rear. To access the items in the queue array, it employs the loop counter I.
The line printf(“%dn”, queue[i]); within the loop publishes each element of the queue on a separate line.
Example
#include <stdio.h>
#include <stdlib.h>#define LIMIT 100 // Max limit of the queue elements
// Global Variables
int queue[LIMIT]; // Array implementation of the queue
int front = -1, rear = -1; // Front and rear pointers
int choice;
// Function prototypes
void insert();
void delet();
void display();
int main() {
printf("Array implementation of a queue\n");
do {
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\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);
default:
printf("Invalid choice! Please try again.\n");
}
} while (choice != 4);
return 0;
}
void insert() {
int element;
if (rear == LIMIT - 1) {
printf("Queue Overflow\n");
} else {
printf("Enter the element to be inserted in the queue: ");
scanf("%d", &element);
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = element;
printf("Element %d has been inserted into the queue.\n", 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() {
if (front == -1) {
printf("Queue is empty.\n");
} else {
printf("Elements of the queue are:\n");
for (int i = front; i <= rear; i++) {
printf("%d\n", queue[i]);
}
}
}
The maximum number of elements that may be stored in the queue is specified by the code’s definition of the constant LIMIT, which has a value of 100.
Declares global variables: queue: A queue will be implemented using an array.
Front and rear: Indicates the front and back of the queue via pointers. Initially, they are set to -1, which denotes an empty queue.
the choice is a variable used to hold the user’s menu selections.
Three operations on the queue are defined in the code: insert(), delet(), and show(). Later in the code, these functions will be defined.
The main() function, which is where the program starts, has been declared. “Array implementation of a queue” is presented as the opening message. Up until the user decides to quit, the menu is shown periodically and actions are taken on the queue using a do-while loop.
The menu selections are shown inside the loop, and the user is prompted to input their selection using the scanf() method. To respond to the user’s selection,
A switch statement is employed:
The insert() method is used to add an element to the queue if option 1 is selected.
The delet() method is used to remove an element from the queue if option number two is selected.
The display() method is invoked to display the queue’s components if option 3 is selected.
If option 4 is selected, the program ends using exit(0). An error message is shown if none of the options are selected.
the definition of the insert() function It checks to see if the back of the line is at its maximum length. If so, “Queue Overflow” is printed by the function since the queue is full.
The user is prompted to input the element to be inserted if the queue is not full. It is set to 0 if the front is -1, which denotes an empty queue.
The inputted element is placed at the rear position in the queue array after the rear is incremented. Printing a success message follows.
the definition of the delet() function It determines if the front is zero or more than the back, which denotes an empty line. If true, “Queue Underflow” is printed.
The element at the front position is displayed as the deleted element and front is increased to remove the element from the queue if the queue is not empty.
Display() is defined as follows: It examines if the front is -1, which denotes an empty queue. If true, “Queue is empty” is printed. If there are any elements in the queue, it displays “Elements of the queue are:” and then loops over the queue array, printing each element as it goes.
Output
- As we’ve just mentioned, linked lists enable the queue’s data items to be dynamically allocated memory. As a result, the queue size is decided while the programme is running and does not need to be predetermined.
- The three fundamental queueing operations — Insertion, Deletion, and Display — follow the same pattern as the array implementation.
- It is significant to note that the linked list implementation of queues does not support the circ*mstance of queue overflow, and the size of the stack is not predetermined. The queue underflow condition, however, is still valid.
We can add items to the queue in this way:
Example
void insert()int ele
struct node *temp = malloc(sizeof(struct node*));
if (temp == NULL)
{
return NULL
}
printf("Please enter an elements: ");
scanf("%d", $ele);
temp->data = ele;
temp->link = NULL;
if (rear == NULL)
{
front = rear = temp;
}
else
{
rear->link = temp;
rear = temp;
}
}
The first line of the insert() method declares the variable ele, which will hold the user-inputted element.
Then, a temp pointer variable of type struct node* is declared. To retain the entered element, a new node will be made using this reference.
To allow memory for the new node, the malloc() method is used. The size of the structure is calculated using the size of (struct node*).
The function returns NULL if the memory allocation fails (i.e., if the temp is NULL).
The code then asks the user to enter an element using the printf() function to show the prompt message if the memory allocation process was successful. An integer should be entered, as indicated by the%d format specifier.
The user-inputted element is read by the scanf() method and stored in the ele variable. The ele variable’s address is obtained using the & operator so that scanf() may save the value there.
Using the temp->data syntax, the code inserts the value of ele into the data field of the newly constructed node.
The newly generated node’s link field is set to NULL to signify that it is the final node in the linked list.
The rear pointer is then checked to see if it’s NULL, which denotes an empty linked list.
The presence of nodes indicates that the linked list is not empty. In this instance, the newly constructed node (temp) is referred to in the link field of the existing rear node. The new node is then made the new final node in the linked list by updating the rear pointer to point to it as well.
Delete
Example
void dele()
{
struct node* temp; // Declare a temporary pointer variable
temp = front; // Assign the value of front pointer to temp if (front == NULL) // Check if the queue is empty (front is NULL)
{
printf("Queue Underflow");
// Set front and rear pointers to NULL to indicate an empty queue
front = rear = NULL;
}
else
{
// Print the value of the data in the front node
printf("The deleted element is: %d\n", front->data);
// Move the front pointer to the next node in the queue
front = front->link;
// Deallocate the memory occupied by the previous front node
free(temp);
}
}
Display
Example
void display()
{
counter = 0;
struct node* temp;
temp = front; if (front == NULL) // Check if the queue is empty (front is NULL)
{
printf("Queue Underflow");
}
else
{
printf("The queue elemtns are: %d\n");
while (temp) // Loop through the nodes until temp becomes NULL
{
// Print the value of data in the current node
printf("%d", temp->data);
temp = temp->link; // Move to the next node in the queue
counter++; // Increment the counter variable
}
}
}
Complete code
#include <stdio.h>
#include <stdlib.h>struct node
{
int data;
struct node *link;
} *front, *rear;
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 the 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 queue are:\n");
while (temp)
{
printf("%d\n", temp->data);
temp = temp->link;
cnt++;
}
}
}
The code constructs a structure node that represents a node in the queue and includes the required header files. Each node has a pointer link to the following node as well as an int data field.
There are defined function prototypes for show(), delete (), and insert().
The method is main() is defined. A welcome message is shown, and the user can select from a menu of queue activities. It constantly asks for user input using a do-while loop until option 4 (exit) is shown.
Delet() is a defined function. It eliminates the queue’s first element. By confirming that the front is NULL, it first determines whether the queue is empty. It displays the front node’s contents, changes the front pointer to refer to the next node, and releases the memory of the prior front node if the queue is not empty.
Display() is a specified function. It moves through the queue and shows every component. By confirming that the front is NULL, it determines whether the queue is empty.
If the queue is not empty, it begins at the front node and iterates through the linked list, outputting the contents of each node and changing the temporary reference so that it points to the subsequent node.
Output
A circular queue is a type of data structure that depicts a queue where the last and first elements are linked. We may take advantage of the vacant spaces left over after dequeuing items thanks to this circular link. In other words, it creates a circular loop that effectively utilises the RAM that is available.
Structure: An array with front and rear pointers makes up a circular queue. The queue’s contents are stored in an array, and the front and rear pointers identify the first and last elements in the queue, respectively.
Circular Connection: The back pointer of a circular queue can wrap around to the beginning of the array, unlike a conventional linear queue. We may make use of the vacant spaces left over after dequeuing items thanks to this circular link.
Empty Queue: Initially, the front and rear points are both set to -1 when the circular queue is empty.
Full Queue: The rear pointer is one spot behind the front pointer when the circular queue is full. We can distinguish between an empty queue and a filled queue using this criterion.
Enqueue Operation: The rear pointer is increased, and the new element is then positioned there to be added to the circular queue (enqueue operation). The rear pointer loops around to the beginning of the array if it approaches the end of the array (circular behaviour).
Dequeue Operation: We raise the front pointer and fetch the element from that location in order to remove an element from the circular queue (dequeue operation). The front pointer will circle back to the beginning of the array if it reaches the end of the array (circular behaviour).
Overflow and Underflow: When the front pointer catches up to the rear pointer, overflow occurs, signifying that the circular queue is filled. When the front pointer is greater than the rear pointer, underflow occurs and the circular queue is empty.
Handling Overflow: We may either refuse the enqueue process and show an overflow notice to handle overflow or dynamically expand the array to fit more entries.
Handling Underflow: We can show an underflow notification when a dequeue operation is attempted on an empty circular queue in order to address underflow.
Insertion
Example
void insert()
{
// Check if the circular queue is full
if ((front == 0 && rear == LIMIT-1) || (front == rear+1))
{
printf("Queue Overflow\n");
// We need this step to prevent inserting elements when the circular queue is already full.
} // Check if the circular queue is empty
if (front == -1)
{
front = rear = 0;
// If the queue is empty, set both front and rear pointers to 0, indicating the first element.
}
else
{
printf("Enter the element to be inserted in queue: ");
scanf("%d", &item);
// Check if the rear pointer is at the last position of the queue
if (rear == LIMIT-1)
{
rear = 0;
// If the rear pointer is at the last position, wrap around to the beginning of the queue.
}
else
{
rear++;
// Move the rear pointer to the next position.
}
}
cqueue[rear] = item;
// Insert the element at the current rear position of the circular queue.
}
The circular queue can have elements added to it using the method insert(). The circular queue’s capacity is checked in the first if condition.
The circular queue is full and cannot take any more items if the front pointer is at the first position and the rear pointer is at the final position, or if the front pointer is ahead of the rear pointer by one place. In this situation, the function terminates and shows a “Queue Overflow” notice.
A second if statement determines whether the circular queue is empty. The queue is empty if the front pointer is set to -1. In this instance, we indicate the initial element location in the queue by setting the front and rear pointers to 0.
The function asks the user to input the element to be inserted if the circular queue is not empty.
The else block’s if condition determines if the rear pointer is at the last position of the queue. In order to make use of the available space, if the rear pointer is at the final position, it wraps around to the beginning of the queue (position 0).
The function moves to the next place in the queue by incrementing the rear pointer if it is not already at the last position.
The user-entered element is then allocated to the circular queue’s current back position.
Deletion
Example
void delet()
{
// Check if the circular queue is empty
if (front == -1)
{
printf("Queue Underflow\n");
// We need this step to prevent deleting elements when the circular queue is empty.
} printf("Element deleted from queue is: %d\n", cqueue[front]);
// Print the element being deleted from the front of the circular queue.
// Check if the queue has only one element
if (front == rear)
{
front = rear = -1;
// If the queue has only one element, set both front and rear pointers to -1, indicating an empty queue.
}
else
{
// Check if the front pointer is at the last position of the queue
if (front == LIMIT-1)
{
front = 0;
// If the front pointer is at the last position, wrap around to the beginning of the queue.
}
else
{
front++;
// Move the front pointer to the next position.
}
}
}
The circular queue member can be removed using the method delet(). The if statement determines whether the circular queue is empty.
The queue cannot be used for any delete operations if the front pointer is set to -1, which indicates that it is empty. In this situation, the function terminates and shows a “Queue Underflow” notice.
The function prints the element being eliminated from the front of the circular queue if the queue is not empty.
The else block’s if condition determines if the queue has just one element. The queue only contains one member if the front and rear pointers are equal. In this instance, we indicate an empty queue by setting the front and rear points to 1.
The function determines if the front pointer is at the last position of the queue if there are several elements in the queue. If the front pointer is in the final place in the queue, it moves to the first position in the queue (position 0).
The function moves to the next place in the queue by incrementing the front pointer if it is not already at the last position.
Display
Example
void display()
{
int front_position = front;
int rear_position = rear; // Check if the circular queue is empty
if (front == -1)
{
printf("Queue underflow\n");
// We need this step to prevent displaying elements when the circular queue is empty.
}
printf("The elements of the queue are:\n");
// Check the position of the front and rear pointers
if (front_position <= rear_position)
{
// Loop through the elements from front to rear
while (front_position <= rear_position)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
}
else
{
// Loop through the elements from front to the last position in the queue
while (front_position <= LIMIT-1)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
front_position = 0; // Reset the front position to the beginning of the queue
// Loop through the elements from the beginning to the rear position
while (front_position <= rear_position)
{
printf("%d\n", cqueue[front_position]);
front_position++;
}
}
}
Explanation
The circular queue’s items are all shown in accordance with the FIFO rule by the function display().
The values of the front and rear pointers are used to initialise the variables front_position and rear_position, respectively.
The if statement determines whether the circular queue is empty. The queue is empty and there are no entries to display if the front pointer is set to -1. In this situation, the function terminates and shows a “Queue underflow” notice.
The function writes a message stating that it will reveal the queue’s contents if the queue is not empty.
The location of the front and rear pointers is checked in the following if statement. The items are stored progressively from front to rear if the front position is less than or equal to the rear position.
The function then begins a loop that iterates from the front position to the back position in this situation. Each element at the current place is printed during the loop.
The items wrap around from the end of the queue to the beginning if the front position is greater than the rear position.
In this instance, the function begins the first loop, which iterates over the queue’s positions from first to last (LIMIT-1). Each element at the current place is printed during the loop.
The front position is reset to 0 to wrap around to the queue’s start after reaching the final spot in the line.
The second loop, which iterates from the front of the queue to the back, is then entered by the function. Each iteration of the loop
For Stack check this link:
Conclusion
sticking to the FIFO rule. It offers insertion, deletion, and display actions, and it may be done using arrays or linked lists. The array implementation addresses overflow and underflow problems but requires that the queue size be specified in advance. On the other hand, the linked list approach does not have an overflow condition and allows for dynamic memory allocation. You can organise and process data in a sequential way with efficiency if you comprehend the ideas behind and how queues are implemented in C.
Sincerely, Noran❤️
