Queue using Arrays in C (Implementation) | C Program

November 2, 2023

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

Stack Representation in Java

Representation of a Stack as a Linked List

Infix to Postfix Conversion in java

Infix to prefix conversion in java

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