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

queue

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

#include<stdio.h>
#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.
Array Implementation of Queue Problems in C

The above is solved by using remainder operations as %(maxCapacity)

Array Implementation of Queue Solution

Code

#include<stdio.h>
#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