C course menu
Stacks and Queues in C: Array and Linked Implementations
Implement stacks and queues in C: a stack with an array (push, pop, peek), using a stack to check balanced brackets, a circular-buffer queue with an array, and a linked-list queue, with notes on overflow, underflow and complexity.
On this page
Stacks and queues are collections that restrict where you add and remove items:
- A stack is last in, first out (LIFO), like a pile of plates: push onto the top, pop from the top.
- A queue is first in, first out (FIFO), like a ticket line: enqueue at the back, dequeue from the front.
Both are building blocks for algorithms and appear constantly in interviews.
A stack using an array#
#include <stdio.h>
#define STACK_MAX 100
typedef struct {
int items[STACK_MAX];
int top; /* number of items */
} Stack;
void stack_init(Stack *s) { s->top = 0; }
int stack_empty(const Stack *s) { return s->top == 0; }
int push(Stack *s, int value) {
if (s->top == STACK_MAX) return 0; /* overflow */
s->items[s->top++] = value;
return 1;
}
int pop(Stack *s, int *out) {
if (stack_empty(s)) return 0; /* underflow */
*out = s->items[--s->top];
return 1;
}
int main(void) {
Stack s;
stack_init(&s);
for (int i = 1; i <= 4; i++) push(&s, i * 10);
int v;
while (pop(&s, &v)) printf("%d ", v);
printf("\n");
printf("pop on empty: %d\n", pop(&s, &v));
return 0;
}40 30 20 10
pop on empty: 0Each operation is O(1). Returning a success flag and passing the value out through a pointer handles underflow (popping an empty stack) and overflow (pushing onto a full one) safely.
Using a stack: balanced brackets#
A classic use: check that every (, [ and { is closed in the right order. Push each opening bracket; on a closing bracket, pop and check that it matches:
#include <stdio.h>
int balanced(const char *s) {
char stack[256];
int top = 0;
for (; *s != '\0'; s++) {
char c = *s;
if (c == '(' || c == '[' || c == '{') {
if (top == (int)sizeof stack) return 0;
stack[top++] = c;
} else if (c == ')' || c == ']' || c == '}') {
if (top == 0) return 0;
char open = stack[--top];
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{')) return 0;
}
}
return top == 0;
}
int main(void) {
const char *tests[] = {"a[i] = (b + c) * {d}", "(]", "((x)", "f(g[h{}])"};
for (int i = 0; i < 4; i++) printf("%-22s %s\n", tests[i], balanced(tests[i]) ? "balanced" : "not balanced");
return 0;
}a[i] = (b + c) * {d} balanced
(] not balanced
((x) not balanced
f(g[h{}]) balancedA queue using a circular array#
A simple array queue would waste the space at the front as items leave. A circular buffer wraps the indexes round with %, so the space is reused:
#include <stdio.h>
#define QCAP 4
typedef struct {
int items[QCAP];
int head; /* index of the front item */
int count;
} Queue;
int enqueue(Queue *q, int value) {
if (q->count == QCAP) return 0;
q->items[(q->head + q->count) % QCAP] = value;
q->count++;
return 1;
}
int dequeue(Queue *q, int *out) {
if (q->count == 0) return 0;
*out = q->items[q->head];
q->head = (q->head + 1) % QCAP;
q->count--;
return 1;
}
int main(void) {
Queue q = {0};
int v;
for (int i = 1; i <= 5; i++) printf("enqueue %d: %s\n", i, enqueue(&q, i) ? "ok" : "full");
dequeue(&q, &v); printf("dequeued %d\n", v);
dequeue(&q, &v); printf("dequeued %d\n", v);
enqueue(&q, 6);
enqueue(&q, 7); /* these wrap round to the start */
while (dequeue(&q, &v)) printf("%d ", v);
printf("\n");
return 0;
}enqueue 1: ok
enqueue 2: ok
enqueue 3: ok
enqueue 4: ok
enqueue 5: full
dequeued 1
dequeued 2
3 4 6 7 Circular buffers are widely used in embedded systems and device drivers, for example to hold bytes arriving from a serial port.
A queue using a linked list#
A linked list with head and tail pointers gives an unbounded queue: enqueue at the tail, dequeue at the head, both O(1):
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode {
int value;
struct QNode *next;
} QNode;
typedef struct {
QNode *head, *tail;
} LinkedQueue;
int lq_enqueue(LinkedQueue *q, int value) {
QNode *n = malloc(sizeof *n);
if (n == NULL) return 0;
n->value = value;
n->next = NULL;
if (q->tail) q->tail->next = n;
else q->head = n;
q->tail = n;
return 1;
}
int lq_dequeue(LinkedQueue *q, int *out) {
QNode *n = q->head;
if (n == NULL) return 0;
*out = n->value;
q->head = n->next;
if (q->head == NULL) q->tail = NULL;
free(n);
return 1;
}
int main(void) {
LinkedQueue q = {NULL, NULL};
for (int i = 100; i <= 500; i += 100) lq_enqueue(&q, i);
int v;
while (lq_dequeue(&q, &v)) printf("%d ", v);
printf("\n");
return 0;
}100 200 300 400 500 When the last node leaves, tail must also be reset to NULL.
Practice#
Practice exercise
Evaluate a postfix (reverse Polish) expression of single-digit numbers with an int stack: for "52+3*" push 5 and 2, apply + to get 7, push 3, apply * to get 21. Support +, - and *, and test "52+3*" and "934*-".
Show solution
#include <stdio.h>
#include <ctype.h>
int eval_postfix(const char *expr) {
int stack[64];
int top = 0;
for (; *expr != '\0'; expr++) {
unsigned char c = (unsigned char)*expr;
if (isdigit(c)) {
stack[top++] = c - '0';
} else {
int b = stack[--top];
int a = stack[--top];
if (c == '+') stack[top++] = a + b;
else if (c == '-') stack[top++] = a - b;
else if (c == '*') stack[top++] = a * b;
}
}
return stack[0];
}
int main(void) {
printf("%d\n", eval_postfix("52+3*"));
printf("%d\n", eval_postfix("934*-"));
return 0;
}21
-3This solution assumes the expression is valid; production code would check for underflow before every pop.
Key takeaway#
Finished this lesson?