Queues: Introduction and implementation in C

KEY TAKEAWAYS

In embedded systems programming, understanding data structures is essential for solving real-world problems. The queue is one of the most frequently used data structures, appearing in UART buffers, event systems, task schedulers, and RTOS message passing. This guide covers queue fundamentals, provides complete C implementations, and shows how queues are used in production embedded firmware.

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. Elements are added (enqueued) at the rear and removed (dequeued) from the front. The element that has been in the queue the longest is always dequeued first, just like a line of people waiting at a ticket counter.

The four fundamental queue operations are: enqueue (add to rear), dequeue (remove from front), peek (view front element without removing), and isEmpty (check if queue has no elements).

Array-Based Circular Queue Implementation

A circular queue (also called a ring buffer) is the most common queue implementation in embedded systems. It uses a fixed-size array with two indices (front and rear) that wrap around using modulo arithmetic. This eliminates the need to shift elements after each dequeue operation and provides O(1) time for all operations.

/* Circular Queue Implementation in C */
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>

#define QUEUE_SIZE 16  /* Must be a power of 2 for mask optimization */

typedef struct {
    int      data[QUEUE_SIZE];
    uint16_t head;     /* Index of front element (dequeue from here) */
    uint16_t tail;     /* Index of next free slot (enqueue here) */
    uint16_t count;    /* Number of elements currently in queue */
} CircularQueue_t;

void queue_init(CircularQueue_t *q) {
    q->head  = 0;
    q->tail  = 0;
    q->count = 0;
}

bool queue_is_empty(CircularQueue_t *q) {
    return (q->count == 0);
}

bool queue_is_full(CircularQueue_t *q) {
    return (q->count == QUEUE_SIZE);
}

bool queue_enqueue(CircularQueue_t *q, int value) {
    if (queue_is_full(q)) {
        return false;  /* Queue full, reject */
    }
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % QUEUE_SIZE;
    q->count++;
    return true;
}

bool queue_dequeue(CircularQueue_t *q, int *value) {
    if (queue_is_empty(q)) {
        return false;  /* Queue empty, nothing to dequeue */
    }
    *value = q->data[q->head];
    q->head = (q->head + 1) % QUEUE_SIZE;
    q->count--;
    return true;
}

bool queue_peek(CircularQueue_t *q, int *value) {
    if (queue_is_empty(q)) {
        return false;
    }
    *value = q->data[q->head];
    return true;
}

uint16_t queue_count(CircularQueue_t *q) {
    return q->count;
}

/* Example usage */
int main(void) {
    CircularQueue_t q;
    queue_init(&q);
    int val;

    queue_enqueue(&q, 10);
    queue_enqueue(&q, 20);
    queue_enqueue(&q, 30);

    printf("Count: %d\n", queue_count(&q));

    queue_dequeue(&q, &val);
    printf("Dequeued: %d\n", val);  /* 10 */

    queue_peek(&q, &val);
    printf("Front: %d\n", val);     /* 20 */

    queue_dequeue(&q, &val);
    printf("Dequeued: %d\n", val);  /* 20 */

    queue_dequeue(&q, &val);
    printf("Dequeued: %d\n", val);  /* 30 */

    printf("Empty: %d\n", queue_is_empty(&q));  /* 1 */

    return 0;
}

Linked-List Based Queue

A linked-list queue uses dynamically allocated nodes, so it can grow and shrink as needed without a fixed maximum size. Each node contains a data value and a pointer to the next node. The queue tracks pointers to both the front and rear nodes.

/* Linked-List Queue Implementation */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

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

typedef struct {
    Node_t *front;
    Node_t *rear;
    int     count;
} LinkedQueue_t;

void lqueue_init(LinkedQueue_t *q) {
    q->front = NULL;
    q->rear  = NULL;
    q->count = 0;
}

bool lqueue_enqueue(LinkedQueue_t *q, int value) {
    Node_t *node = (Node_t *)malloc(sizeof(Node_t));
    if (!node) return false;  /* malloc failed */

    node->data = value;
    node->next = NULL;

    if (q->rear == NULL) {
        q->front = node;
        q->rear  = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    q->count++;
    return true;
}

bool lqueue_dequeue(LinkedQueue_t *q, int *value) {
    if (q->front == NULL) return false;

    Node_t *temp = q->front;
    *value = temp->data;
    q->front = temp->next;

    if (q->front == NULL) {
        q->rear = NULL;  /* Queue is now empty */
    }

    free(temp);
    q->count--;
    return true;
}

void lqueue_destroy(LinkedQueue_t *q) {
    int dummy;
    while (lqueue_dequeue(q, &dummy));
}

Queue Applications in Embedded Systems

Queues appear throughout embedded firmware. Here are the most common applications:

UART TX/RX buffers: When your UART receives data faster than your main loop can process it, a receive ring buffer stores incoming bytes until the application is ready to handle them. Similarly, a transmit buffer lets the application queue bytes for transmission without blocking while the UART hardware sends each byte. This is the single most common use of queues in embedded C.

Task scheduling: In a cooperative multitasking system without an RTOS, a simple task queue holds function pointers that the main loop executes in order. ISRs add tasks to the queue instead of doing lengthy processing themselves, keeping interrupt latency low.

Event queues: Button presses, sensor alerts, and communication events are queued as event structures and processed by an event handler in the main loop. This decouples event detection (often in ISRs) from event processing (in main context), following the producer-consumer pattern.

ISR-Safe Queue Implementation

When an ISR writes to a queue and the main loop reads from it (or vice versa), you must handle concurrency carefully. Without protection, the ISR can interrupt the main loop in the middle of modifying the queue, corrupting the data structure. Here is a bare-metal ISR-safe ring buffer for a UART receive path:

/* ISR-Safe Ring Buffer for UART RX */
#include <stdint.h>
#include <stdbool.h>

#define UART_BUF_SIZE 64  /* Power of 2 for fast modulo via bitmask */
#define UART_BUF_MASK (UART_BUF_SIZE - 1)

typedef struct {
    volatile uint8_t  buffer[UART_BUF_SIZE];
    volatile uint16_t head;  /* Written by ISR (producer) */
    volatile uint16_t tail;  /* Read by main loop (consumer) */
} UartRxBuffer_t;

static UartRxBuffer_t rx_buf = { .head = 0, .tail = 0 };

/* Called from UART RX interrupt handler */
void uart_rx_isr_handler(uint8_t byte) {
    uint16_t next_head = (rx_buf.head + 1) & UART_BUF_MASK;
    if (next_head != rx_buf.tail) {  /* Not full */
        rx_buf.buffer[rx_buf.head] = byte;
        rx_buf.head = next_head;
    }
    /* If full, byte is silently dropped */
}

/* Called from main loop */
bool uart_rx_read(uint8_t *byte) {
    if (rx_buf.head == rx_buf.tail) {
        return false;  /* Empty */
    }
    *byte = rx_buf.buffer[rx_buf.tail];
    rx_buf.tail = (rx_buf.tail + 1) & UART_BUF_MASK;
    return true;
}

uint16_t uart_rx_available(void) {
    return (rx_buf.head - rx_buf.tail) & UART_BUF_MASK;
}

/* Usage in main loop */
void process_uart_data(void) {
    uint8_t ch;
    while (uart_rx_read(&ch)) {
        process_byte(ch);
    }
}

Key points for ISR safety: declare shared variables as volatile so the compiler does not optimize away reads; use a single-producer single-consumer design where only the ISR writes head and only the main loop writes tail; this lock-free design avoids the need for disabling interrupts. If you need multiple producers or consumers, you must use critical sections (disable/enable interrupts) around the queue operations.

FreeRTOS Message Queue Example

FreeRTOS provides thread-safe message queues that handle all synchronization internally. Tasks can block while waiting for data, and ISRs can safely send to queues using the FromISR API variants.

/* FreeRTOS Queue Example: Sensor to Display */
#include "FreeRTOS.h"
#include "task.h"
#include "queue.h"

typedef struct {
    uint8_t sensor_id;
    float   value;
    uint32_t timestamp;
} SensorReading_t;

QueueHandle_t xSensorQueue;

/* Producer task: reads sensor and sends data */
void vSensorTask(void *pvParameters) {
    SensorReading_t reading;

    for (;;) {
        reading.sensor_id  = 1;
        reading.value      = read_temperature_sensor();
        reading.timestamp  = xTaskGetTickCount();

        /* Send to queue, block up to 100ms if queue is full */
        if (xQueueSend(xSensorQueue, &reading,
                       pdMS_TO_TICKS(100)) != pdPASS) {
            /* Queue full for 100ms: log error or drop reading */
            error_count++;
        }

        vTaskDelay(pdMS_TO_TICKS(500));  /* Read every 500ms */
    }
}

/* Consumer task: receives data and updates display */
void vDisplayTask(void *pvParameters) {
    SensorReading_t reading;

    for (;;) {
        /* Block indefinitely until data is available */
        if (xQueueReceive(xSensorQueue, &reading,
                          portMAX_DELAY) == pdPASS) {
            printf("Sensor %d: %.1f at tick %lurn",
                   reading.sensor_id,
                   reading.value,
                   reading.timestamp);
            update_lcd(reading.value);
        }
    }
}

/* ISR can also send to the queue */
void EXTI0_IRQHandler(void) {
    BaseType_t xHigherPriorityTaskWoken = pdFALSE;
    SensorReading_t alert = { .sensor_id = 99, .value = 0.0f };

    xQueueSendFromISR(xSensorQueue, &alert,
                      &xHigherPriorityTaskWoken);
    portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
}

int main(void) {
    /* Create queue that holds up to 10 SensorReading_t items */
    xSensorQueue = xQueueCreate(10, sizeof(SensorReading_t));

    xTaskCreate(vSensorTask,  "Sensor",  256, NULL, 2, NULL);
    xTaskCreate(vDisplayTask, "Display", 256, NULL, 1, NULL);

    vTaskStartScheduler();
    for (;;);  /* Should never reach here */
}

Priority Queue Concept

A priority queue serves elements based on their priority rather than their arrival order. Higher-priority items are dequeued before lower-priority ones, regardless of when they were added. In embedded systems, priority queues are used for interrupt-driven event handling where critical events (like safety alarms) must be processed before routine events (like display updates).

A simple implementation uses multiple regular queues, one per priority level, and the dequeue function checks the highest-priority queue first. FreeRTOS does not have a built-in priority queue, but you can achieve similar behavior by using multiple queues and a queue set, or by using event flags with priority-based task wake-up.

Common Bugs and Race Conditions

Buffer overflow: Failing to check if the queue is full before enqueuing causes the tail index to overwrite data that has not been dequeued yet. Always check the return value of your enqueue function.

Race conditions in ISR context: If both the ISR and main loop modify the same index variable, the ISR can interrupt a read-modify-write operation and corrupt the index. The solution is the single-producer single-consumer pattern (one writer per index), or wrapping operations in critical sections with interrupt disable/enable.

Missing volatile: Forgetting to declare shared variables as volatile allows the compiler to cache values in registers, so the main loop may never see changes made by the ISR. This bug is particularly insidious because it often works in debug builds (with optimizations off) and fails only in release builds.

Non-power-of-2 buffer sizes: Using a bitmask (index & MASK) instead of modulo (index % SIZE) for index wrapping only works if the buffer size is a power of 2. Using a bitmask with a non-power-of-2 size silently corrupts the queue.

Performance Comparison: Array vs Linked-List Queues

Array-based circular queue: O(1) enqueue and dequeue, fixed memory footprint, cache-friendly (contiguous memory), no dynamic allocation, deterministic timing. Ideal for embedded systems where predictable performance and no heap fragmentation are required. Downside: fixed maximum size.

Linked-list queue: O(1) enqueue and dequeue, dynamic size, can grow as needed. However, each node requires a malloc/free call (non-deterministic timing), uses extra memory for the next pointer (8 bytes on a 32-bit system per node), and has poor cache locality because nodes are scattered in memory. Generally avoided in embedded systems due to heap fragmentation risk.

For embedded systems, the array-based circular queue is almost always the right choice. Use it for UART buffers, event queues, and any fixed-capacity FIFO. Reserve linked-list queues for desktop or Linux-based embedded systems where dynamic memory is acceptable.

Read Next – POSIX Queues in C: A Complete Guide to Understand and Implement – NerdyElectronics

Vivek Bhageria

Vivek Bhageria — Lead Firmware R&D Engineer, 12+ years. Ex-Bosch (automotive powertrain), MusicTribe (real-time audio), medical devices. M.Tech BITS Pilani. I write at NerdyElectronics — practical, register-level embedded systems for engineers who want to understand what’s actually happening under the hood.

nerdyelectronics.com/about/