Queue Data Structure using C Programming

A Queue is a collection of data elements, where elements are inserted at one end (rear) and elements are deleted from the other end (front). These operations are known as enqueue (insertion) and dequeue (deletion).

---

Operations on Queue

---

Generally, two operations are performed in the Queue data structure. The operations are

• insertion of new elements to the queue, known as Enqueue operation and
• removal of existing elements from the queue, known as a Dequeue operation.

There is another operation, which is used to read the front element of the queue without performing any modification to the queue. The operation is known as Peek.

---

Queue implementation using Array

---

Defining Queue data structure

#define SIZE 5

typedef struct Queue {
	int front, rear;
	int data[SIZE];
} queue;

Queue creation

void createQueue(queue *q)
{
	q->front = -1;
	q->rear = -1;
}

Enqueue operation

void enqueue(queue *q, int data)
{
	int i;
	if(isFull(q))
	{
		printf("\nQueue is full");
		return;
	}
	if(q->front == -1)
	{
		q->front = q->rear = 0;
	}
	else if((q->rear == SIZE - 1) && (q->front != 0))
	{
		for(i = q->front; i <= q->rear; i++)
			q->data[i - q->front] = q->data[i];
		q->rear = q->rear - q->front + 1;
		q->front = 0;
	}
	else
		q->rear++;
	q->data[q->rear] = data;
}

Dequeue operation

int dequeue(queue *q)
{
	int data;
	if(isEmpty(q))
	{
		printf("\nQueue is empty");
		return -1;
	}
	data = q->data[q->front];
	if(q->front == q->rear)
	{
		q->front = q->rear = -1;
	}
	else
		q->front++;
	return data;
}

Is Full Checking

		
int isFull(queue *q)
{
	if(q->front == 0 && q->rear == SIZE - 1)
		return 1;
	else
		return 0;
}

Is Empty Checking

int isEmpty(queue *q)
{
	if(q->front == -1)
		return 1;
	else
		return 0;
}

Complete source code

#include <stdio.h> #define SIZE 5 typedef struct Queue { int front, rear; int data[SIZE]; } queue; void createQueue(queue *q); int isFull(queue *q); int isEmpty(queue *q); void enqueue(queue *q, int data); int dequeue(queue *q); int main(void) { int choice, data; queue q; createQueue(&q); while(1) { printf("\nChoices:"); printf("\n 1: enqueue"); printf("\n 2: dequeue"); printf("\n 0: exit"); printf("\nEnter your choice:"); scanf("%d", &choice); switch(choice) { case 1: printf("\nEnter an element:"); scanf("%d", &data); enqueue(&q, data); break; case 2: data = dequeue(&q); if(data != -1) printf("\nThe dequeued element is :%d", data); break; case 0: exit(0); default: printf("\nInvalid choice"); } } } void createQueue(queue *q) { q->front = -1; q->rear = -1; } int isEmpty(queue *q) { if(q->front == -1) return 1; else return 0; } int isFull(queue *q) { if((q->front == 0) && (q->rear == SIZE - 1)) return 1; else return 0; } void enqueue(queue *q, int data) { int i; if(isFull(q)) { printf("\nQueue is full"); return; } if(q->front == -1) { q->front = q->rear = 0; } else if((q->rear == SIZE - 1) && (q->front != 0)) { for(i = q->front; i <= q->rear; i++) q->data[i - q->front] = q->data[i]; q->rear = q->rear - q->front + 1; q->front = 0; } else q->rear++; q->data[q->rear] = data; } int dequeue(queue *q) { int data; if(isEmpty(q)) { printf("\nQueue is empty"); return -1; } data = q->data[q->front]; if(q->front == q->rear) { q->front = q->rear = -1; } else q->front++; return data; }

---

Queue implementation using Linked List

---

Defining Structure

typedef struct Node {
	int data;
	struct Node *next;
} node;

typedef struct {
	node *front;
	node *rear;
} queue;

Queue creation

void createQueue(queue *q) {
	q->front = q->rear = NULL;
}

Is Empty Checking

int isEmpty(queue *q) {
	if(q->front == NULL)
		return 1;
	else
		return 0;
}

Enqueue operation

void enqueue(queue *q, int data) {
	node *ptr;
	ptr = malloc(sizeof(struct Node));
	ptr->data = data;
	ptr->next = NULL;
	if (q->rear == NULL) {
		q->front = q->rear = ptr;
	} else {
		(q->rear)->next = ptr;
		q->rear = ptr;
	}
}

Dequeue operation

int dequeue(queue *q ) {
	int data;
	node *ptr;
	
	data = (q->front)->data;
	ptr = q->front;

	if (q->front == q->rear) 
		q->front = q->rear = NULL;
	else 
		q->front = (q->front)->next;
	free(ptr);
	return data;
}

Complete source code

#include<stdio.h> #include<stdlib.h> typedef struct Node { int data; struct Node *next; } node; typedef struct { node *front; node *rear; } queue; void createQueue(queue *q); int isEmpty(queue *q); void enqueue(queue *q, int data); int dequeue(queue *q ); int main() { queue q; int choice, data; createQueue(&q); while (1) { printf("Main Menu\n 1. Enter data in queue\n 2. Delete from queue\n 0. Exit\n"); scanf("%d", &choice); switch (choice) { case 1: printf("Enter the data: "); scanf("%d", &data); enqueue(&q, data); break; case 2: if(isEmpty(&q)) printf("The queue is empty!\n"); else{ data = dequeue(&q); printf("The dequeued element is %d\n", data); } break; case 0: exit(0); default: printf("Invalid choice\n"); } } return 0; } void createQueue(queue *q) { q->front = q->rear = NULL; } int isEmpty(queue *q) { if(q->front == NULL) return 1; else return 0; } void enqueue(queue *q, int data) { node *ptr; ptr = malloc(sizeof(struct Node)); ptr->data = data; ptr->next = NULL; if (q->rear == NULL) { q->front = q->rear = ptr; } else { (q->rear)->next = ptr; q->rear = ptr; } } int dequeue(queue *q ) { int data; node *ptr; data = (q->front)->data; ptr = q->front; if (q->front == q->rear) q->front = q->rear = NULL; else q->front = (q->front)->next; free(ptr); return data; }

Happy Exploring!