Stacks & Queues
Stacks and queues are abstract data types that dictate the order in which elements come and go. In C you build them out of whatever's handy: an array, a linked list, sometimes both stitched together.
Stack: Last In, First Out (LIFO)
Two operations and that's it: push drops a value on top, pop plucks one off.
#define MAX_SIZE 100
typedef struct { int data[MAX_SIZE]; int top;} Stack;
void stack_init(Stack *s) { s->top = -1; }
int stack_push(Stack *s, int value) { if (s->top >= MAX_SIZE - 1) return -1; // overflow s->data[++s->top] = value; return 0;}
int stack_pop(Stack *s, int *out) { if (s->top < 0) return -1; // underflow *out = s->data[s->top--]; return 0;}Both functions return 0 for success and -1 for failure, and stack_pop hands back the value through the out pointer. That split is deliberate. If pop returned the value directly, which int would mean "the stack was empty"? Any value you picked, -1 included, could also be real data. Returning a status and writing the result through a pointer is the usual C answer, and you'll see it all over the standard library and POSIX.
Predict: starting empty, push 1, 2 and 3, pop twice, push 4, then pop twice more. Which values come out of those four pops, in order?
3, 2, 4, 1. The first two pops take the newest values, 3 then 2, leaving only 1 with top at 0. Pushing 4 puts it at data[1] on top of the 1, so the next pop returns 4 and the last one finally reaches 1, the first value pushed.
Where You'll Meet Them
A stack fits any job where the most recent thing has to be dealt with first: undo history, matching brackets in a parser, walking a tree without recursion. Every running C program keeps one too. Each function call pushes a frame holding its return address and local variables, and each return pops it again, which is the call stack from the memory model lesson. Queues suit work that should be handled in arrival order: keystrokes waiting for a program to read them, packets waiting to be sent, jobs waiting for a worker.
Queue: First In, First Out (FIFO)
A queue gives you enqueue at the back and dequeue from the front. Naively, that means shuffling every element forward on each dequeue. A circular buffer dodges all of that by letting front and rear walk around the array, modulo its size:
typedef struct { int data[MAX_SIZE]; int front; int rear; int count;} Queue;
void queue_init(Queue *q) { q->front = 0; q->rear = -1; q->count = 0;}
int queue_enqueue(Queue *q, int value) { if (q->count >= MAX_SIZE) return -1; q->rear = (q->rear + 1) % MAX_SIZE; q->data[q->rear] = value; q->count++; return 0;}
int queue_dequeue(Queue *q, int *out) { if (q->count <= 0) return -1; *out = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; q->count--; return 0;}The modular indexing (% MAX_SIZE) makes the array's tail loop back around to the head, recycling slots that dequeue has freed up. Enqueue and dequeue stay O(1) and nothing ever needs to be memmoved.
Worked Example: A Queue Wrapping Round
Take the queue above with MAX_SIZE set to 4 and trace each call. Watch rear jump from 3 back to 0:
| Call | front | rear | count | data[0..3] | Returns |
|---|---|---|---|---|---|
queue_init | 0 | -1 | 0 | _ _ _ _ | |
| enqueue 10 | 0 | 0 | 1 | 10 _ _ _ | 0 |
| enqueue 20 | 0 | 1 | 2 | 10 20 _ _ | 0 |
| enqueue 30 | 0 | 2 | 3 | 10 20 30 _ | 0 |
| dequeue | 1 | 2 | 2 | 10 20 30 _ | 10 |
| dequeue | 2 | 2 | 1 | 10 20 30 _ | 20 |
| enqueue 40 | 2 | 3 | 2 | 10 20 30 40 | 0 |
| enqueue 50 | 2 | 0 | 3 | 50 20 30 40 | 0 |
| dequeue | 3 | 0 | 2 | 50 20 30 40 | 30 |
The enqueue of 50 computes (3 + 1) % 4 = 0 and writes over the 10 that was dequeued earlier. Dequeue never erases anything: the old 10, 20 and 30 stay in the array until a later enqueue overwrites them. Only front, rear and count decide which slots hold live data.
Step through the same nine calls. Grey slots still hold old values that dequeue left behind; only the bright ones are live. Before step 8, predict which slot 50 lands in.
Queue with MAX_SIZE 4
int queue_enqueue(Queue *q, int value) {if (q->count >= MAX_SIZE) return -1;q->rear = (q->rear + 1) % MAX_SIZE;q->data[q->rear] = value;q->count++;return 0;}int queue_dequeue(Queue *q, int *out) {if (q->count <= 0) return -1;*out = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;q->count--;return 0;}
Why keep a separate count? Without it, front == rear (in a version where rear points one past the last element) means both "empty" and "full", and you can't tell which. The other classic fix drops count and deliberately leaves one slot unused, so the queue reports full one element early and the two states never look alike.
Linked List Variants
Both structures port over to linked lists too, which kills the fixed-size cap at the cost of a malloc per push or enqueue (and a free per pop or dequeue). A stack needs only a head pointer: push inserts a new node at the head and pop removes it, both O(1). A queue needs a tail pointer as well. Enqueue appends after tail and dequeue removes from head; without tail, every enqueue would walk the whole list to find the end.
Pick based on what hurts more: a hard upper bound, or an allocation on every operation. Arrays usually win on raw speed, since the elements sit next to each other in memory and there's no allocator call; linked-list versions win on flexibility.