A queue is a linear data structure used in programming that follows the First-In, First-Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue). Queues are widely used in operating systems, task scheduling, and simulations. This article demonstrates how to implement a queue using arrays in C, providing a simple yet efficient approach for fixed-size data storage.
Understanding the Problem
A queue is a data structure that follows the First In, First Out (FIFO) principle, meaning the first element added is the first one to be removed. When implementing a queue using arrays, we track two pointers: front for the first element and rear for the last element. Key challenges include handling queue overflow (when the array is full) and queue underflow (when attempting to remove an element from an empty queue). Proper management of these pointers ensures that enqueue and dequeue operations work correctly.
For a linked list implementation, the challenge shifts to dynamic memory management. We must accurately maintain front and rear pointers while allocating and freeing memory for each node. Correct handling guarantees that enqueue and dequeue operations remain efficient, memory is managed properly, and no invalid memory accesses occur.
Program 1: Queue Implementation Using Arrays
In this implementation, a fixed-size array is used to store the queue elements. The front pointer keeps track of the first element, and the rear pointer tracks the last element. Enqueue operations add elements to the rear, and dequeue operations remove elements from the front, following the FIFO principle. Overflow and underflow conditions are checked to ensure safe execution.
#include <stdio.h>
#define MAX 5
int queue[MAX];
int front = -1, rear = -1;
int isFull() {
return rear == MAX - 1;
}
int isEmpty() {
return front == -1 || front > rear;
}
void enqueue(int value) {
if (isFull()) {
printf("Queue Overflow! Cannot insert %d\n", value);
return;
}
if (front == -1) {
front = 0;
}
rear++;
queue[rear] = value;
printf("%d enqueued to the queue.\n", value);
}
void dequeue() {
if (isEmpty()) {
printf("Queue Underflow! Nothing to dequeue.\n");
return;
}
printf("%d dequeued from the queue.\n", queue[front]);
front++;
}
void display() {
if (isEmpty()) {
printf("Queue is empty.\n");
return;
}
printf("Queue elements: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
enqueue(40);
enqueue(50);
enqueue(60); // Overflow test
display();
return 0;
}This program demonstrates basic queue operations using arrays. The enqueue function inserts elements at the rear while ensuring the queue does not exceed its capacity. The dequeue function removes elements from the front, and the display function prints the current queue state. Checking for underflow and overflow ensures robust behavior.
Program 2: Dynamic Queue Using Linked List
For scenarios where the maximum number of elements is unknown or very large, a dynamic queue using a linked list is preferred. This implementation eliminates the fixed-size limitation of arrays and allows the queue to grow as needed. Memory is allocated for each new element dynamically, and deallocated when the element is removed, providing efficient space usage.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *front = NULL, *rear = NULL;
void enqueue(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (!rear) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
printf("%d enqueued to the queue.\n", value);
}
void dequeue() {
if (!front) {
printf("Queue Underflow! Nothing to dequeue.\n");
return;
}
Node *temp = front;
printf("%d dequeued from the queue.\n", front->data);
front = front->next;
if (!front) rear = NULL;
free(temp);
}
void display() {
if (!front) {
printf("Queue is empty.\n");
return;
}
Node *temp = front;
printf("Queue elements: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
enqueue(10);
enqueue(20);
enqueue(30);
display();
dequeue();
display();
enqueue(40);
enqueue(50);
display();
return 0;
}This dynamic queue implementation uses linked nodes for each element. The enqueue function adds elements to the rear, while dequeue removes elements from the front. Memory is freed as elements are dequeued, ensuring no memory leaks occur. This approach allows the queue to expand dynamically without worrying about overflow.
FAQs
Q1: Can a queue implemented with an array grow dynamically?
No, a fixed-size array cannot grow. However, a linked-list queue can expand dynamically as elements are added.
Q2: What is the time complexity of enqueue and dequeue operations?
Both operations run in O(1) time for array-based and linked-list queues.
Q3: Can we implement a circular queue using arrays?
Yes, a circular queue wraps the rear pointer to the start of the array, efficiently using space from dequeued elements.
Q4: When is a linked-list queue better than an array-based queue?
Linked-list queues are ideal for large or unpredictable numbers of elements because they grow dynamically. Array-based queues are simpler and faster for small, fixed-size queues.
Q5: How is memory managed in a linked-list queue?
Each node is allocated dynamically during enqueue and freed during dequeue, ensuring no memory leaks.
Q6: Can a linked-list queue become inefficient?
Linked-list queues remain efficient if pointers are managed correctly. Inefficiency may occur if memory allocation fails or nodes are not freed properly.
Conclusion
Queues are essential data structures for handling tasks in FIFO order. Array-based queues are simple and efficient for small fixed-size applications, while linked-list queues provide dynamic sizing for larger or unpredictable workloads. By managing pointers carefully and avoiding common mistakes like overflow, underflow, or memory leaks, queue operations can be implemented reliably.
References & Additional Resources
A curated collection of textbooks and tutorials for learning queues, their types, and implementations in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference covering C fundamentals such as arrays, pointers, and memory management needed for queue implementations.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of queue concepts, circular queues, and practical C examples.
- TutorialsPoint: Queue Data Structure – Explains queues, operations (
enqueue,dequeue), and algorithms. - Programiz: Queue Implementation in C – Practical guide with C examples for linear and circular queues.
- GeeksforGeeks: Circular Queue Using Arrays – Step-by-step explanation of circular queue implementation using arrays.
- C Standard Library Documentation – Official reference for C libraries and functions often used in queue operations.
