Queue using Arrays in C (Implementation) | C Program
Using just Arrays to implement Queues
Generally, we use structures with supporting arrays to implement queues. However, queues can also be implemented using arrays, while this is not a sensical way to implement queues and structures must be used to implement in C. But let us look at the program
How Queues work ?
You can think of queues as a queue of people at airport ticket counter. The first person to enter the queue is served by the air hostess at ticket counter first, the last person to enter is served last. Which is why Queues are called as First in First out (FIFO) system or Last in Last out system(LILO)
The following are terminologies used in Queue Array implementation –
- Front – The item at the front of the queue is called front item
- Rear – The item at the end of the Queue is called rear item
- Enqueue – Process of adding or inserting a new item in the queue is called as Enqueing
- Dequeueing – Process of removing or deleting an existing item from the queue is called as dequeueing
- Size – The max size of the queue is called as size an is initialised when the queue is created
- currSize – The size of queue at any given time is notated as currSize.
C Program to Implement Queues using Arrays
Run
#include
#define SIZE 5
//Basic value initialisation
int queue[SIZE], front = -1, rear = -1;
//Function created to handle enqueue
void enqueue(int item){
if(rear == SIZE-1){
printf("Can't enqueue as the queue is full\n");
}
else{
//The first element condition
if(front == -1){
front = 0;
}
rear = rear + 1;
queue[rear] = item;
printf("We have enqueued %d\n",item);
}
}
//Function created to handle dequeue
void dequeue(){
if(front == -1){
printf("Can't dequeue as the queue is empty\n");
}
else{
printf("We have dequeued : %d\n", queue[front]);
front = front + 1;
//Only happens when the last element was dequeued
if(front > rear){
front = -1;
rear = -1;
}
}
}
//function to print the queue
void printQueue(){
if(rear == -1)
printf("\nUnable to display as queue is empty");
else{
int i;
printf("\nThe queue after enqueue & dequeue ops looks like :");
for(i = front; i <= rear; i++)
printf("%d ",queue[i]);
}
}
int main()
{
//enqueue begins here
enqueue(2);
enqueue(4);
enqueue(6);
enqueue(8);
//dequeue beings here
dequeue();
dequeue();
printQueue();
return 0;
}Output –
We have enqueued 2 We have enqueued 4 We have enqueued 6 We have enqueued 8 We have dequeued : 2 We have dequeued : 4 The queue after enqueue & dequeue ops looks like :6 8
Problem with simple implementation of Queue using Arrays
The simple implementation of queues faces a unique problem
- Whenever we do simultaneous enqueue or dequeue in the queue.
- The effective size of queue is reduced
- This can be solved once all the elements are dequeued and values of front and rear are again put back to -1.
Alternative way
Another way of solving this is either by circular queues or tweak in implementation as given in the code below -
The above is solved by using remainder operations as %(maxCapacity)
Code
Run
#include
#define maxCapacity 5
int queue[maxCapacity], front = -1, rear = -1, currSize = 0;
void enQueue(int data){
if(currSize == maxCapacity)
printf("\nMax Size reached can't do enqueue");
else{
if(front == -1){
front = currSize = 0;
rear = maxCapacity - 1;
}
//imagine scenario where enqueue is happening at last element of queue
//if some dequeue has happened then 0th element or others may be free
//using % operation we can now enter at 0th or others positions here
rear = (rear + 1)%maxCapacity;
queue[rear] = data;
currSize = currSize + 1;
printf("%d Successfully Enqueued at array pos:%d\n", data,rear);
}
}
void deQueue(){
if(currSize == 0)
printf("\nNo elements, queue is empty can't dequeue");
else{
printf("\nDequeued : %d", queue[front]);
int item = queue[front];
front = (front + 1)%maxCapacity;
currSize = currSize - 1;
printf("\n%d Successfully dequeued & changed front value which is: at pos:%d\n", item,front);
}
}
void display(){
if(rear == -1)
printf("\nQueue was Empty!!!");
else{
int i;
printf("\nQueue :\n");
for(i=front; i<=rear; i++)
printf("%d ",queue[i]);
}
}
int main()
{
enQueue(2);//front: a[0], rear: a[0]
enQueue(4);//front: a[0], rear: a[1]
enQueue(6);//front: a[0], rear: a[2]
enQueue(8);//front: a[0], rear: a[3]
//front: a[0], rear: a[3]
deQueue();//0th pos now empty, //front: a[1], rear: a[3]
deQueue();//1st pos now empty, //front: a[2], rear: a[3]
//note the explanation in the above image starts from here
enQueue(10);//front: a[2], rear: a[4]
//front: a[2], rear: a[4]
//rear = (rear + 1)%maxCapacity; a[rear] = data;
//rear = (4 + 1)%maxCapacity; i.e. rear = 5%5 = 0, thus, a[0] = 12;
enQueue(12);//front: a[2], rear: a[0]
enQueue(14);//front: a[2], rear: a[1]
deQueue();//2nd pos now empty, front: a[3], rear: a[1]
enQueue(14);//front: a[3], rear: a[2]
return 0;
}
Output
2 Successfully Enqueued at array pos:0 4 Successfully Enqueued at array pos:1 6 Successfully Enqueued at array pos:2 8 Successfully Enqueued at array pos:3 Dequeued : 2 2 Successfully dequeued and changed front value which is: at pos:1 Dequeued : 4 4 Successfully dequeued & changed front value which is: at pos:2 10 Successfully Enqueued at array pos:4 12 Successfully Enqueued at array pos:0 14 Successfully Enqueued at array pos:1 Dequeued : 6 6 Successfully dequeued & changed front value which is: at pos:3 14 Successfully Enqueued at array pos:2
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment