Skip to content
Tutorials Center
My learning

Topics

Lesson 85 of 135 ยท Data Structures in C

Stacks and Queues

Implement stacks and queues in C with arrays and linked lists, build a circular buffer queue, handle overflow and underflow, and use a stack to match brackets.

A stack and a queue are both containers where you can't reach into the middle. You add items and take them out again, and the only difference is which item comes out. A stack hands back the item added most recently, last in, first out (LIFO), like a pile of plates. A queue hands back the oldest item, first in, first out (FIFO), like people waiting at a ticket counter.

These two rules sound almost too simple to deserve a lesson, yet they're everywhere: the call stack that runs your functions (Recursion), undo history in editors, expression parsers, keyboard and network buffers, print spoolers, task schedulers and breadth-first search. In this lesson you'll implement both on top of arrays and on top of linked lists, build the circular buffer that real-time and embedded code relies on, and use a stack to check brackets in source code.

The operations

Both structures have a tiny interface. Each operation should run in O(1), constant time, regardless of how many items are stored:

Stack Queue Meaning
push enqueue Add an item
pop dequeue Remove and return the next item
peek / top peek / front Look at the next item without removing it
is_empty is_empty Are there any items?

Two error conditions matter in C, because nothing checks them for you: underflow (popping from an empty container) and overflow (pushing into a full fixed-size one). A good C design reports them through the return value instead of crashing or reading garbage. The examples below return bool and deliver the value through a pointer parameter, a pattern from Pointers and Functions.

A stack on an array

The simplest stack is an array plus a count. Items occupy indexes 0 to count - 1, and the top is at count - 1. Push writes at items[count] and increments; pop decrements and reads. Nothing ever shifts, which is why both are O(1).

C A fixed-capacity array stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The output shows LIFO order clearly: 10 to 40 are pushed, pushing 50 fails because the capacity is 4, peek reports top is 40, and the pops come out as 40, 30, 20, 10. The post-increment in items[s->count++] and the pre-decrement in items[--s->count] are deliberate: push writes then moves up, pop moves down then reads (see Assignment and Increment Operators).

A fixed capacity is fine when you know the maximum depth (embedded code often does). Otherwise, grow the array with realloc when it fills up, exactly like the dynamic array you built earlier:

C
bool stack_push(struct int_stack *s, int value)
{
    if (s->count == s->capacity) {
        size_t new_capacity = s->capacity == 0 ? 8 : s->capacity * 2;
        int *bigger = realloc(s->items, new_capacity * sizeof *bigger);
        if (bigger == NULL) {
            return false;                /* the old array is still valid */
        }
        s->items = bigger;
        s->capacity = new_capacity;
    }
    s->items[s->count++] = value;
    return true;
}

Doubling keeps pushes O(1) amortized: most pushes are cheap, and the occasional copy is paid for by all the cheap ones before it.

A stack on a linked list

A singly linked list makes a natural stack: push and pop both happen at the head, which is O(1) and never runs out of room until memory does. Each item costs an allocation, though, so array stacks are usually faster. This version stores strings, which shows a typical ownership rule: the stack keeps its own copy of each string and frees it on pop.

C An undo history on a linked stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Undo pops delete 'world' first, then type ' world', and two edits remain. Notice the contract in the comment above pop_text: ownership of the string moves to the caller, who must free it. Documenting who frees what is essential in C, where nothing does it automatically.

Using a stack: matching brackets

Compilers, editors and JSON parsers all need to check that brackets are balanced: every (, [ or { must be closed by the matching character in the right order. A stack solves it in one pass. Push each opener; for each closer, pop and check that it matches. At the end the stack must be empty.

Why a stack? Because the bracket that must be closed next is always the one opened most recently. That's LIFO by definition. This program checks every line in the Input box:

C Bracket checker

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The first and last lines pass. The second reports 2 bracket(s) never closed (the first ( and the { at the end), the third reports expected ']' but found ')' at column 13 (the closers are crossed), and }{ fails at column 1 because a closer arrives with nothing open. Characters inside string literals would need extra handling in a real parser, which is a nice exercise.

The same push-and-pop rhythm powers postfix (RPN) evaluation, undo/redo, depth-first search, and the conversion of infix expressions like 2 + 3 * 4 into a form a machine can evaluate, which you'll use in the calculator project.

A queue as a circular buffer

A queue needs two ends: items join at the back and leave from the front. With a plain array, removing from the front would mean shifting every item left (O(n)), and just advancing a front index would waste the space behind it forever.

The fix is a circular buffer (also called a ring buffer): when an index runs off the end of the array, it wraps around to 0. You store the index of the front item and the number of items; the back position is computed from them:

TEXT
capacity 5, head = 3, count = 3
index:   0     1     2     3     4
       [ C ] [   ] [   ] [ A ] [ B ]
                          front       back wraps to index 0

The modulo operator does the wrapping: (head + count) % capacity is where the next item goes. Using a count (instead of comparing head and tail) makes "full" and "empty" easy to tell apart.

C A ring buffer queue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Follow the head value in the output. After two items are served, head is 2. Adding 500, 600 and 700 fills the buffer by wrapping around to indexes 4, 0 and 1, so 800 is rejected. The final loop serves 300 through 700 in arrival order, and the queue ends empty with head=2: the indexes kept moving, but no item was ever shifted.

Tip: If the capacity is a power of two, index & (capacity - 1) gives the same result as index % capacity for unsigned indexes, and it's a classic trick in high-performance ring buffers (see Bitwise Operators). With -O1 and a constant capacity, the compiler does this for you anyway.

A queue on a linked list

For an unbounded queue, use a linked list with two pointers: head for removing and tail for appending, so both operations are O(1). The only subtle cases are the transitions between empty and non-empty, where both pointers must be updated:

C A linked queue of print jobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Jobs print in submission order, 101, 102, 103, then the late arrival 104, for 22 pages in total. Forgetting to reset tail when the last item leaves is the classic bug here: the next submit would write through a dangling pointer to freed memory.

Choosing an implementation

Array (fixed) Array (growing) Linked list
Push/enqueue O(1), may be full O(1) amortized O(1), one malloc each
Pop/dequeue O(1) O(1) O(1), one free each
Memory fixed, no allocation contiguous, some slack pointer + allocator overhead per item
Cache behavior excellent excellent poor
Typical use embedded, interrupts, audio buffers general purpose items already allocated elsewhere, unbounded queues

A deque (double-ended queue) allows pushing and popping at both ends; a ring buffer extends to one easily by also moving head backwards. A priority queue, where the most urgent item comes out first, is usually built on a binary heap, a cousin of the binary trees in the next lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. You push 1, 2 and 3 onto a stack, pop once, then push 4. What does the next pop return?

    After the first pop removes 3, the stack holds 1 and 2. Pushing 4 puts it on top, so it comes out next (LIFO).
  2. 2. You enqueue A, B, C, dequeue once, then enqueue D. What does the next dequeue return?

    The first dequeue removed A. The oldest remaining item is B, so it is served next (FIFO).
  3. 3. In the ring buffer with capacity 5, head is 3 and count is 2. Where does enqueue store the next item?

    (head + count) % capacity is (3 + 2) % 5, which is 0: the index wraps around to the start of the array.
  4. 4. Why does a stack fit bracket matching so well?

    Brackets nest, so closers must appear in reverse order of their openers, which is exactly last in, first out.
  5. 5. In the linked queue, what goes wrong if next_job doesn't reset tail when the queue becomes empty?

    tail would still point at the node that was just freed, so q->tail->next = j is a use-after-free.

Summary

  • A stack is LIFO (push, pop, peek at one end); a queue is FIFO (enqueue at the back, dequeue at the front). All core operations should be O(1).
  • Report overflow and underflow with return values; deliver popped values through a pointer parameter.
  • An array stack is an array plus a count; grow it with realloc and doubling for amortized O(1) pushes.
  • A linked stack pushes and pops at the head; document who owns (and frees) the stored data.
  • A circular buffer queue wraps indexes with % capacity and tracks head and count, so nothing ever shifts.
  • A linked queue keeps head and tail pointers and must update both when it becomes empty or stops being empty.
  • Stacks solve nesting problems such as bracket matching and expression parsing; queues model waiting lines and buffers.

Next: Binary Search Trees, where nodes get two children and searching becomes much faster than walking a list.