Data Structures in C - Queue

Posted on April 14, 2016
data-structures-in-c-queue

In this part of Data Structure in C tutorial series, I will explain what is Queue and I will show you - how to write a Queue from scratch in C. Queue is a very important data structure and is often asked in interviews. Candidates are asked to explain and write complete Queue code from scratch. They are also asked to implement a Queue using two Stacks.


A Queue looks like as shown below.



An Empty Queue looks like as shown below.


If you insert an element 3 to an Empty Queue it looks like as shown below.



If you insert one more element 5 into this Queue, the Queue will look as show below.



Therefore, when you insert an element into a Queue, its appended into the end of the Queue.

If we remove an element from the Queue, the Queue looks like as shown below.



Therefore, when we remove an element from the Queue it gets removed from the front of the Queue.

The front of the Queue is pointed by a Front pointer and the end of the Queue is pointed by the Rear pointer. There are mainly three operations a Queue supports.



  • Add

  • Remove

  • Peek


The Add function adds an element to the end of the Queue. The Remove function removes an element from the front of the Queue. The Peek function gives you the element which is present at the front of the Queue without removing it from the Queue.


Apart from the above basic functions, a Queue should also give facility to the user to see if the Queue is Empty. If the user tries to Remove or Peek from an Empty Queue, the user should be reported with appropriate error message.


A Queue is implemented using a Linked List or an Array. If the Queue is implemented using an Array, the queue will have a maximum size. Therefore, if the user tries to insert an element into a Queue which is already full, an appropriate error message should be shown to the user.


Below is the complete working code for Queue data structures in C using Linked List. I have taken elements as integer. You can modify the code to change the data types of the elements as per your requirement.


#include <stdio.h>
#include <stdlib.h>
struct node{
int v;
struct node *next
};
struct Queue{
struct node *front,*rear;
};
struct Queue *createQ(){
struct Queue *Q = (struct Queue*)malloc(sizeof(struct Queue));
Q->front = Q->rear = NULL;
return Q;
}
int isEmptyQ(struct Queue *Q){
if(!Q){
printf("Null pointer Exception!");
exit(1);
}
if(!Q->front)
return 1;
return 0;
}
void add(struct Queue *Q,int v){
if(!Q){
printf("Null pointer Exception!");
exit(1);
}
if(!Q->front && !Q->rear){
Q->rear = (struct node*)malloc(sizeof(struct node));
Q->rear->v = v;
Q->rear->next = NULL;
Q->front = Q->rear;
}
else if(Q->front==Q->rear){
Q->rear = (struct node*)malloc(sizeof(struct node));
Q->rear->v = v;
Q->rear->next = NULL;
Q->front->next = Q->rear;
}
else{
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->v = v;
newNode->next = NULL;
Q->rear->next = newNode;
Q->rear = newNode;
}
}
int remove(struct Queue *Q){
if(!isEmptyQ(Q)){
struct node *currFront = Q->front;
Q->front = Q->front->next;
if(!Q->front)
Q->rear = NULL;
int v = currFront->v;
free(currFront);
return v;
}
printf("The Queue is Empty!");
return -1;
}
int peek(struct Queue *Q){
if(!isEmptyQ(Q)){
return Q->front->v;
}
printf("The Queue is Empty!");
return -1;
}
int main()
{
struct Queue *Q = createQ();
if(isEmptyQ(Q)){
printf("Queue is Empty!\n");
}
add(Q,2);
add(Q,6);
add(Q,5);
printf("Removed element from the Queue is: %d\n",remove(Q));
add(Q,9);
printf("Removed element from the Queue is: %d\n",remove(Q));
printf("Removed element from the Queue is: %d\n",remove(Q));
printf("Removed element from the Queue is: %d\n",remove(Q));
if(isEmptyQ(Q)){
printf("Queue is Empty!\n");
}
add(Q,8);
printf("Front element in the Queue is: %d",peek(Q));
return 0;
}


If you have any doubt regarding the code or any other concept, please leave your queries in the comment section.

Sharing is Caring!

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah

Research Engineer @XRCI


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2016
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates