How to implement queue data structure from scratch?
Queue data structure enables you to use FIFO [ First IN First OUT ] approach. Whatever data comes first goes first. It is also called LILO [ Last IN Last OUT ]. For I/O, it provides you two functions.
- Enqueue [ To insert data into queue ]
- Dequeue [ To delete the data from the queue ]
Have you ever thought about where this queue concept is being used?
It is quite famous to solve the producer-consumer problem.
How to create your own queue from scratch? The below code is just a sample of creating and utilizing a queue.
#ifndef __QUEUE_H__
#define __QUEUE_H__
typedef struct _queue{
unsigned int *data;
unsigned int rear;
unsigned int front;
unsigned int size;
}queue;
queue* createQueue(unsigned int size_of_queue);
void enque(queue *q, unsigned int val);
int deque(queue *q);
void destroyQueue(queue *q);
void showQueue(queue *q);
#endifqueue.h
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
queue* createQueue(unsigned int size_of_queue)
{
queue *q = malloc(sizeof(queue));
q->data = malloc(sizeof(size_of_queue));
if(q->data == NULL){
free(q);
return NULL;
}
q->front = 0;
q->rear = 0;
q->size = size_of_queue;
return q;
}
void enque(queue *q, unsigned int val)
{
if(q->rear == q->size){
printf("Queue is fulln");
return;
}
q->data[(q->rear)++] = val;
}
int deque(queue *q)
{
if(q->front == q->rear){
printf("Queue is emptyn");
return -1;
}
int val = q->data[(q->front)++];
if(q->rear == q->front){
q->rear = q->front = 0;
}
return val;
}
void destroyQueue(queue *q)
{
if(q != NULL){
if(q->data != NULL)
{
free(q->data);
}
free(q);
}
}
void showQueue(queue *q)
{
static int i =0;
printf("<<|");
for(i=q->front; i<q->rear; i++){
printf(" %d | ",q->data[i]);
}
printf("n");
}queue.c
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
int main()
{
int size;
int ch;
int val;
printf("Enter the size of the queue you want to create : ");
scanf(" %d", &size);
queue *q1 = createQueue(size);
if(q1 == NULL)
{
printf("Can not allocated queue.n");
printf("Queue Failed !!n");
return -1;
}
while(1){
printf("tEnter 1. for enque()n");
printf("tEnter 2. for deque()n");
printf("tEnter any other integer for exit()n");
printf("Enter your choice :");
scanf(" %d",&ch);
switch(ch)
{
case 1:
printf("Enter the value you want to enque into queue : ");
scanf(" %d", &val);
enque(q1, val);
showQueue(q1);
break;
case 2:
val = deque(q1);
if(val >= 0){
printf("Popped value from the queue is : %dn",val);
}
showQueue(q1);
break;
default:
goto exitQueue;
}
}
exitQueue:
destroyQueue(q1);
return 0;
}main.c
Drawbacks /-
For this solution, one can notice that queue is not being utilized in an optimized way. If Queue is full and even if one runs dequeue operation which will eventually empty one space but still enqueue operation can’t be performed since rear points to last. Take this below example. After enqueue(4), Queue is full but after dequeue() operation we have one space available in the queue but can not run the enqueue() operation as rear points to the last index.
In order to optimized this solution, we can do a cyclic queue approach also known as Ring Buffer.
