Queues are fundamental data structures that follow the First-In-First-Out (FIFO) principle. They are essential in systems programming, task scheduling, buffering, and many algorithmic applications. Implementing queues in C requires careful memory management, pointer manipulation, and understanding of both static and dynamic data structures. This guide covers multiple implementations from simple arrays to thread-safe concurrent queues.

What is a Queue?

A queue is a linear data structure that operates like a waiting line: elements are added at one end (rear/tail) and removed from the other end (front/head). This FIFO behavior makes queues ideal for managing resources, scheduling tasks, and handling asynchronous data streams.

Why Queue Implementation is Essential in C

1. System Programming: Message queues, process scheduling, and interrupt handling
2. Data Buffering: I/O buffers, network packet queues, and streaming data
3. Algorithm Design: BFS graph traversal, level-order tree traversal
4. Resource Management: Thread pools, connection pools, and request queues
5. Real-time Systems: Event processing and task scheduling

Basic Queue Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
// Core queue operations:
// - enqueue() / push() / offer()  - Add element to rear
// - dequeue() / pop() / poll()     - Remove element from front
// - front() / peek()                - View front element without removing
// - isEmpty()                       - Check if queue is empty
// - isFull()                        - Check if queue is full (for array-based)
// - size()                          - Get number of elements

1. Array-Based Circular Queue

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// ============================================================
// CIRCULAR QUEUE USING ARRAY (STATIC IMPLEMENTATION)
// ============================================================
typedef struct {
int *data;       // Dynamic array for queue elements
int front;       // Index of front element
int rear;        // Index where next element will be inserted
int size;        // Current number of elements
int capacity;    // Maximum capacity of queue
} CircularQueue;
// Initialize queue with given capacity
CircularQueue* createQueue(int capacity) {
CircularQueue *q = (CircularQueue*)malloc(sizeof(CircularQueue));
q->data = (int*)malloc(capacity * sizeof(int));
q->front = 0;
q->rear = 0;
q->size = 0;
q->capacity = capacity;
return q;
}
// Check if queue is empty
bool isEmpty(CircularQueue *q) {
return q->size == 0;
}
// Check if queue is full
bool isFull(CircularQueue *q) {
return q->size == q->capacity;
}
// Add element to rear of queue
bool enqueue(CircularQueue *q, int value) {
if (isFull(q)) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return false;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % q->capacity;  // Circular increment
q->size++;
return true;
}
// Remove and return front element
int dequeue(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue Underflow! Cannot dequeue\n");
return -1;  // Error value
}
int value = q->data[q->front];
q->front = (q->front + 1) % q->capacity;  // Circular increment
q->size--;
return value;
}
// Get front element without removing
int peek(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty! Cannot peek\n");
return -1;
}
return q->data[q->front];
}
// Get current size
int queueSize(CircularQueue *q) {
return q->size;
}
// Get capacity
int queueCapacity(CircularQueue *q) {
return q->capacity;
}
// Clear all elements (reset queue)
void clearQueue(CircularQueue *q) {
q->front = 0;
q->rear = 0;
q->size = 0;
}
// Display queue contents
void displayQueue(CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty\n");
return;
}
printf("Queue (front to rear): ");
int i = q->front;
int count = 0;
while (count < q->size) {
printf("%d ", q->data[i]);
i = (i + 1) % q->capacity;
count++;
}
printf("\n");
printf("Front index: %d, Rear index: %d, Size: %d\n", 
q->front, q->rear, q->size);
}
// Free queue memory
void freeQueue(CircularQueue *q) {
free(q->data);
free(q);
}
// Example usage
int main() {
printf("=== Array-based Circular Queue ===\n\n");
CircularQueue *q = createQueue(5);
printf("Enqueuing elements: 10, 20, 30, 40\n");
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
enqueue(q, 40);
displayQueue(q);
printf("\nDequeue: %d\n", dequeue(q));
printf("Dequeue: %d\n", dequeue(q));
displayQueue(q);
printf("\nPeek front: %d\n", peek(q));
printf("\nEnqueue: 50, 60\n");
enqueue(q, 50);
enqueue(q, 60);
displayQueue(q);
printf("\nEnqueue: 70 (should fail - full)\n");
enqueue(q, 70);  // Should show overflow
printf("\nDequeue all elements:\n");
while (!isEmpty(q)) {
printf("Dequeued: %d\n", dequeue(q));
}
freeQueue(q);
return 0;
}

2. Dynamic Array-Based Queue (Auto-resizing)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// DYNAMIC QUEUE WITH AUTO-RESIZING
// ============================================================
typedef struct {
int *data;
int front;
int rear;
int size;
int capacity;
} DynamicQueue;
DynamicQueue* createDynamicQueue(int initialCapacity) {
DynamicQueue *q = (DynamicQueue*)malloc(sizeof(DynamicQueue));
q->data = (int*)malloc(initialCapacity * sizeof(int));
q->front = 0;
q->rear = 0;
q->size = 0;
q->capacity = initialCapacity;
return q;
}
// Resize queue to new capacity
void resizeQueue(DynamicQueue *q, int newCapacity) {
int *newData = (int*)malloc(newCapacity * sizeof(int));
// Copy elements in order from front to rear
int i = q->front;
int count = 0;
while (count < q->size) {
newData[count] = q->data[i];
i = (i + 1) % q->capacity;
count++;
}
free(q->data);
q->data = newData;
q->front = 0;
q->rear = q->size;
q->capacity = newCapacity;
printf("Queue resized to capacity: %d\n", newCapacity);
}
void enqueueDynamic(DynamicQueue *q, int value) {
if (q->size == q->capacity) {
// Double the capacity
resizeQueue(q, q->capacity * 2);
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % q->capacity;
q->size++;
}
int dequeueDynamic(DynamicQueue *q) {
if (q->size == 0) {
printf("Queue underflow!\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % q->capacity;
q->size--;
// Shrink if size < capacity/4 (to avoid frequent resizing)
if (q->size > 0 && q->size == q->capacity / 4 && q->capacity > 4) {
resizeQueue(q, q->capacity / 2);
}
return value;
}
int peekDynamic(DynamicQueue *q) {
if (q->size == 0) {
printf("Queue empty\n");
return -1;
}
return q->data[q->front];
}
void displayDynamicQueue(DynamicQueue *q) {
if (q->size == 0) {
printf("Queue empty\n");
return;
}
printf("Queue: ");
int i = q->front;
int count = 0;
while (count < q->size) {
printf("%d ", q->data[i]);
i = (i + 1) % q->capacity;
count++;
}
printf("(size=%d, capacity=%d)\n", q->size, q->capacity);
}
void freeDynamicQueue(DynamicQueue *q) {
free(q->data);
free(q);
}
int main() {
printf("=== Dynamic Auto-resizing Queue ===\n\n");
DynamicQueue *q = createDynamicQueue(4);
printf("Adding 8 elements (will trigger resizing):\n");
for (int i = 1; i <= 8; i++) {
enqueueDynamic(q, i * 10);
printf("Enqueued: %d, ", i * 10);
displayDynamicQueue(q);
}
printf("\nRemoving 6 elements:\n");
for (int i = 0; i < 6; i++) {
int val = dequeueDynamic(q);
printf("Dequeued: %d, ", val);
displayDynamicQueue(q);
}
freeDynamicQueue(q);
return 0;
}

3. Linked List-Based Queue

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// LINKED LIST QUEUE (DYNAMIC MEMORY)
// ============================================================
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;    // Pointer to front node
Node *rear;     // Pointer to rear node
int size;       // Number of elements
} LinkedListQueue;
// Create new node
Node* createNode(int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// Initialize empty queue
LinkedListQueue* createLLQueue() {
LinkedListQueue *q = (LinkedListQueue*)malloc(sizeof(LinkedListQueue));
q->front = NULL;
q->rear = NULL;
q->size = 0;
return q;
}
// Check if queue is empty
bool isLLEmpty(LinkedListQueue *q) {
return q->front == NULL;
}
// Add element to rear
void enqueueLL(LinkedListQueue *q, int value) {
Node *newNode = createNode(value);
if (isLLEmpty(q)) {
q->front = newNode;
q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}
// Remove and return front element
int dequeueLL(LinkedListQueue *q) {
if (isLLEmpty(q)) {
printf("Queue underflow!\n");
return -1;
}
Node *temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;  // Queue became empty
}
free(temp);
q->size--;
return value;
}
// Peek front element
int peekLL(LinkedListQueue *q) {
if (isLLEmpty(q)) {
printf("Queue empty\n");
return -1;
}
return q->front->data;
}
// Get size
int sizeLL(LinkedListQueue *q) {
return q->size;
}
// Display queue
void displayLLQueue(LinkedListQueue *q) {
if (isLLEmpty(q)) {
printf("Queue empty\n");
return;
}
printf("Queue: ");
Node *current = q->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("(size=%d)\n", q->size);
}
// Free entire queue
void freeLLQueue(LinkedListQueue *q) {
Node *current = q->front;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
free(q);
}
int main() {
printf("=== Linked List Queue ===\n\n");
LinkedListQueue *q = createLLQueue();
printf("Enqueuing: 5, 10, 15, 20\n");
enqueueLL(q, 5);
enqueueLL(q, 10);
enqueueLL(q, 15);
enqueueLL(q, 20);
displayLLQueue(q);
printf("\nDequeue: %d\n", dequeueLL(q));
printf("Dequeue: %d\n", dequeueLL(q));
displayLLQueue(q);
printf("\nPeek front: %d\n", peekLL(q));
printf("\nEnqueue: 25, 30\n");
enqueueLL(q, 25);
enqueueLL(q, 30);
displayLLQueue(q);
printf("\nDequeue all:\n");
while (!isLLEmpty(q)) {
printf("Dequeued: %d\n", dequeueLL(q));
}
freeLLQueue(q);
return 0;
}

4. Double-Ended Queue (Deque)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// DOUBLE-ENDED QUEUE (DEQUE)
// ============================================================
typedef struct DequeNode {
int data;
struct DequeNode *prev;
struct DequeNode *next;
} DequeNode;
typedef struct {
DequeNode *front;
DequeNode *rear;
int size;
} Deque;
DequeNode* createDequeNode(int value) {
DequeNode *node = (DequeNode*)malloc(sizeof(DequeNode));
node->data = value;
node->prev = NULL;
node->next = NULL;
return node;
}
Deque* createDeque() {
Deque *d = (Deque*)malloc(sizeof(Deque));
d->front = NULL;
d->rear = NULL;
d->size = 0;
return d;
}
bool isDequeEmpty(Deque *d) {
return d->front == NULL;
}
// Add to front
void pushFront(Deque *d, int value) {
DequeNode *node = createDequeNode(value);
if (isDequeEmpty(d)) {
d->front = node;
d->rear = node;
} else {
node->next = d->front;
d->front->prev = node;
d->front = node;
}
d->size++;
}
// Add to rear
void pushRear(Deque *d, int value) {
DequeNode *node = createDequeNode(value);
if (isDequeEmpty(d)) {
d->front = node;
d->rear = node;
} else {
node->prev = d->rear;
d->rear->next = node;
d->rear = node;
}
d->size++;
}
// Remove from front
int popFront(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque underflow!\n");
return -1;
}
DequeNode *temp = d->front;
int value = temp->data;
d->front = d->front->next;
if (d->front == NULL) {
d->rear = NULL;
} else {
d->front->prev = NULL;
}
free(temp);
d->size--;
return value;
}
// Remove from rear
int popRear(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque underflow!\n");
return -1;
}
DequeNode *temp = d->rear;
int value = temp->data;
d->rear = d->rear->prev;
if (d->rear == NULL) {
d->front = NULL;
} else {
d->rear->next = NULL;
}
free(temp);
d->size--;
return value;
}
// Get front without removing
int peekFront(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque empty\n");
return -1;
}
return d->front->data;
}
// Get rear without removing
int peekRear(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque empty\n");
return -1;
}
return d->rear->data;
}
// Display from front to rear
void displayDeque(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque empty\n");
return;
}
printf("Deque (front to rear): ");
DequeNode *current = d->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("(size=%d)\n", d->size);
}
// Display from rear to front (reverse)
void displayDequeReverse(Deque *d) {
if (isDequeEmpty(d)) {
printf("Deque empty\n");
return;
}
printf("Deque (rear to front): ");
DequeNode *current = d->rear;
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
printf("\n");
}
void freeDeque(Deque *d) {
while (!isDequeEmpty(d)) {
popFront(d);
}
free(d);
}
int main() {
printf("=== Double-Ended Queue (Deque) ===\n\n");
Deque *d = createDeque();
printf("Pushing to rear: 10, 20, 30\n");
pushRear(d, 10);
pushRear(d, 20);
pushRear(d, 30);
displayDeque(d);
printf("\nPushing to front: 5, 2\n");
pushFront(d, 5);
pushFront(d, 2);
displayDeque(d);
printf("\nPop front: %d\n", popFront(d));
printf("Pop rear: %d\n", popRear(d));
displayDeque(d);
printf("\nPeek front: %d\n", peekFront(d));
printf("Peek rear: %d\n", peekRear(d));
printf("\nReverse order: ");
displayDequeReverse(d);
freeDeque(d);
return 0;
}

5. Priority Queue

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// PRIORITY QUEUE (MAX-HEAP IMPLEMENTATION)
// ============================================================
typedef struct {
int *data;
int *priorities;
int size;
int capacity;
} PriorityQueue;
PriorityQueue* createPriorityQueue(int capacity) {
PriorityQueue *pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->data = (int*)malloc(capacity * sizeof(int));
pq->priorities = (int*)malloc(capacity * sizeof(int));
pq->size = 0;
pq->capacity = capacity;
return pq;
}
// Swap two elements
void swap(PriorityQueue *pq, int i, int j) {
int tempData = pq->data[i];
pq->data[i] = pq->data[j];
pq->data[j] = tempData;
int tempPri = pq->priorities[i];
pq->priorities[i] = pq->priorities[j];
pq->priorities[j] = tempPri;
}
// Heapify up (for insertion)
void heapifyUp(PriorityQueue *pq, int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (pq->priorities[index] > pq->priorities[parent]) {
swap(pq, index, parent);
index = parent;
} else {
break;
}
}
}
// Heapify down (for removal)
void heapifyDown(PriorityQueue *pq, int index) {
int largest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < pq->size && pq->priorities[left] > pq->priorities[largest]) {
largest = left;
}
if (right < pq->size && pq->priorities[right] > pq->priorities[largest]) {
largest = right;
}
if (largest != index) {
swap(pq, index, largest);
heapifyDown(pq, largest);
}
}
// Insert element with priority
void enqueuePriority(PriorityQueue *pq, int value, int priority) {
if (pq->size == pq->capacity) {
printf("Priority queue full!\n");
return;
}
pq->data[pq->size] = value;
pq->priorities[pq->size] = priority;
heapifyUp(pq, pq->size);
pq->size++;
}
// Remove and return highest priority element
int dequeuePriority(PriorityQueue *pq) {
if (pq->size == 0) {
printf("Priority queue empty!\n");
return -1;
}
int value = pq->data[0];
pq->data[0] = pq->data[pq->size - 1];
pq->priorities[0] = pq->priorities[pq->size - 1];
pq->size--;
heapifyDown(pq, 0);
return value;
}
// Peek highest priority element
int peekPriority(PriorityQueue *pq) {
if (pq->size == 0) {
printf("Priority queue empty!\n");
return -1;
}
return pq->data[0];
}
// Change priority of an element (if you know its current value)
void changePriority(PriorityQueue *pq, int value, int newPriority) {
for (int i = 0; i < pq->size; i++) {
if (pq->data[i] == value) {
int oldPriority = pq->priorities[i];
pq->priorities[i] = newPriority;
if (newPriority > oldPriority) {
heapifyUp(pq, i);
} else if (newPriority < oldPriority) {
heapifyDown(pq, i);
}
return;
}
}
printf("Value %d not found in priority queue\n", value);
}
void displayPriorityQueue(PriorityQueue *pq) {
printf("Priority Queue (value:priority): ");
for (int i = 0; i < pq->size; i++) {
printf("(%d:%d) ", pq->data[i], pq->priorities[i]);
}
printf("\n");
}
void freePriorityQueue(PriorityQueue *pq) {
free(pq->data);
free(pq->priorities);
free(pq);
}
int main() {
printf("=== Priority Queue (Max-Heap) ===\n\n");
PriorityQueue *pq = createPriorityQueue(10);
printf("Enqueuing with priorities:\n");
enqueuePriority(pq, 10, 3);
enqueuePriority(pq, 20, 1);
enqueuePriority(pq, 30, 5);
enqueuePriority(pq, 40, 2);
enqueuePriority(pq, 50, 4);
displayPriorityQueue(pq);
printf("\nDequeue (highest priority): %d\n", dequeuePriority(pq));
displayPriorityQueue(pq);
printf("\nDequeue: %d\n", dequeuePriority(pq));
displayPriorityQueue(pq);
printf("\nChange priority of 40 to 5:\n");
changePriority(pq, 40, 5);
displayPriorityQueue(pq);
freePriorityQueue(pq);
return 0;
}

6. Circular Buffer Queue

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// ============================================================
// CIRCULAR BUFFER QUEUE (FIXED SIZE, OVERWRITE OPTION)
// ============================================================
typedef struct {
int *buffer;
int head;       // Read position
int tail;       // Write position
int count;      // Current number of elements
int capacity;   // Maximum capacity
bool overwrite; // Whether to overwrite when full
} CircularBuffer;
CircularBuffer* createCircularBuffer(int capacity, bool overwrite) {
CircularBuffer *cb = (CircularBuffer*)malloc(sizeof(CircularBuffer));
cb->buffer = (int*)malloc(capacity * sizeof(int));
cb->head = 0;
cb->tail = 0;
cb->count = 0;
cb->capacity = capacity;
cb->overwrite = overwrite;
return cb;
}
// Add element to buffer
bool writeBuffer(CircularBuffer *cb, int value) {
if (cb->count == cb->capacity) {
if (cb->overwrite) {
// Overwrite oldest element
cb->buffer[cb->tail] = value;
cb->tail = (cb->tail + 1) % cb->capacity;
cb->head = (cb->head + 1) % cb->capacity;
return true;
} else {
printf("Buffer full, cannot write %d\n", value);
return false;
}
}
cb->buffer[cb->tail] = value;
cb->tail = (cb->tail + 1) % cb->capacity;
cb->count++;
return true;
}
// Read and remove oldest element
int readBuffer(CircularBuffer *cb) {
if (cb->count == 0) {
printf("Buffer empty\n");
return -1;
}
int value = cb->buffer[cb->head];
cb->head = (cb->head + 1) % cb->capacity;
cb->count--;
return value;
}
// Peek oldest without removing
int peekBuffer(CircularBuffer *cb) {
if (cb->count == 0) {
printf("Buffer empty\n");
return -1;
}
return cb->buffer[cb->head];
}
// Check if buffer is full
bool isBufferFull(CircularBuffer *cb) {
return cb->count == cb->capacity;
}
// Check if buffer is empty
bool isBufferEmpty(CircularBuffer *cb) {
return cb->count == 0;
}
// Get free space
int freeSpace(CircularBuffer *cb) {
return cb->capacity - cb->count;
}
// Display buffer contents in order
void displayBuffer(CircularBuffer *cb) {
printf("Buffer: [");
int idx = cb->head;
for (int i = 0; i < cb->count; i++) {
printf("%d", cb->buffer[idx]);
if (i < cb->count - 1) printf(", ");
idx = (idx + 1) % cb->capacity;
}
printf("] (count=%d, capacity=%d, head=%d, tail=%d)\n",
cb->count, cb->capacity, cb->head, cb->tail);
}
void freeCircularBuffer(CircularBuffer *cb) {
free(cb->buffer);
free(cb);
}
int main() {
printf("=== Circular Buffer Queue ===\n\n");
printf("Without overwrite (blocking when full):\n");
CircularBuffer *cb = createCircularBuffer(5, false);
for (int i = 1; i <= 5; i++) {
writeBuffer(cb, i * 10);
printf("Wrote: %d, ", i * 10);
displayBuffer(cb);
}
printf("\nTrying to write when full:\n");
writeBuffer(cb, 60);  // Should fail
printf("\nReading 2 elements:\n");
printf("Read: %d\n", readBuffer(cb));
printf("Read: %d\n", readBuffer(cb));
displayBuffer(cb);
printf("\nWriting new elements:\n");
writeBuffer(cb, 60);
writeBuffer(cb, 70);
displayBuffer(cb);
freeCircularBuffer(cb);
printf("\nWith overwrite enabled:\n");
cb = createCircularBuffer(5, true);
for (int i = 1; i <= 7; i++) {
writeBuffer(cb, i * 10);
printf("Wrote: %d, ", i * 10);
displayBuffer(cb);
}
freeCircularBuffer(cb);
return 0;
}

7. Thread-Safe Queue (Using Mutex)

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
#include <stdbool.h>
// ============================================================
// THREAD-SAFE QUEUE (WITH MUTEX AND CONDITION VARIABLES)
// ============================================================
typedef struct NodeTS {
int data;
struct NodeTS *next;
} NodeTS;
typedef struct {
NodeTS *front;
NodeTS *rear;
int size;
pthread_mutex_t mutex;
pthread_cond_t notEmpty;
pthread_cond_t notFull;
int maxSize;  // -1 for unlimited
} ThreadSafeQueue;
ThreadSafeQueue* createTSQueue(int maxSize) {
ThreadSafeQueue *q = (ThreadSafeQueue*)malloc(sizeof(ThreadSafeQueue));
q->front = NULL;
q->rear = NULL;
q->size = 0;
q->maxSize = maxSize;
pthread_mutex_init(&q->mutex, NULL);
pthread_cond_init(&q->notEmpty, NULL);
pthread_cond_init(&q->notFull, NULL);
return q;
}
NodeTS* createTSNode(int value) {
NodeTS *node = (NodeTS*)malloc(sizeof(NodeTS));
node->data = value;
node->next = NULL;
return node;
}
// Thread-safe enqueue (may block if full)
void tsEnqueue(ThreadSafeQueue *q, int value) {
pthread_mutex_lock(&q->mutex);
// Wait if queue is full (if maxSize is set)
while (q->maxSize > 0 && q->size >= q->maxSize) {
pthread_cond_wait(&q->notFull, &q->mutex);
}
NodeTS *node = createTSNode(value);
if (q->rear == NULL) {
q->front = node;
q->rear = node;
} else {
q->rear->next = node;
q->rear = node;
}
q->size++;
printf("Thread %lu enqueued: %d (size=%d)\n", 
pthread_self(), value, q->size);
// Signal that queue is not empty
pthread_cond_signal(&q->notEmpty);
pthread_mutex_unlock(&q->mutex);
}
// Thread-safe dequeue (blocks if empty)
int tsDequeue(ThreadSafeQueue *q) {
pthread_mutex_lock(&q->mutex);
// Wait if queue is empty
while (q->front == NULL) {
pthread_cond_wait(&q->notEmpty, &q->mutex);
}
NodeTS *temp = q->front;
int value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
q->size--;
printf("Thread %lu dequeued: %d (size=%d)\n", 
pthread_self(), value, q->size);
// Signal that queue is not full
if (q->maxSize > 0) {
pthread_cond_signal(&q->notFull);
}
pthread_mutex_unlock(&q->mutex);
return value;
}
// Non-blocking try dequeue
bool tsTryDequeue(ThreadSafeQueue *q, int *value) {
pthread_mutex_lock(&q->mutex);
if (q->front == NULL) {
pthread_mutex_unlock(&q->mutex);
return false;
}
NodeTS *temp = q->front;
*value = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
q->size--;
if (q->maxSize > 0) {
pthread_cond_signal(&q->notFull);
}
pthread_mutex_unlock(&q->mutex);
return true;
}
// Get current size
int tsSize(ThreadSafeQueue *q) {
pthread_mutex_lock(&q->mutex);
int size = q->size;
pthread_mutex_unlock(&q->mutex);
return size;
}
// Destroy queue
void freeTSQueue(ThreadSafeQueue *q) {
pthread_mutex_lock(&q->mutex);
// Free all nodes
NodeTS *current = q->front;
while (current != NULL) {
NodeTS *temp = current;
current = current->next;
free(temp);
}
pthread_mutex_unlock(&q->mutex);
pthread_mutex_destroy(&q->mutex);
pthread_cond_destroy(&q->notEmpty);
pthread_cond_destroy(&q->notFull);
free(q);
}
// Producer thread function
void* producer(void *arg) {
ThreadSafeQueue *q = (ThreadSafeQueue*)arg;
for (int i = 1; i <= 5; i++) {
tsEnqueue(q, i * 10);
usleep(rand() % 100000);  // Random delay
}
return NULL;
}
// Consumer thread function
void* consumer(void *arg) {
ThreadSafeQueue *q = (ThreadSafeQueue*)arg;
for (int i = 1; i <= 5; i++) {
int value = tsDequeue(q);
usleep(rand() % 200000);  // Random delay
}
return NULL;
}
int main() {
printf("=== Thread-Safe Queue ===\n\n");
ThreadSafeQueue *q = createTSQueue(10);  // Max size 10
pthread_t producer1, producer2, consumer1, consumer2;
// Create threads
pthread_create(&producer1, NULL, producer, q);
pthread_create(&producer2, NULL, producer, q);
pthread_create(&consumer1, NULL, consumer, q);
pthread_create(&consumer2, NULL, consumer, q);
// Wait for threads to finish
pthread_join(producer1, NULL);
pthread_join(producer2, NULL);
pthread_join(consumer1, NULL);
pthread_join(consumer2, NULL);
printf("\nFinal queue size: %d\n", tsSize(q));
freeTSQueue(q);
return 0;
}

8. Blocking Queue with Timeout

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <sys/time.h>
#include <errno.h>
// ============================================================
// BLOCKING QUEUE WITH TIMEOUT
// ============================================================
typedef struct {
int *buffer;
int capacity;
int count;
int head;
int tail;
pthread_mutex_t mutex;
pthread_cond_t notEmpty;
pthread_cond_t notFull;
} BlockingQueue;
BlockingQueue* createBlockingQueue(int capacity) {
BlockingQueue *q = (BlockingQueue*)malloc(sizeof(BlockingQueue));
q->buffer = (int*)malloc(capacity * sizeof(int));
q->capacity = capacity;
q->count = 0;
q->head = 0;
q->tail = 0;
pthread_mutex_init(&q->mutex, NULL);
pthread_cond_init(&q->notEmpty, NULL);
pthread_cond_init(&q->notFull, NULL);
return q;
}
// Enqueue with timeout (milliseconds)
bool enqueueTimeout(BlockingQueue *q, int value, int timeout_ms) {
struct timespec ts;
struct timeval tv;
gettimeofday(&tv, NULL);
ts.tv_sec = tv.tv_sec + timeout_ms / 1000;
ts.tv_nsec = (tv.tv_usec + (timeout_ms % 1000) * 1000) * 1000;
if (ts.tv_nsec >= 1000000000) {
ts.tv_sec++;
ts.tv_nsec -= 1000000000;
}
pthread_mutex_lock(&q->mutex);
while (q->count == q->capacity) {
int rc = pthread_cond_timedwait(&q->notFull, &q->mutex, &ts);
if (rc == ETIMEDOUT) {
pthread_mutex_unlock(&q->mutex);
return false;  // Timeout
}
}
q->buffer[q->tail] = value;
q->tail = (q->tail + 1) % q->capacity;
q->count++;
pthread_cond_signal(&q->notEmpty);
pthread_mutex_unlock(&q->mutex);
return true;
}
// Dequeue with timeout (milliseconds)
bool dequeueTimeout(BlockingQueue *q, int *value, int timeout_ms) {
struct timespec ts;
struct timeval tv;
gettimeofday(&tv, NULL);
ts.tv_sec = tv.tv_sec + timeout_ms / 1000;
ts.tv_nsec = (tv.tv_usec + (timeout_ms % 1000) * 1000) * 1000;
if (ts.tv_nsec >= 1000000000) {
ts.tv_sec++;
ts.tv_nsec -= 1000000000;
}
pthread_mutex_lock(&q->mutex);
while (q->count == 0) {
int rc = pthread_cond_timedwait(&q->notEmpty, &q->mutex, &ts);
if (rc == ETIMEDOUT) {
pthread_mutex_unlock(&q->mutex);
return false;  // Timeout
}
}
*value = q->buffer[q->head];
q->head = (q->head + 1) % q->capacity;
q->count--;
pthread_cond_signal(&q->notFull);
pthread_mutex_unlock(&q->mutex);
return true;
}
void freeBlockingQueue(BlockingQueue *q) {
free(q->buffer);
pthread_mutex_destroy(&q->mutex);
pthread_cond_destroy(&q->notEmpty);
pthread_cond_destroy(&q->notFull);
free(q);
}
// Example usage in main
int main() {
printf("=== Blocking Queue with Timeout ===\n\n");
BlockingQueue *q = createBlockingQueue(3);
printf("Enqueue with timeout 1 second:\n");
for (int i = 1; i <= 5; i++) {
if (enqueueTimeout(q, i * 10, 1000)) {
printf("Enqueued: %d\n", i * 10);
} else {
printf("Failed to enqueue %d (timeout)\n", i * 10);
}
}
printf("\nDequeue with timeout 1 second:\n");
for (int i = 1; i <= 5; i++) {
int value;
if (dequeueTimeout(q, &value, 1000)) {
printf("Dequeued: %d\n", value);
} else {
printf("Failed to dequeue (timeout)\n");
}
}
freeBlockingQueue(q);
return 0;
}

Queue Applications

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// ============================================================
// PRACTICAL APPLICATIONS OF QUEUES
// ============================================================
// 1. Task Scheduler
typedef struct {
int taskId;
char taskName[50];
int priority;
void (*taskFunc)(void*);
void *args;
} Task;
typedef struct {
Task **tasks;
int front;
int rear;
int size;
int capacity;
} TaskQueue;
TaskQueue* createTaskQueue(int capacity) {
TaskQueue *tq = (TaskQueue*)malloc(sizeof(TaskQueue));
tq->tasks = (Task**)malloc(capacity * sizeof(Task*));
tq->front = 0;
tq->rear = 0;
tq->size = 0;
tq->capacity = capacity;
return tq;
}
void scheduleTask(TaskQueue *tq, Task *task) {
if (tq->size == tq->capacity) {
printf("Task queue full!\n");
return;
}
tq->tasks[tq->rear] = task;
tq->rear = (tq->rear + 1) % tq->capacity;
tq->size++;
printf("Task scheduled: %s\n", task->taskName);
}
Task* getNextTask(TaskQueue *tq) {
if (tq->size == 0) return NULL;
Task *task = tq->tasks[tq->front];
tq->front = (tq->front + 1) % tq->capacity;
tq->size--;
return task;
}
// 2. Print Spooler
typedef struct {
char **documents;
int front;
int rear;
int size;
int capacity;
} PrintQueue;
PrintQueue* createPrintQueue(int capacity) {
PrintQueue *pq = (PrintQueue*)malloc(sizeof(PrintQueue));
pq->documents = (char**)malloc(capacity * sizeof(char*));
pq->front = 0;
pq->rear = 0;
pq->size = 0;
pq->capacity = capacity;
return pq;
}
void addPrintJob(PrintQueue *pq, const char *doc) {
if (pq->size == pq->capacity) {
printf("Print queue full!\n");
return;
}
pq->documents[pq->rear] = strdup(doc);
pq->rear = (pq->rear + 1) % pq->capacity;
pq->size++;
printf("Added to print queue: %s\n", doc);
}
char* getNextPrintJob(PrintQueue *pq) {
if (pq->size == 0) return NULL;
char *doc = pq->documents[pq->front];
pq->front = (pq->front + 1) % pq->capacity;
pq->size--;
return doc;
}
// 3. BFS Graph Traversal using Queue
#define MAX_NODES 100
typedef struct {
int nodes[MAX_NODES][MAX_NODES];
int numNodes;
} Graph;
void bfs(Graph *g, int start) {
bool visited[MAX_NODES] = {false};
int queue[MAX_NODES];
int front = 0, rear = 0;
visited[start] = true;
queue[rear++] = start;
printf("BFS traversal starting from node %d: ", start);
while (front < rear) {
int current = queue[front++];
printf("%d ", current);
for (int i = 0; i < g->numNodes; i++) {
if (g->nodes[current][i] && !visited[i]) {
visited[i] = true;
queue[rear++] = i;
}
}
}
printf("\n");
}
int main() {
printf("=== Queue Applications ===\n\n");
// Task scheduler demo
printf("--- Task Scheduler ---\n");
TaskQueue *tq = createTaskQueue(5);
Task tasks[3] = {
{1, "Process Data", 1, NULL, NULL},
{2, "Send Email", 2, NULL, NULL},
{3, "Generate Report", 3, NULL, NULL}
};
for (int i = 0; i < 3; i++) {
scheduleTask(tq, &tasks[i]);
}
printf("\nProcessing tasks:\n");
Task *next;
while ((next = getNextTask(tq)) != NULL) {
printf("Processing: %s\n", next->taskName);
}
// Print spooler demo
printf("\n--- Print Spooler ---\n");
PrintQueue *pq = createPrintQueue(3);
addPrintJob(pq, "Document1.pdf");
addPrintJob(pq, "Document2.pdf");
addPrintJob(pq, "Document3.pdf");
addPrintJob(pq, "Document4.pdf");  // Should fail
printf("\nPrinting jobs:\n");
char *job;
while ((job = getNextPrintJob(pq)) != NULL) {
printf("Printing: %s\n", job);
free(job);
}
// BFS traversal demo
printf("\n--- BFS Graph Traversal ---\n");
Graph g;
g.numNodes = 6;
memset(g.nodes, 0, sizeof(g.nodes));
// Create a sample graph
g.nodes[0][1] = g.nodes[0][2] = 1;
g.nodes[1][3] = g.nodes[1][4] = 1;
g.nodes[2][5] = 1;
bfs(&g, 0);
return 0;
}

Queue Performance Comparison

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// ============================================================
// PERFORMANCE COMPARISON OF DIFFERENT QUEUE IMPLEMENTATIONS
// ============================================================
// Use the queue implementations from above
// (CircularQueue, LinkedListQueue)
void benchmarkQueues() {
const int OPERATIONS = 100000;
clock_t start, end;
printf("=== Performance Comparison ===\n\n");
printf("Operations: %d enqueues + %d dequeues\n\n", OPERATIONS, OPERATIONS);
// Test circular queue
CircularQueue *cq = createQueue(OPERATIONS + 10);
start = clock();
for (int i = 0; i < OPERATIONS; i++) {
enqueue(cq, i);
}
for (int i = 0; i < OPERATIONS; i++) {
dequeue(cq);
}
end = clock();
printf("Circular Queue: %.3f seconds\n", 
(double)(end - start) / CLOCKS_PER_SEC);
freeQueue(cq);
// Test linked list queue
LinkedListQueue *lq = createLLQueue();
start = clock();
for (int i = 0; i < OPERATIONS; i++) {
enqueueLL(lq, i);
}
for (int i = 0; i < OPERATIONS; i++) {
dequeueLL(lq);
}
end = clock();
printf("Linked List Queue: %.3f seconds\n", 
(double)(end - start) / CLOCKS_PER_SEC);
freeLLQueue(lq);
printf("\nNotes:\n");
printf("- Circular queue: faster, fixed size, cache-friendly\n");
printf("- Linked list: flexible size, more memory overhead\n");
printf("- Choice depends on requirements: speed vs flexibility\n");
}
int main() {
benchmarkQueues();
return 0;
}

Best Practices and Common Pitfalls

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// BEST PRACTICES AND COMMON PITFALLS
// ============================================================
// PITFALL 1: Not handling empty/full conditions properly
// SOLUTION: Always check before operations
// PITFALL 2: Memory leaks in linked list queues
// SOLUTION: Properly free all nodes
// PITFALL 3: Integer overflow in array indices
// SOLUTION: Use modulo operations for circular queues
// PITFALL 4: Not considering thread safety
// SOLUTION: Use mutex for concurrent access
// PITFALL 5: Inefficient resizing strategy
// SOLUTION: Double capacity when full, halve when quarter full
// Best Practice 1: Define clear interface
typedef struct {
void *data;        // Generic pointer for any data type
size_t elementSize;
int front;
int rear;
int size;
int capacity;
} GenericQueue;
GenericQueue* createGenericQueue(int capacity, size_t elemSize) {
GenericQueue *q = (GenericQueue*)malloc(sizeof(GenericQueue));
q->data = malloc(capacity * elemSize);
q->elementSize = elemSize;
q->front = 0;
q->rear = 0;
q->size = 0;
q->capacity = capacity;
return q;
}
bool enqueueGeneric(GenericQueue *q, void *value) {
if (q->size == q->capacity) return false;
void *dest = (char*)q->data + (q->rear * q->elementSize);
memcpy(dest, value, q->elementSize);
q->rear = (q->rear + 1) % q->capacity;
q->size++;
return true;
}
bool dequeueGeneric(GenericQueue *q, void *result) {
if (q->size == 0) return false;
void *src = (char*)q->data + (q->front * q->elementSize);
memcpy(result, src, q->elementSize);
q->front = (q->front + 1) % q->capacity;
q->size--;
return true;
}
// Best Practice 2: Use assertions in debug mode
#ifdef DEBUG
#define ASSERT_QUEUE_VALID(q) \
assert(q != NULL); \
assert(q->size >= 0); \
assert(q->size <= q->capacity); \
assert(q->front >= 0 && q->front < q->capacity); \
assert(q->rear >= 0 && q->rear < q->capacity);
#else
#define ASSERT_QUEUE_VALID(q)
#endif
// Best Practice 3: Provide comprehensive error information
typedef enum {
QUEUE_SUCCESS,
QUEUE_EMPTY,
QUEUE_FULL,
QUEUE_INVALID_PARAM,
QUEUE_MEMORY_ERROR
} QueueError;
QueueError enqueueWithError(GenericQueue *q, void *value, char *errorMsg) {
if (q == NULL || value == NULL) {
strcpy(errorMsg, "Null pointer provided");
return QUEUE_INVALID_PARAM;
}
if (q->size == q->capacity) {
strcpy(errorMsg, "Queue is full");
return QUEUE_FULL;
}
// ... rest of implementation
return QUEUE_SUCCESS;
}
int main() {
printf("=== Generic Queue (type-safe) ===\n\n");
// Integer queue
GenericQueue *intQueue = createGenericQueue(5, sizeof(int));
int val = 42;
enqueueGeneric(intQueue, &val);
val = 100;
enqueueGeneric(intQueue, &val);
int result;
dequeueGeneric(intQueue, &result);
printf("Dequeued int: %d\n", result);
free(intQueue->data);
free(intQueue);
// Double queue
GenericQueue *doubleQueue = createGenericQueue(5, sizeof(double));
double dval = 3.14159;
enqueueGeneric(doubleQueue, &dval);
double dresult;
dequeueGeneric(doubleQueue, &dresult);
printf("Dequeued double: %f\n", dresult);
free(doubleQueue->data);
free(doubleQueue);
return 0;
}

Summary Table

Conclusion

Queues are fundamental data structures with wide-ranging applications in systems programming. This guide covered:

1. Array-based circular queues for fixed-size, high-performance needs
2. Dynamic queues for flexible capacity requirements
3. Linked list queues for unlimited size and dynamic memory
4. Deques for double-ended operations
5. Priority queues for ordered processing
6. Thread-safe queues for concurrent programming
7. Circular buffers for streaming data
8. Practical applications in task scheduling, printing, and graph algorithms

Key takeaways:

• Choose implementation based on requirements: fixed vs dynamic size, single vs multiple threads, priority needs
• Always handle empty/full conditions gracefully
• Consider memory management carefully, especially in linked implementations
• For concurrent access, proper synchronization is essential
• Profile different implementations for your specific use case

Mastering queue implementations in C provides the foundation for building efficient systems, from embedded devices to large-scale distributed applications.