Queue is a linear data structure. It follows First In First Out (FIFO). In other words, the item which is inserted first is accessed/deleted first.
For example, when you go to cashier in a mall, then the person first in line is served first. This is a queue.
Basic Operations:-
- enqueue/push: Insert item in the queue.
- dequeue/pop: pops/deletes an item from the queue.
- peek/front: access the element in front.
Implementation:
- using Array
- using LinkedList
Queue using array
This method is never used for practical purposes.
Steps
- We declare an array que.
- We initialize 2 variables front and rear, front stores the index of the beginning and rear stores index of the end of the queue.
- For enqueue operation, we increment rear and insert data at que[rear].
- For dequeue operation, we increment front.

Code
#include<stdio.h>
/*
First, we declare 4 global variables
que: stores the queue elements
size: maximum size of the que
front: index of first element of que
rear: index of last element of que
*/
int que[100];
int size = 100;
int rear = -1;
int front = 0;
/*
The qneueue(x) function pushes the value 'x' at the end of the queue
If the queue is full, "OverFlow" message is printed on screen else
*/
void enqueue(int x){
// check if queue is full or not
if(rear==size-1){
printf("OverFlow \n");
}
else{
++rear;
que[rear] = x;
}
}
/* returns true if queue is empty */
int isEmpty(){
if(front>rear)
return 1;
else
return 0;
}
/*
Returns front elemnt of the queue
*/
int peek(){
// check if stack is empty or not
if(isEmpty()){
printf("UnderFlow \n");
return -1;
}
else{
return que[front];
}
}
/*
removes front element from the queue
*/
void dequeue(){
// check if stack is empty or not
if(isEmpty()){
printf("UnderFlow \n");
}
else{
printf("%d removed from the queue\n",que[front]);
++front;
}
}
int main()
{
int choice,x;
printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
do{
printf("ENTER YOUR CHOICE: ");
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter data: ");
scanf("%d",&x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
printf("Element at front of queue is: %d\n",peek());
break;
case 4:
if(isEmpty()) printf("Queue is Empty\n");
else printf("Queue is not Empty\n");
}
}while(choice>=1&&choice<=4);
}
Output
1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 150
ENTER YOUR CHOICE: 1
Enter data: 50
ENTER YOUR CHOICE: 2
100 removed from the queue
ENTER YOUR CHOICE: 2
150 removed from the queue
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 300
ENTER YOUR CHOICE: 3
Element at front of queue is: 50
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0
Advantages
- Easy to implement.
- No need to store the address of the next element.
Disadvantages
- Suppose we have an array of size 100. Due to repeated dequeue, enqueue operations, the front and rear become 99. This means there’s only 1 element in the queue. We want to enqueue again. Even tho the array is mostly empty, we won’t be able to enqueue because of rear == size-1.
To perform enqueue, we will need to shift data from the end to the front of the array. This increases the complexity from O(1) to O(N), where N is the size of the array.
To overcome this problem, we use a circular queue.
Queue using LinkedList
Steps
- Initialize 2 nodes, front, and rear. front point to the beginning and rear point to the node at the end of the queue.
- To enqueue,
- Initialize a new node temp.
- Store temp address in the rear.
- Make temp the new rear.
- To dequeue, make the node next to front the new front.

Code
#include<stdio.h>
#include<stdlib.h>
struct node{
int v; // value to be store in queue
struct node *next; // to store address os the next node
};
// points to the top of the stack
struct node *front,*rear;
/*
The push(x) function pushes the value 'x' at the end of the queue
*/
void enqueue(int x){
struct node *temp = (struct node*)malloc(sizeof(struct node));
if(temp==NULL){
printf("failed to allocated memory\n");
return;
}
temp->v = x;
temp->next = NULL;
if(front==NULL){
// this block will run if queue is empty
front = rear = temp;
}
else{
rear->next = temp;
rear = temp;
}
}
/*
Returns front node value of the queue
*/
int peek(){
if(front==NULL){
printf("UnderFlow \n");
return -1;
}
else{
return front->v;
}
}
/*
deletes the front node of the queue
*/
void dequeue(){
if(front==NULL){
printf("UnderFlow \n");
}
else{
printf("%d removed form the queue\n",front->v);
// initialize temp with front node address
node *temp = front;
// Set Top to node just below it
front = front->next;
// release memory of popped element
// since it is no longer of out use
// if memory is not released
// then at one point system will have no memory left
// and operations which may required new memory
// will fail, like creation of new node
free(temp);
}
}
int isEmpty(){
if(front==NULL)
return 1;
else
return 0;
}
int main()
{
front = rear = NULL;
int choice,x;
printf("1 to enqueue\n2 to dequeue\n3 to see front element of queue\n4 to check if queue is empty\n");
do{
printf("ENTER YOUR CHOICE: ");
scanf("%d",&choice);
switch(choice){
case 1:
printf("Enter data: ");
scanf("%d",&x);
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
printf("Element at front of queue is: %d\n",peek());
break;
case 4:
if(isEmpty()) printf("Queue is Empty\n");
else printf("Queue is not Empty\n");
}
}while(choice>=1&&choice<=4);
return 0;
}
Output
1 to enqueue
2 to dequeue
3 to see front element of queue
4 to check if queue is empty
ENTER YOUR CHOICE: 1
Enter data: 100
ENTER YOUR CHOICE: 1
Enter data: 400
ENTER YOUR CHOICE: 1
Enter data: 200
ENTER YOUR CHOICE: 2
100 removed form the queue
ENTER YOUR CHOICE: 2
400 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 200
ENTER YOUR CHOICE: 1
Enter data: 500
ENTER YOUR CHOICE: 2
200 removed form the queue
ENTER YOUR CHOICE: 3
Element at front of queue is: 500
ENTER YOUR CHOICE: 4
Queue is not Empty
ENTER YOUR CHOICE: 0
Advantages
- The number of nodes is equal to the number of elements in the queue. No need to allocated more memory than required, unlike arrays.
- LinkedList can easily grow/shrink.
Disadvantages
- Complex as compared to arrays.
- Extra memory required to store the address of the next node.
Applications
- It is used to implement First Come First Serve (FCFS) algorithms.
- In the operating system, the interrupts of equal priority are served on a first-come basis.
- It is used by some network protocols like Token-Bucket, to handle packets.
References
https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues#Linked_List_Implementation_2