Loading...

C essentialsData Structures

Data structures: stacks & queues

15 min lesson

Next
  • A stack and a queue are two simple ways to store items with strict rules about the order they come out: a stack is last-in, first-out (LIFO), and a queue is first-in, first-out (FIFO).
  • They matter because many real problems follow these rules: undo history, function calls, print jobs and task scheduling.
  • Think of a stack as a pile of plates: you add and remove from the top only. A queue is like a line at a counter: the first person in is the first served.
  • A stack has push (add to top) and pop (remove from top); the most recent item comes out first.
  • A queue has enqueue (add to back) and dequeue (remove from front); the oldest item comes out first.
  • Both can be built on an array or a linked list; the array version needs a capacity and a top or front/back index.
  • The computer keeps a top index for a stack and front/back indices for a queue, updating them on each operation.
  • The syntax for a simple array stack is: int stack[N]; int top = -1; then stack[++top] = x; and x = stack[top--];.
  • A realistic use: a stack for matching brackets or undo, and a queue for handling tasks in the order they arrive.
  • A surprising detail: a naive array queue wastes space as front advances; a circular buffer reuses the slots and is the standard trick.
  • The example program implements a small array stack and a small array queue, pushes and enqueues values, then pops and dequeues them in order.
Keep in mind
  • Use a stack when the most recent item should come out first; use a queue for first-in, first-out.
  • Always check for empty before popping or dequeuing, and for full before pushing or enqueuing.
  • Use a circular buffer for array-based queues to avoid wasting slots.
  • These structures appear everywhere; learn them well.
  • You are building real algorithmic intuition. Excellent work!
main.c
#include <stdio.h>

#define CAP 4

int main(void) {
    // Array-based stack with top index starting at -1 (empty)
    int stack[CAP];
    int top = -1;
    // Push three values onto the stack
    stack[++top] = 1;
    stack[++top] = 2;
    stack[++top] = 3;
    // Pop them: last in, first out
    while (top >= 0) {
        printf("pop: %d\n", stack[top--]);
    }

    // Array-based queue with front and back indices
    int queue[CAP];
    int front = 0;
    int back = 0;
    // Enqueue three values at the back
    queue[back++] = 10;
    queue[back++] = 20;
    queue[back++] = 30;
    // Dequeue from the front: first in, first out
    while (front < back) {
        printf("dequeue: %d\n", queue[front++]);
    }

    return 0;
}

What happens: pop: 3 pop: 2 pop: 1 dequeue: 10 dequeue: 20 dequeue: 30

Breaking it down

Stack array

int stack[CAP]; int top = -1;

The array holds the items and top marks the last used index. -1 means the stack is empty.

Push

stack[++top] = 1;

Increments top first, then stores the value at the new top. This adds to the top of the stack.

Pop

stack[top--]

Reads the value at top, then decrements top. This removes the most recent item.

Queue indices

int front = 0; int back = 0;

front points to the next item to dequeue and back points to the next free slot. Empty when front == back.

Dequeue

queue[front++]

Reads the item at front, then moves front forward. This removes the oldest item.

Stack vs queue

FeatureStackQueue
OrderLIFOFIFO
Addpush (top)enqueue (back)
Removepop (top)dequeue (front)
Empty checktop == -1front == back
Example useUndo, bracketsPrint jobs, tasks

A helpful analogy

A stack is like a pile of plates: you add and remove from the top, so the last plate placed is the first one taken. A queue is like a line at a counter: the first person in is the first one served, and new people join at the back.

Nesting rules

  • 1.Check for empty before pop or dequeue; reading from an empty structure is a bug.
  • 2.Check for full before push or enqueue in an array-based version.
  • 3.For a stack, increment top before storing and decrement after reading.
  • 4.For a circular queue, wrap indices with modulo: back = (back + 1) % CAP.

Common mistakes

Popping an empty stack

Avoid

int x = stack[top--]; // top may be -1

Use instead

if (top >= 0) { int x = stack[top--]; }

When top is -1 the stack is empty and reading stack[-1] is undefined behavior.

Using a linear queue until it fills

Avoid

queue[back++] = x; // back keeps growing

Use instead

queue[back] = x; back = (back + 1) % CAP;

A linear queue wastes space as front advances. A circular buffer reuses the freed slots.

Confusing push and enqueue order

Avoid

expecting a stack to be FIFO

Use instead

use a queue for FIFO behavior

A stack removes the most recent item; a queue removes the oldest. Choose the structure that matches the rule you need.

Quick tips

  • •Write is_empty and is_full helpers to keep the checks in one place.
  • •Draw the top, front and back indices while tracing small examples.
  • •Try filling the stack past CAP to see the need for a full check.
  • •Implement a circular queue next; it is a common interview topic.
  • •Use a linked list for unbounded stacks and queues when CAP is unknown.
Previous
Next