Skills101

AdvancedC Programming · Lesson 19 of 21 · Updated ·

Stack and Queue in C — Array and Linked List Implementations, Circular Queue

A stack and a queue are lists with rules about where you may add and remove items. They are part of every "Data Structures using C" syllabus and are used everywhere: the call stack, undo buttons, printer queues, and ticket booking systems. In this lesson you build both yourself in C.

1. Stack and queue: the rules

StackQueue
OrderLIFO — last in, first outFIFO — first in, first out
Real-life picturea pile of platespeople in a railway ticket line
Addpush (on the top)enqueue (at the rear)
Removepop (from the top)dequeue (from the front)
Look without removingpeek / topfront

Two error conditions to always handle:

  • Overflow — adding to a structure that is full.
  • Underflow — removing from a structure that is empty.

2. Stack using an array

Keep an array and an index top that points to the topmost item. An empty stack has top = -1.

#include <stdio.h>

#define MAX 4

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

int push(int x) {
    if (top == MAX - 1) {
        printf("overflow: cannot push %d\n", x);
        return 0;
    }
    stack[++top] = x;           /* move top up, then store */
    return 1;
}

int pop(int *out) {
    if (top == -1) {
        printf("underflow: stack is empty\n");
        return 0;
    }
    *out = stack[top--];        /* read, then move top down */
    return 1;
}

int main(void) {
    int v;
    push(10); push(20); push(30); push(40);
    push(50);                                   /* the stack is full */
    while (pop(&v))
        printf("popped %d\n", v);               /* comes out in reverse */
    return 0;
}
overflow: cannot push 50
popped 40
popped 30
popped 20
popped 10
underflow: stack is empty

pop returns a success flag and gives the value through a pointer, so the caller can tell "popped a 0" from "the stack was empty". All operations are O(1).

A stack of size 4: push 10, 20, 30 moves top up from -1 to 2; pop removes 30 from the top and top goes back to 1

3. Stack using a linked list

An array stack has a fixed size. A linked list stack grows as long as memory lasts. Push and pop both work at the head of the list, so they stay O(1).

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

void push(struct node **top, int x) {          /* pointer to pointer: we change top */
    struct node *n = malloc(sizeof *n);
    if (n == NULL) { printf("out of memory\n"); return; }
    n->data = x;
    n->next = *top;                             /* new node points to the old top */
    *top = n;
}

int pop(struct node **top, int *out) {
    if (*top == NULL) return 0;                 /* underflow */
    struct node *old = *top;
    *out = old->data;
    *top = old->next;
    free(old);                                  /* no memory leak */
    return 1;
}

int main(void) {
    struct node *top = NULL;
    for (int i = 1; i <= 3; i++)
        push(&top, i * 100);
    int v;
    while (pop(&top, &v))
        printf("%d ", v);
    printf("\nempty: %s\n", top == NULL ? "yes" : "no");
    return 0;
}
300 200 100
empty: yes

We pass &top (a struct node **) because push and pop must change the caller's top pointer — C passes arguments by value, so a plain struct node * parameter would only change a copy.

4. A simple queue and its problem

A queue needs two indexes: front (where we remove) and rear (where we add). In a plain array, both only ever move forward. After some enqueues and dequeues, the free slots at the start are wasted: the queue reports "full" even though there is space.

The fix is a circular queue: when an index reaches the end of the array, it wraps around to 0. The modulo operator does this: rear = (rear + 1) % MAX.

A circular queue of size 5 drawn as a ring: after enqueue and dequeue operations, front is at slot 3 and rear has wrapped around to slot 1, so the queue holds the values in slots 3, 4, 0 and 1

5. Circular queue using an array

We keep a count of items, which makes "full" and "empty" easy to test.

#include <stdio.h>

#define MAX 5

int q[MAX];
int front = 0, rear = -1, count = 0;

int enqueue(int x) {
    if (count == MAX) { printf("overflow: %d\n", x); return 0; }
    rear = (rear + 1) % MAX;             /* wrap around */
    q[rear] = x;
    count++;
    return 1;
}

int dequeue(int *out) {
    if (count == 0) { printf("underflow\n"); return 0; }
    *out = q[front];
    front = (front + 1) % MAX;           /* wrap around */
    count--;
    return 1;
}

void show(void) {
    printf("queue:");
    for (int i = 0; i < count; i++)
        printf(" %d", q[(front + i) % MAX]);
    printf("  (front=%d rear=%d)\n", front, rear);
}

int main(void) {
    int v;
    for (int i = 1; i <= 5; i++) enqueue(i * 10);   /* 10 20 30 40 50: full */
    enqueue(60);
    dequeue(&v); dequeue(&v); dequeue(&v);          /* remove 10 20 30 */
    show();
    enqueue(60); enqueue(70);                       /* reuse freed slots */
    show();
    return 0;
}
overflow: 60
queue: 40 50  (front=3 rear=4)
queue: 40 50 60 70  (front=3 rear=1)

After three dequeues, rear wrapped from 4 to 0 and then 1, reusing the slots that 10 and 20 left behind. A plain (non-circular) queue would have reported overflow here.

6. Using a stack: balanced brackets

A classic problem: is a string like {[()()]} correctly bracketed? Push every opening bracket. For every closing bracket, the top of the stack must be its matching opener. At the end, the stack must be empty.

#include <stdio.h>
#include <string.h>

int balanced(const char *s) {
    char st[100];
    int top = -1;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == 99) return 0;            /* too deep for this stack */
            st[++top] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;            /* closer with no opener */
            char o = st[top--];
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
                return 0;                       /* wrong kind of bracket */
        }
    }
    return top == -1;                           /* nothing left open */
}

int main(void) {
    const char *tests[] = {"{[()()]}", "(a+b)*[c]", "([)]", "((", "())"};
    for (int i = 0; i < 5; i++)
        printf("%-10s %s\n", tests[i], balanced(tests[i]) ? "balanced" : "not balanced");
    return 0;
}
{[()()]}   balanced
(a+b)*[c]  balanced
([)]       not balanced
((         not balanced
())        not balanced

The same idea is used by compilers to check your code, and by calculators to evaluate expressions.

7. Which implementation to choose

ArrayLinked list
Sizefixed at compile timegrows while memory lasts
Memory per itemjust the valuevalue + a next pointer
Speedvery fast, cache-friendlya malloc/free per operation
Overflowwhen the array is fullonly when malloc fails

Common mistakes

  • Not checking for overflow before push/enqueue, or for underflow before pop/dequeue.
  • Writing stack[top++] = x with top starting at -1 — it writes to stack[-1]. With top = -1, use stack[++top].
  • A linear queue that never reuses space — use the circular version with % MAX.
  • Forgetting free in the linked-list pop (a memory leak).
  • Passing top instead of &top to a linked-list push, so the caller's pointer never changes.

Quick recap

  • Stack = LIFO (push/pop at the top); queue = FIFO (enqueue at the rear, dequeue at the front).
  • Array stack: top starts at -1; push stack[++top] = x, pop stack[top--].
  • Linked-list stack: push and pop at the head; pass struct node ** to change the top.
  • Circular queue: index = (index + 1) % MAX reuses freed slots; track count.
  • Balanced brackets: push openers, match closers with the top, end with an empty stack.

Practice what you learned

📝 Quiz: Stack and Queue in C5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →