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

Source: https://skills101.in/learn/c-programming/c-stack-and-queue — Skills101 free tutorial (C Programming). Updated 2026-11-21.

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

| | Stack | Queue |
|---|---|---|
| Order | **LIFO** — last in, first out | **FIFO** — first in, first out |
| Real-life picture | a pile of plates | people in a railway ticket line |
| Add | `push` (on the top) | `enqueue` (at the rear) |
| Remove | `pop` (from the top) | `dequeue` (from the front) |
| Look without removing | `peek` / `top` | `front` |

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`.

```c
#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;
}
```

```text
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](https://skills101.in/learn-img/c-programming/stack-array.svg)

## 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).

```c
#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;
}
```

```text
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](https://skills101.in/learn-img/c-programming/circular-queue.svg)

## 5. Circular queue using an array

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

```c
#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;
}
```

```text
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.

```c
#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;
}
```

```text
{[()()]}   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

| | Array | Linked list |
|---|---|---|
| Size | fixed at compile time | grows while memory lasts |
| Memory per item | just the value | value + a `next` pointer |
| Speed | very fast, cache-friendly | a `malloc`/`free` per operation |
| Overflow | when the array is full | only 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 quiz and free certificate: https://skills101.in/learn/c-programming/c-stack-and-queue