Post Category: Resources > Tutorials

How to Create a Queue in C Language?

A queue is a linear data structure that follows the FIFO (First-In-First-Out) principle. Elements are inserted from the rear (enqueue) and removed from the front (dequeue) of the queue. It operates like a real-life queue, such as waiting in line for a ticket.

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It behaves like a real-life queue, where elements are added to the back and removed from the front, just like people waiting in line. The first element inserted is the first one to be removed.

Main Operations of a Queue:

A queue typically supports the following main operations:

Enqueue (Insertion): Adding an element to the back (rear) of the queue.

Dequeue (Deletion): Removing and returning the front element from the queue.

isEmpty: Checking if the queue is empty.

Peek: Viewing the front element without removing it

Implementation of Queue in C:

Queues can be implemented using various data structures like arrays or linked lists. One popular implementation is using a linked list.

Queue using Linked List:

In C, a queue using a linked list can be represented by a structure containing a pointer to the front and rear nodes of the queue. Each node in the linked list holds an element and a pointer to the next node.

Basic Steps for Queue Implementation:

  1. Define the data structure for the queue node and the queue itself.
  2. Initialize the queue by setting the front & rear pointers to NULL and the size to 0.
  3. Implement the enqueue operation to add elements to the rear of the queue.
  4. Implement the dequeue operation to remove elements from the front of the queue.
  5. Implement a function to check if the queue is empty.
  6. Optionally, implement a function to peek at the front element without removing it.
  7. Remember to handle memory allocation and deallocation to avoid memory leaks properly.

Example Use Case:

A common use case of a queue is in breadth-first search (BFS) algorithms, where nodes are processed level by level, ensuring that nodes at the same level are visited before moving to the next level.

Steps To Implementation Queue In C

Step 1: Define the Queue Structure

// queue.h
#ifndef QUEUE_H
#define QUEUE_H
// Define the data type for elements in the queue
typedef int QueueElement;
// Define the structure for the queue
typedef struct QueueNode {
QueueElement data;
struct QueueNode* next;
} QueueNode;
typedef struct Queue {
QueueNode* front;
QueueNode* rear;
int size;
} Queue;

#endif // QUEUE_H

Step 2: Initialize the Queue

// queue.c
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
// Initialize an empty queue
Queue* createQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
queue->front = NULL;
queue->rear = NULL;
queue->size = 0;
return queue;
}

Step 3: Enqueue Operation

// queue.c (Continued)
// Add an element to the rear of the queue
void enqueue(Queue* queue, QueueElement data) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = data;
newNode->next = NULL;
if (queue->rear == NULL) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
queue->size++;
}

Step 4: Dequeue Operation

// queue.c (Continued)
// Remove and return the front element of the queue
QueueElement dequeue(Queue* queue) {
if (queue->front == NULL) {
fprintf(stderr, "Error: Queue is empty.\n");
exit(EXIT_FAILURE);
}
QueueElement data = queue->front->data;
QueueNode* temp = queue->front;
queue->front = queue->front->next;
free(temp);
queue->size--;
return data;
}

Step 5: Check if the Queue is Empty

// queue.c (Continued)
// Check if the queue is empty
int isEmpty(Queue* queue) {
 return queue->size == 0;
}

Step 6: Peek at the Front Element

// queue.c (Continued)
// Get the front element without removing it
QueueElement front(Queue* queue) {
 if (queue->front == NULL) {
 fprintf(stderr, "Error: Queue is empty.\n");
 exit(EXIT_FAILURE);
}
return queue->front->data;
}

Step 7: Destroy the Queue

// queue.c (Continued)
// Destroy the queue and free all memory
void destroyQueue(Queue* queue) {
while (!isEmpty(queue)) {
dequeue(queue);
}
free(queue);
}

Example Use Cases:

Now that we have implemented the queue let's see how we can use it in some example scenarios:

#include <stdio.h>
#include "queue.h"

int main() {
// Create a new queue
 Queue* queue = createQueue();

// Enqueue elements
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);

 // Dequeue and print elements
 printf("Dequeue: %d\n", dequeue(queue));
 printf("Dequeue: %d\n", dequeue(queue));

 // Check if the queue is empty
 printf("Is the queue empty? %s\n", isEmpty(queue) ? "Yes" : "No");

 // Peek at the front element
printf("Front element: %d\n", front(queue));

// Destroy the queue
 destroyQueue(queue);

 return 0;
}

Conclusion:

In conclusion, a queue is a simple and useful data structure that enables efficient handling of elements in a First-In-First-Out manner. It has various applications in computer science and is widely used in solving algorithmic problems. Implementing a queue using linked lists is straightforward in C and provides an excellent starting point for understanding other complex data structures and algorithms.

In this article, we've covered creating a queue in C using a linked list. Queues are a versatile data structure used in various scenarios like task scheduling, BFS traversal, etc. Understanding queues is essential for every programmer, and implementing them from scratch helps deepen your understanding of data structures and algorithms.

How to Implement Face Detection using OpenCV in Python?
How to Remove Spaces From a String in Python?

No products in the cart.