A queue in C is basically a linear data structure
to store and manipulate the data elements. It follows the order of First In First Out (FIFO).
In queues, the first element entered into the array is the first element to be removed from the array.
For example, let’s consider the scenario of a bus-ticket booking stall. Here, the fashion of a C programming queue is followed. The tickets are distributed on the first-come-first-serve basis i.e. the first one to enter is the first one to be served with the tickets.
A queue is open at both ends. One end is provided for the insertion of data and the other end for the deletion of data.
A queue can be implemented with any programming language such as C, Java, Python, etc.
A queue being an Abstract Data Structure provides the following operations for manipulation on the data elements:
isEmpty()
: To check if the queue is emptyisFull()
: To check whether the queue is full or notdequeue()
: Removes the element from the frontal side of the queueenqueue()
: It inserts elements to the end of the queueFront
: Pointer element responsible for fetching the first element from the queueRear
: Pointer element responsible for fetching the last element from the queueQueue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.
Front
and Rear
pointers keep the record of the first and last element in the queue.Front = -1
and Rear = -1
Queues in C can be implemented using Arrays, Lists, Structures, etc. Below here we have implemented queues using Arrays in C.
Example:
#include <stdio.h>
# define SIZE 100
void enqueue();
void dequeue();
void show();
int inp_arr[SIZE];
int Rear = - 1;
int Front = - 1;
main()
{
int ch;
while (1)
{
printf("1.Enqueue Operation\n");
printf("2.Dequeue Operation\n");
printf("3.Display the Queue\n");
printf("4.Exit\n");
printf("Enter your choice of operations : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("Incorrect choice \n");
}
}
}
void enqueue()
{
int insert_item;
if (Rear == SIZE - 1)
printf("Overflow \n");
else
{
if (Front == - 1)
Front = 0;
printf("Element to be inserted in the Queue\n : ");
scanf("%d", &insert_item);
Rear = Rear + 1;
inp_arr[Rear] = insert_item;
}
}
void dequeue()
{
if (Front == - 1 || Front > Rear)
{
printf("Underflow \n");
return ;
}
else
{
printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
Front = Front + 1;
}
}
void show()
{
if (Front == - 1)
printf("Empty Queue \n");
else
{
printf("Queue: \n");
for (int i = Front; i <= Rear; i++)
printf("%d ", inp_arr[i]);
printf("\n");
}
}
Output:
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue:
10 20
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10
1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue:
20
Stack Data Structure can be used to implement the operations of the queue. We’ll need two stacks to implement a queue using them. Before you work through the examples below, make sure you understand the functioning of stacks very well.
A queue can be implemented using Stacks by either of the following ways:
Let us assume two stacks: S1 and S2 to implement queue operations using the same.
Note: The time complexity of the enqueue operation would be O(n).
Note: The time complexity of the dequeue operation would be O(1).
If you analyze the time complexities of the Enqueue and Dequeue operations using Stack, you’ll find out that the Enqueue operation is much costlier than the Dequeue operation.
Thus, as mentioned above, we make the first entered or the oldest entered element to remain at the top of Stack S1 so that it gets removed when the Dequeue operation is invoked.
Let us again assume two Stacks: S1 and S2 to implement queue operations using the same.
In this article, we have understood the working of queue data structure and have also shadowed over the implementation of queues using stack data structure.
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.
While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.
Sign up for Infrastructure as a Newsletter.
Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.
Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.
Hi, this code doesn’t run because you never defined exit()
- neil