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
| 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.
#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).
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.
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
| 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 beforepop/dequeue. - Writing
stack[top++] = xwithtopstarting at -1 — it writes tostack[-1]. Withtop = -1, usestack[++top]. - A linear queue that never reuses space — use the circular version with
% MAX. - Forgetting
freein the linked-list pop (a memory leak). - Passing
topinstead of&topto 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:
topstarts at -1; pushstack[++top] = x, popstack[top--]. - Linked-list stack: push and pop at the head; pass
struct node **to change the top. - Circular queue:
index = (index + 1) % MAXreuses freed slots; trackcount. - Balanced brackets: push openers, match closers with the top, end with an empty stack.