Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Queue
A **queue** is a first-in, first-out (FIFO) sequence.

Elements are added at the back (enqueue) and removed from the front (dequeue). A queue can be implemented over a [[linked-list]] with a head and tail pointer, over a [[circular-buffer]] for a bounded version, or as a [[lock-free-queue|lock-free queue]] for concurrent use.

```c
// linked-list-backed queue
struct node { int val; struct node *next; };

struct queue {
    struct node *head;  // dequeue from here
    struct node *tail;  // enqueue here
};

void enqueue(struct queue *q, int val) {
    struct node *n = malloc(sizeof *n);
    n->val = val; n->next = NULL;
    if (q->tail) q->tail->next = n; else q->head = n;
    q->tail = n;
}

int dequeue(struct queue *q) {
    struct node *n = q->head;
    int val = n->val;
    q->head = n->next;
    if (!q->head) q->tail = NULL;
    free(n);
    return val;
}
```

Queues are the natural structure for any processing pipeline where order must be preserved: network packet buffers, OS task schedulers (ready queues), message passing between threads (producer-consumer), and breadth-first search. When both ends need O(1) push and pop, the linked implementation or a circular buffer is preferred over a [[dynamic-array]], where dequeueing from the front would shift all remaining elements.

| Operation | Time |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek front | O(1) |
| Search | O(n) |