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