Implement Queue Data Structure using C programming language

You can watch me live-code this data-structure on YouTube for better understanding.You can read the text and follow the video with it for clear understanding.

A queue is an abstract Data-Structure where, a data item is inserted or added at one end.

And, data item is removed from other end.

To keep track of two openings, one for insertion and other for deletion. We keep two variables for that. We also keep a constant to keep track of maximum size of the queue.

And, we have created a struct to hold these variables and an array of integers to hold our data.

//First In First Out
struct Queue {
    int_least8_t frontIndex;
    int_least8_t rearIndex;
    uint_least8_t maxCapacity;
    int           data[];
};

I have created the function definitions that I will implement later on.

//Create Stack - Allocate Memory for stack
extern struct Queue *createQueue(int *capacity);

//Free Memory - Delete Queue from memory
extern void deleteQueue(struct Queue *queue);

//Status Check functions
extern int numberOfItemsInQueue(struct Queue *queue);
extern bool isQueueFull(struct Queue *queue);
extern bool isQueueEmpty(struct Queue *queue);

//Data modification functions
extern int  putInQueue(struct Queue *queue, int *data);
extern int  removeFromQueue(struct Queue *queue);

In the function created below, we allocate memory and initialize the values.

//Creation is done
struct Queue *createQueue(int *capacity){
    struct Queue *queue;
    queue = (struct Queue *) malloc((sizeof *queue) + (sizeof(int) * *capacity));

    if(queue != NULL) {
       queue->frontIndex = queue->rearIndex = -1; 
       queue->maxCapacity = *capacity; 
    }

    return queue;
}

In the function created below, we use c standard library free-function to remove memory allocation.

//Deletion of Queue
void deleteQueue(struct Queue *queue){
    if(queue == NULL) return;
    free(queue);
}

In the function created below, we check that the number of elements is equal to the maximum capacity of the queue.

//Check Status
bool isQueueFull(struct Queue *queue){
    return queue == NULL || numberOfItemsInQueue(queue) == queue->maxCapacity;
}

In the function created below, we check that the value of the frontIndex or rearIndex is less than zero, then the queue is empty.

bool isQueueEmpty(struct Queue *queue){
    return queue == NULL || queue->frontIndex < 0;
}

In the function created below, we add new value in the queue, iff the queue is not full

//Data modifications
int putInQueue(struct Queue *queue, int *data){
    if(isQueueFull(queue)) return EOF;
    
    ++queue->rearIndex;

    if(queue->frontIndex < 0) queue->frontIndex = queue->rearIndex;
    else if(queue->rearIndex == queue->maxCapacity) queue->rearIndex = 0;

    queue->data[queue->rearIndex] = *data;
    return queue->data[queue->rearIndex];
}

In the function created below, we remove a value from queue, iff the queue is not empty

int removeFromQueue(struct Queue *queue){
   if(isQueueEmpty(queue)) return EOF;

   int data = queue->data[queue->frontIndex];

   if(queue->frontIndex == queue->rearIndex) queue->frontIndex = queue->rearIndex = -1;
   else if(queue->frontIndex + 1 == queue->maxCapacity) queue->frontIndex = 0;
   else ++queue->frontIndex;

   return data;
}

We have a utility function to find the total number of items in Queue.

int numberOfItemsInQueue(struct Queue *queue){
    if(queue->frontIndex < 0) return 0;
    if(queue->frontIndex <= queue->rearIndex)  return (queue->rearIndex - queue->frontIndex) + 1;
    
    //when front Index is greater than rear index
    return (queue->maxCapacity - queue->frontIndex) + queue-> rearIndex + 1;
}

We have utility function to print the elements in the queue. And, we have to handle three different cases.

if the frontIndex is less than rearIndex, then print all elements from frontIndex to rearIndex.
if frontIndex is greater than rearIndex, then print all elements from frontIndex till the end of array, and then print all elements from start of array to rearIndex.
if frontIndex is equal to rearIndex, then just print that one element, because right now only one element is there in the queue.

void printQueue(struct Queue *queue){
      if(isQueueEmpty(queue)) return;
      if(queue->frontIndex < queue->rearIndex) {
          int index = queue->frontIndex;
      while(index <= queue->rearIndex) printf("%d ", queue->data[index++]); 
      } else if(queue->frontIndex > queue->rearIndex) {
          int index = queue->frontIndex;
      int endIndex = queue->maxCapacity - 1;
      while(index <= endIndex) printf("%d ", queue->data[index++]); 

      index = 0;
      endIndex = queue->rearIndex;
      while(index <= endIndex) printf("%d ", queue->data[index++]); 
      } else {
            printf("%d ", queue->data[queue->frontIndex]);
      }
      printf("\n");
}

Entire Code for Header File

#include<stdio.h>
#include<stdlib.h> //malloc and free
#include<stdbool.h> // we get bool and true and false
#include<stdint.h> 

//First In First Out
struct Queue {
    int_least8_t frontIndex;
    int_least8_t rearIndex;
    uint_least8_t maxCapacity;
    int           data[];
};

//Create Stack - Allocate Memory for stack
extern struct Queue *createQueue(int *capacity);

//Free Memory - Delete Queue from memory
extern void deleteQueue(struct Queue *queue);

//Status Check functions
extern int numberOfItemsInQueue(struct Queue *queue);
extern bool isQueueFull(struct Queue *queue);
extern bool isQueueEmpty(struct Queue *queue);

//Data modification functions
extern int  putInQueue(struct Queue *queue, int *data);
extern int  removeFromQueue(struct Queue *queue);

Entire Code For C-source file

#include "Queue.h"

//Creation is done
struct Queue *createQueue(int *capacity){
    struct Queue *queue;
    queue = (struct Queue *) malloc((sizeof *queue) + (sizeof(int) * *capacity));

    if(queue != NULL) {
       queue->frontIndex = queue->rearIndex = -1; 
       queue->maxCapacity = *capacity; 
    }

    return queue;
}

//Deletion of Queue
void deleteQueue(struct Queue *queue){
    if(queue == NULL) return;
    free(queue);
}

int numberOfItemsInQueue(struct Queue *queue){
    if(queue->frontIndex < 0) return 0;
    if(queue->frontIndex <= queue->rearIndex)  return (queue->rearIndex - queue->frontIndex) + 1;
    
    //when front Index is greater than rear index
    return (queue->maxCapacity - queue->frontIndex) + queue-> rearIndex + 1;
}
//Check Status
bool isQueueFull(struct Queue *queue){
    return queue == NULL || numberOfItemsInQueue(queue) == queue->maxCapacity;
}

bool isQueueEmpty(struct Queue *queue){
    return queue == NULL || queue->frontIndex < 0;
}

//Data modifications
int putInQueue(struct Queue *queue, int *data){
    if(isQueueFull(queue)) return EOF;
    
    ++queue->rearIndex;

    if(queue->frontIndex < 0) queue->frontIndex = queue->rearIndex;
    else if(queue->rearIndex == queue->maxCapacity) queue->rearIndex = 0;

    queue->data[queue->rearIndex] = *data;
    return queue->data[queue->rearIndex];
}

int removeFromQueue(struct Queue *queue){
   if(isQueueEmpty(queue)) return EOF;

   int data = queue->data[queue->frontIndex];

   if(queue->frontIndex == queue->rearIndex) queue->frontIndex = queue->rearIndex = -1;
   else if(queue->frontIndex + 1 == queue->maxCapacity) queue->frontIndex = 0;
   else ++queue->frontIndex;

   return data;
}

void printIndices(struct Queue *queue){
    if(queue != NULL) printf("Front Index %d, Rear Index %d.\n", queue->frontIndex, queue->rearIndex);
}

void printQueue(struct Queue *queue){
      if(isQueueEmpty(queue)) return;
      if(queue->frontIndex < queue->rearIndex) {
          int index = queue->frontIndex;
      while(index <= queue->rearIndex) printf("%d ", queue->data[index++]); 
      } else if(queue->frontIndex > queue->rearIndex) {
          int index = queue->frontIndex;
      int endIndex = queue->maxCapacity - 1;
      while(index <= endIndex) printf("%d ", queue->data[index++]); 

      index = 0;
      endIndex = queue->rearIndex;
      while(index <= endIndex) printf("%d ", queue->data[index++]); 
      } else {
            printf("%d ", queue->data[queue->frontIndex]);
      }
      printf("\n");
}

void main(){
    int capacity = 4;
    struct Queue *queue = createQueue(&capacity);
    if(queue != NULL) printf("Queue Created.\n");
     
     printIndices(queue);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));
     int data = 11;
     putInQueue(queue,  &data);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));

     data = 14;
     putInQueue(queue,  &data);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));
     data = 12;
     putInQueue(queue,  &data);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));
     data = 13;
     putInQueue(queue,  &data);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));
    printQueue(queue);
    removeFromQueue(queue);
     printf("Number Of Items in Queue %d.\n", numberOfItemsInQueue(queue));
    printQueue(queue);
    deleteQueue(queue);
    queue = NULL;
}

Refactored Codes

Implement Queue Data Structure using C programming language

Home ⁄ C Coding ⁄ Implement Queue Data Structure using C programming language

Implement Queue Data Structure using C programming language