C Stacks and Queues: Two Data Structures Every Programmer Must Know
Table of Contents
What Are Stacks and Queues?
Stacks and queues are two of the most fundamental data structures in computer science. They show up everywhere — from how your CPU manages function calls to how your printer decides which document to print next. If you’ve been working through C Arrays and C Pointers, you already have the building blocks. Now let’s use them to build something real.
Both stacks and queues are linear data structures, meaning elements are arranged in a sequence. The difference is in how you add and remove elements.
Stack: Last In, First Out (LIFO)
Think of a stack of plates. You put plates on top, and you take plates off the top. The last plate you placed is the first one you grab. That’s LIFO — Last In, First Out.
A stack supports two primary operations:
- Push — Add an element to the top
- Pop — Remove the element from the top
- Peek — Look at the top element without removing it
Implementing a Stack with Arrays
The simplest stack implementation uses an array and a variable to track the top index. This is fast and cache-friendly, but has a fixed maximum size.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void stack_init(Stack *s) {
s->top = -1;
}
bool stack_is_empty(Stack *s) {
return s->top == -1;
}
bool stack_is_full(Stack *s) {
return s->top == MAX_SIZE - 1;
}
bool stack_push(Stack *s, int value) {
if (stack_is_full(s)) {
fprintf(stderr, "Stack overflow!\n");
return false;
}
s->data[++(s->top)] = value;
return true;
}
int stack_pop(Stack *s) {
if (stack_is_empty(s)) {
fprintf(stderr, "Stack underflow!\n");
exit(EXIT_FAILURE);
}
return s->data[(s->top)--];
}
int stack_peek(Stack *s) {
if (stack_is_empty(s)) {
fprintf(stderr, "Stack is empty!\n");
exit(EXIT_FAILURE);
}
return s->data[s->top];
}
int main(void) {
Stack s;
stack_init(&s);
stack_push(&s, 10);
stack_push(&s, 20);
stack_push(&s, 30);
printf("Top: %d\n", stack_peek(&s)); // 30
printf("Pop: %d\n", stack_pop(&s)); // 30
printf("Pop: %d\n", stack_pop(&s)); // 20
printf("Top: %d\n", stack_peek(&s)); // 10
return 0;
}Notice how top starts at -1. That’s our convention for “empty.” Every push increments it first, then stores the value. Every pop reads the value, then decrements. Simple, predictable, fast.
Implementing a Stack with Linked Lists
If you need a stack that can grow without limits, a linked list implementation is the way to go. Each node points to the one below it. Pushing creates a new head; popping removes it. If you need a refresher on how nodes and pointers work, check out C Pointers.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
int size;
} Stack;
Stack *stack_create(void) {
Stack *s = malloc(sizeof(Stack));
if (!s) {
perror("malloc");
exit(EXIT_FAILURE);
}
s->top = NULL;
s->size = 0;
return s;
}
void stack_push(Stack *s, int value) {
Node *node = malloc(sizeof(Node));
if (!node) {
perror("malloc");
exit(EXIT_FAILURE);
}
node->data = value;
node->next = s->top;
s->top = node;
s->size++;
}
int stack_pop(Stack *s) {
if (!s->top) {
fprintf(stderr, "Stack underflow!\n");
exit(EXIT_FAILURE);
}
Node *temp = s->top;
int value = temp->data;
s->top = temp->next;
free(temp);
s->size--;
return value;
}
void stack_destroy(Stack *s) {
while (s->top) {
Node *temp = s->top;
s->top = temp->next;
free(temp);
}
free(s);
}
int main(void) {
Stack *s = stack_create();
stack_push(s, 100);
stack_push(s, 200);
stack_push(s, 300);
printf("Pop: %d\n", stack_pop(s)); // 300
printf("Pop: %d\n", stack_pop(s)); // 200
stack_destroy(s);
return 0;
}The linked list version has no size limit (other than available memory), but each element requires an extra pointer’s worth of memory. For most applications, the tradeoff is worth it.
Queue: First In, First Out (FIFO)
Now picture a line at a coffee shop. The first person in line gets served first. That’s FIFO — First In, First Out.
A queue supports:
- Enqueue — Add an element to the back
- Dequeue — Remove an element from the front
- Front/Peek — Look at the front element
Implementing a Queue with Arrays
A naive array-based queue shifts all elements left on each dequeue, which is O(n). Instead, we use two indices — front and rear — to avoid shifting.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
int count;
} Queue;
void queue_init(Queue *q) {
q->front = 0;
q->rear = -1;
q->count = 0;
}
bool queue_is_empty(Queue *q) {
return q->count == 0;
}
bool queue_is_full(Queue *q) {
return q->count == MAX_SIZE;
}
bool queue_enqueue(Queue *q, int value) {
if (queue_is_full(q)) {
fprintf(stderr, "Queue is full!\n");
return false;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = value;
q->count++;
return true;
}
int queue_dequeue(Queue *q) {
if (queue_is_empty(q)) {
fprintf(stderr, "Queue is empty!\n");
exit(EXIT_FAILURE);
}
int value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->count--;
return value;
}
int main(void) {
Queue q;
queue_init(&q);
queue_enqueue(&q, 10);
queue_enqueue(&q, 20);
queue_enqueue(&q, 30);
printf("Dequeue: %d\n", queue_dequeue(&q)); // 10
printf("Dequeue: %d\n", queue_dequeue(&q)); // 20
return 0;
}Notice the modulo arithmetic: (q->rear + 1) % MAX_SIZE. This wraps the index around the array, turning it into a circular buffer. That’s already a circular queue — we’ll formalize it shortly.
Implementing a Queue with Linked Lists
For unbounded queues, a linked list works well. We keep pointers to both the front and rear for O(1) enqueue and dequeue.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
int size;
} Queue;
Queue *queue_create(void) {
Queue *q = malloc(sizeof(Queue));
if (!q) { perror("malloc"); exit(EXIT_FAILURE); }
q->front = q->rear = NULL;
q->size = 0;
return q;
}
void queue_enqueue(Queue *q, int value) {
Node *node = malloc(sizeof(Node));
if (!node) { perror("malloc"); exit(EXIT_FAILURE); }
node->data = value;
node->next = NULL;
if (q->rear) {
q->rear->next = node;
} else {
q->front = node; // First element
}
q->rear = node;
q->size++;
}
int queue_dequeue(Queue *q) {
if (!q->front) {
fprintf(stderr, "Queue is empty!\n");
exit(EXIT_FAILURE);
}
Node *temp = q->front;
int value = temp->data;
q->front = temp->next;
if (!q->front) q->rear = NULL; // Queue is now empty
free(temp);
q->size--;
return value;
}
void queue_destroy(Queue *q) {
while (q->front) {
Node *temp = q->front;
q->front = temp->next;
free(temp);
}
free(q);
}
int main(void) {
Queue *q = queue_create();
queue_enqueue(q, 42);
queue_enqueue(q, 73);
queue_enqueue(q, 99);
while (q->size > 0) {
printf("Dequeue: %d\n", queue_dequeue(q));
}
// Output: 42, 73, 99 (FIFO order)
queue_destroy(q);
return 0;
}Circular Queue
A circular queue is an array-based queue where the rear wraps around to the beginning when it reaches the end. We already used this technique above with the modulo operator. Here’s a clean, standalone version:
#include <stdio.h>
#include <stdbool.h>
#define CAPACITY 5
typedef struct {
int data[CAPACITY];
int front;
int rear;
int count;
} CircularQueue;
void cq_init(CircularQueue *cq) {
cq->front = 0;
cq->rear = -1;
cq->count = 0;
}
bool cq_enqueue(CircularQueue *cq, int value) {
if (cq->count == CAPACITY) return false;
cq->rear = (cq->rear + 1) % CAPACITY;
cq->data[cq->rear] = value;
cq->count++;
return true;
}
int cq_dequeue(CircularQueue *cq) {
if (cq->count == 0) return -1; // error sentinel
int value = cq->data[cq->front];
cq->front = (cq->front + 1) % CAPACITY;
cq->count--;
return value;
}
void cq_print(CircularQueue *cq) {
printf("Queue (%d items): ", cq->count);
int idx = cq->front;
for (int i = 0; i < cq->count; i++) {
printf("%d ", cq->data[idx]);
idx = (idx + 1) % CAPACITY;
}
printf("\n");
}
int main(void) {
CircularQueue cq;
cq_init(&cq);
cq_enqueue(&cq, 1);
cq_enqueue(&cq, 2);
cq_enqueue(&cq, 3);
cq_enqueue(&cq, 4);
cq_enqueue(&cq, 5);
cq_print(&cq); // 1 2 3 4 5
cq_dequeue(&cq);
cq_dequeue(&cq);
cq_enqueue(&cq, 6);
cq_enqueue(&cq, 7);
cq_print(&cq); // 3 4 5 6 7 (wrapped around!)
return 0;
}The beauty of a circular queue is that you never waste space. Once elements are dequeued from the front, those slots become available at the rear. This is exactly how operating systems implement keyboard input buffers and network packet queues.
Real Example: Balanced Parentheses Checker
This is a classic interview problem, and it’s a perfect use case for stacks. Given a string like {[()]}, determine if the parentheses are balanced. Every opening bracket must have a matching closing bracket in the correct order.
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX_LEN 1000
bool is_balanced(const char *str) {
char stack[MAX_LEN];
int top = -1;
for (int i = 0; str[i] != '\0'; i++) {
char c = str[i];
// Push opening brackets
if (c == '(' || c == '[' || c == '{') {
stack[++top] = c;
continue;
}
// For closing brackets, check match
if (c == ')' || c == ']' || c == '}') {
if (top == -1) return false; // Nothing to match
char open = stack[top--];
if (c == ')' && open != '(') return false;
if (c == ']' && open != '[') return false;
if (c == '}' && open != '{') return false;
}
}
return top == -1; // Stack should be empty
}
int main(void) {
const char *tests[] = {
"{[()]}", // true
"((()))", // true
"{[}]", // false (mismatched)
"(((", // false (unclosed)
"", // true (empty is balanced)
};
int n = sizeof(tests) / sizeof(tests[0]);
for (int i = 0; i < n; i++) {
printf("%-12s -> %s\n", tests[i],
is_balanced(tests[i]) ? "balanced" : "NOT balanced");
}
return 0;
}This pattern — using a stack to track matching pairs — extends to compilers (matching begin/end tokens), HTML parsers (matching tags), and expression evaluators. If you want to dive deeper into how C handles strings in these situations, see C Strings.
Real-World Applications
Stacks in the Real World
- Function call stack — Every time you call a function in C, the return address and local variables are pushed onto the call stack. When the function returns, they’re popped off. This is why C Recursion works — each recursive call gets its own stack frame.
- Undo/Redo — Text editors push each action onto a stack. Ctrl+Z pops the last action.
- Expression evaluation — Compilers use stacks to parse and evaluate mathematical expressions (infix to postfix conversion).
- Backtracking — Maze solvers and puzzle solvers push states onto a stack, then pop and try alternatives when stuck.
Queues in the Real World
- BFS (Breadth-First Search) — Graph traversal uses a queue to visit nodes level by level.
- Print spooler — Documents are printed in the order they were submitted (FIFO).
- Task scheduling — Operating systems use queues for CPU scheduling (round-robin, priority queues).
- Message queues — Systems like RabbitMQ and Kafka are essentially sophisticated queues for inter-process communication.
Common Mistakes
1. Stack Overflow on Array Stacks
Pushing beyond MAX_SIZE without checking causes buffer overflows. Always check stack_is_full() before pushing.
2. Forgetting to Free in Linked List Versions
Every malloc needs a matching free. If you pop from a linked list stack but forget to free the node, you have a memory leak. Study C Memory Bugs to learn how to catch these.
3. Off-by-One Errors in Circular Queues
Using front == rear to detect empty vs. full is ambiguous. Use a separate count variable or sacrifice one array slot. The count approach shown above is the cleanest.
4. Popping from an Empty Stack
Always check is_empty() before popping. Returning a sentinel value like -1 works for positive-only data, but in general, return a status code and use an output parameter.
5. Not Handling NULL in Linked List Queues
When dequeuing the last element, you must set both front and rear to NULL. Forgetting to reset rear leaves a dangling pointer.
Practice Exercises
- Reverse a string using a stack. Push each character, then pop them all into a new buffer.
- Implement a min-stack that supports
push,pop, andget_minin O(1) time. Hint: use two stacks. - Evaluate a postfix expression like
"3 4 + 2 *"using a stack. (Answer: 14) - Implement a queue using two stacks. One stack for enqueue, one for dequeue. This is a common interview question.
- Build a hot potato simulation using a circular queue. N people stand in a circle, counting off every K-th person who is eliminated. Who survives? (This is the Josephus problem.)
- Implement a double-ended queue (deque) that supports push/pop from both ends using a doubly-linked list.
Stacks and queues are the workhorses of algorithms. Master them, and you’ll have the foundation for trees, graphs, and every serious data structure that follows. Ready for more? Explore the full C Programming Roadmap to keep building.
