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

System Programming: Message queues, process scheduling, and interrupt handling
Data Buffering: I/O buffers, network packet queues, and streaming data
Algorithm Design: BFS graph traversal, level-order tree traversal
Resource Management: Thread pools, connection pools, and request queues
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

Implementation	Pros	Cons	Best Use Case
Array Circular	Fast, cache-friendly	Fixed size	Known max size, performance critical
Dynamic Array	Auto-resizing	Occasional resize cost	Unknown size, good performance
Linked List	Unlimited size	More memory, slower	Frequent inserts/deletes
Deque	Both ends accessible	More complex	Sliding windows, palindrome checking
Priority Queue	Priority ordering	O(log n) operations	Task scheduling
Thread-Safe	Concurrent access	Lock overhead	Multi-threaded applications
Circular Buffer	Fixed size, overwrite	Data loss on overwrite	Real-time data streaming

Conclusion

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

Array-based circular queues for fixed-size, high-performance needs
Dynamic queues for flexible capacity requirements
Linked list queues for unlimited size and dynamic memory
Deques for double-ended operations
Priority queues for ordered processing
Thread-safe queues for concurrent programming
Circular buffers for streaming data
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.

Complete C Programming Guide + Compilers Collection

1. C srand() Function – Understanding Seed Initialization

https://macronepal.com/understanding-the-c-srand-function
Explains how srand() initializes the pseudo-random number generator in C by setting a seed value. Using the same seed produces the same sequence, while time(NULL) gives different results each run.

2. C rand() Function Mechanics and Limitations

https://macronepal.com/c-rand-function-mechanics-and-limitations
Explains how rand() generates pseudo-random numbers between 0 and RAND_MAX, its deterministic nature, and limitations for security use cases.

3. C log() Function

https://macronepal.com/c-log-function-2
Covers natural logarithm calculation using <math.h> and its applications.

4. Mastering Date and Time in C

https://macronepal.com/mastering-date-and-time-in-c
Explains <time.h> functions like time(), clock(), difftime(), and struct tm.

5. Mastering time_t Type in C

https://macronepal.com/mastering-the-c-time_t-type-for-time-management
Explains time representation as seconds since Unix epoch and conversion functions.

6. C exp() Function

https://macronepal.com/c-exp-function-mechanics-and-implementation
Explains exponential function exp(x) and its scientific applications.

7. C log() Function (Alternate Guide)

https://macronepal.com/c-log-function
Comparison of log() and log10() with usage examples.

8. C log10() Function

https://macronepal.com/mastering-the-log10-function-in-c
Explains base-10 logarithm for engineering and scientific applications.

9. C tan() Function

https://macronepal.com/understanding-the-c-tan-function
Explains tangent function and radian-based calculations.

10. Random Numbers in C (Secure vs Predictable)

https://macronepal.com/mastering-c-random-numbers-for-secure-and-predictable-applications
Explains difference between rand() and secure randomness methods.

11. Free Online C Compiler

https://macronepal.com/free-online-c-code-compiler-2
Browser-based compiler for testing C programs instantly.

C Functions, Arguments, Parameters & Flow

Mastering Functions in C – Complete Guide

https://macronepal.com/c/mastering-functions-in-c-a-complete-guide/
Covers function structure, modular programming, and real-world usage.

Function Arguments in C

https://macronepal.com/c-function-arguments/
Explains how arguments are passed and used in function calls.

Function Parameters in C

https://macronepal.com/c-function-parameters/
Explains defining inputs for functions and matching them with arguments.

Function Declarations in C

https://macronepal.com/c-function-declarations-syntax-rules-and-best-practices/
Covers prototypes, syntax rules, and best practices.

Function Calls in C

https://macronepal.com/understanding-function-calls-in-c-syntax-mechanics-and-best-practices/
Explains execution flow and parameter handling during function calls.

Void Functions in C

https://macronepal.com/understanding-void-functions-in-c-syntax-patterns-and-best-practices/
Explains functions that do not return values.

Return Values in C

https://macronepal.com/c-return-values-mechanics-types-and-best-practices/
Explains different return types and how functions return results.

Pass-by-Value in C

https://macronepal.com/aws/understanding-pass-by-value-in-c-mechanics-implications-and-best-practices/
Explains how copies of variables are passed into functions.

Pass-by-Reference in C

https://macronepal.com/c/understanding-pass-by-reference-in-c-pointers-semantics-and-safe-practices/
Explains using pointers to modify original variables.

C strstr() Function

https://macronepal.com/aws/c-strstr-function/
Explains substring search inside strings in C.

C Preprocessor & Macros

C Structures, Memory, Scope & Linkage

C Scope, Storage Classes & Typedef

Extra Articles

https://macronepal.com/13757-2/
https://macronepal.com/13748-2/
https://macronepal.com/13747-2/
https://macronepal.com/13746-2/
https://macronepal.com/13745-2/
https://macronepal.com/13708-2/
https://macronepal.com/13707-2/
https://macronepal.com/13702-2/

Online Compilers