Queue in C Programming

Queues Implementation

A Queue, generally implemented using structures. Generally, the implementation is FIFO i.e. First in First out. A good example would be people standing at a billing counter in a queue, the person who comes first, will be served first

queue

Basic Information about Queues

Queue is FIFO type i.e. First in First out. In queues inserting an item is called as Enqueue and removing an item is called as Dequeue.

As given in the image the following about queues is true – 

Terminologies

  • Enqueue means adding one item to the queue and happens at the rear end of queue
  • Dequeue means removal of one item from the queue and happens at the front end of the queue
  • If the max size of queue is reached then the queue is said to be in Overflow condition
  • If the queue has no items then queue is said to be in Underflow condition
Queue in C Programming
How Queue in C Programming works
#include<stdio.h>
#define SIZE 5

//Basic value initialization
int queue[SIZE], front = -1, rear = -1;

void Enqueue(int val){
if(rear == SIZE-1)
printf("Encountered Overflow Condition\n");
else{
//When adding initial element
if(front == -1)
front = 0;

rear++;
queue[rear] = val;
printf("%d was enqueued\n",val);
}
}
void Dequeue(){
if(front == -1)
printf("Underflow condition\n");
else{
printf("Dequeued : %d\n", queue[front]);
front++;

//resetting the queue when last item is Dequeued
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is empty");
else{
int i;
printf("\nNow, we are printing the Queue :");

for(i=front; i<=rear; i++)
printf("%d ",queue[i]);
}
}

int main()
{
Enqueue(10);
Enqueue(20);
Enqueue(30);
Enqueue(40);


Dequeue();
Dequeue();

display();
return 0;
}

Output

10 was enqueued
20 was enqueued
30 was enqueued
40 was enqueued
Dequeued : 10
Dequeued : 20

Now, we are printing the Queue :30 40
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

// creating a structure to hod the queue
struct myQueue
{
int front, rear;
unsigned size;
//here we have created a pointer which will point to memory of array
//created later in createQueue function
int* array;
};

// initialise the queue
struct myQueue* createQueue(unsigned size)
{
struct myQueue* queue = (struct myQueue*) malloc(sizeof(struct myQueue));
queue->size = size;
queue->front = -1;
queue->rear = -1;

//Memory is created for the array
queue->array = (int*) malloc(queue->size * sizeof(int));
return queue;
}

// Will return true if queue size has reached capacity
int isFull(struct myQueue* queue)
{
if(queue->rear == queue->size -1)
printf("Overflow condition\n");

return (queue->rear == queue->size -1);
}

// Will return true if the queue is empty
int isEmpty(struct myQueue* queue)
{
if(queue->front == -1)
printf("Underflow Condition\n");

return (queue->front == -1);
}

// function to Enqueue in the queue and change relevant values
void enqueue(struct myQueue* queue, int item)
{
if (isFull(queue))
return;

if(queue->front == -1)
queue->front = 0;

queue->rear++;
queue->array[queue->rear] = item;
printf("%d added to the queue\n", item);
}

// Function is dequeue from queue and change relevant values
void dequeue(struct myQueue* queue)
{
if (isEmpty(queue))
return;

int item = queue->array[queue->front];
queue->front++;

//resetting the queue when last item is Dequeued
if(queue->front > queue->rear)
queue->front = queue->rear = -1;
printf("%d dequeued from queue\n", item);
}

//function to display the queue
void display(struct myQueue* queue)
{
if(queue->rear == -1)
printf("\nQueue was Empty!!!");
else{
int i;
printf("\nQueue :\n");

for(i=queue->front; i<=queue->rear; i++)
printf("%d ",queue->array[i]);
}
}

// Main function
int main()
{
struct myQueue* queue = createQueue(5);

enqueue(queue, 5);
enqueue(queue, 15);
enqueue(queue, 25);
enqueue(queue, 35);

dequeue(queue);
dequeue(queue);

display(queue);

return 0;
}

Limitations with Queues in C

Queues in C Problem or limitations with Queue

How to solve the above issue ?

The above issue can be solved in the following ways –

  • Either we can use Circular queues
  • Or modify the code as given below –

The modification in the below code is purely because we are applying remainder operation to size.

That is, for most operations we are doing (value)%size

#include <stdio.h>
#define maxCapacity 5

int queue[maxCapacity], front = -1, rear = -1, currSize = 0;

void enQueue(int data){
if(currSize == maxCapacity)
printf("\nQueue was full can't do insertion");
else{
if(front == -1){
front = currSize = 0;
rear = maxCapacity - 1;
}

rear = (rear + 1)%maxCapacity;
queue[rear] = data;
currSize = currSize + 1;
printf("%d added to the queue at array pos:%d\n", data,rear);
}
}
void deQueue(){
if(currSize == 0)
printf("\n Queue was Empty!!! Couldn't delete");
else{
printf("\nDequeued : %d", queue[front]);

int item = queue[front];
front = (front + 1)%maxCapacity;
currSize = currSize - 1;
printf("\n%d dequeued from queue, new front is at pos:%d\n", item,front);
}
}
void display(){
if(currSize == 0)
printf("\nQueue was Empty!!!");
else{
int i= front, j;
printf("\nQueue :\n");

for(j=0; j<currSize; j++)
printf("%d ",queue[(i+j)%maxCapacity]);
}
}

int main()
{
enQueue(10);
enQueue(20);
enQueue(30);
enQueue(40);

deQueue();
deQueue();

enQueue(50);
enQueue(60);

display();

return
0;
}
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>

// Basic struct for queue
struct Queue
{
int front, rear, currSize;
unsigned maxCapacity;
// we are storing string in integer array, this will not give error
// as values will be stored in ASCII and returned in ASCII thus, returned as string again
int* array;
};

// Here we initialize queue and init. Current size of queue to 0
struct Queue* createQueue(unsigned maxCapacity)
{
struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
queue->maxCapacity = maxCapacity;
queue->front = queue->currSize = 0;
queue->rear = maxCapacity - 1; // This is important, see the enqueue
queue->array = (int*) malloc(queue->maxCapacity * sizeof(int));
return queue;
}

// Will return true if queue Current size has reached maxCapacity
int isFull(struct Queue* queue)
{
if(queue->currSize == queue->maxCapacity)
printf("Can't insert as queue is full\n");

return (queue->currSize == queue->maxCapacity);
}

// Will return true if queue Current size is 0
int isEmpty(struct Queue* queue)
{
if(queue->currSize == 0)
printf("Can't deuque as queue is empty\n");
return (queue->currSize == 0);
}

// Here we add new item to queue and change rear and Current size
void enqueue(struct Queue* queue, int item)
{
if (isFull(queue))
return;

//Bcz, queue->rear is set up to maxCapacity adding + 1
//and % maxCapacity will set rear to start of queue

//enqueue happens at the rear value always so to maintain First in first out
queue->rear = (queue->rear + 1)%queue->maxCapacity;
queue->array[queue->rear] = item;
queue->currSize = queue->currSize + 1;
printf("%d added to the queue at array pos:%d\n", item,queue->rear);
}

// Here we remove or dequeue from queue and
//also change the front value and Current size of queue

void dequeue(struct Queue* queue)
{
if (isEmpty(queue))
return;
int item = queue->array[queue->front];
queue->front = (queue->front + 1)%queue->maxCapacity;
queue->currSize = queue->currSize - 1;
printf("\n%d dequeued from queue, new front is at pos:%d\n", item,queue->front);
}

void display(struct Queue* queue)
{
if(queue->currSize == 0)
printf("\nQueue was Empty!!!");
else{
int i=queue->front, j;
printf("\nQueue :\n");

for(j=0; j<queue->currSize; j++)
printf("%d ",queue->array[(i+j)%queue->maxCapacity]);
}
}
// Main function to run queue program
int main()
{
struct Queue* queue = createQueue(5);

enqueue(queue,10);
enqueue(queue,20);
enqueue(queue,30);
enqueue(queue,40);


dequeue(queue);
dequeue(queue);

enqueue(queue,50);
enqueue(queue,60);

display(queue);
return 0;
}