A stack in C programming is a linear data structure where you add and remove elements from one end only, called the top. It follows the LIFO rule: Last In, First Out.
Think of a pile of plates:
- A new plate goes on top
- The next plate you use comes from the top
- Nobody pulls the bottom plate first
That one-door design is why stacks are simple, fast and hard to misuse.
Vocabulary you’ll see everywhere:
- Push: add an element to the top
- Pop: remove the top element (and usually hand it back to you)
- Peek / Top: read the top element without removing it
- isEmpty: check whether the stack has any elements
- isFull: check whether an array-based stack has run out of room
- Overflow: pushing onto a full stack
- Underflow: popping from an empty stack
push ↓ ↑ pop
+----------+
top →| 30 | ← last in, first out
+----------+
| 20 |
+----------+
| 10 | ← first in, last out
+----------+
What is the Stack Data Structure in C?
The stack data structure in C is an abstract data type (ADT). It is defined by what it does (push, pop, peek, LIFO order), not by how it’s stored. You choose the storage, usually an array or a linked list.
Key points:
- The C standard library has no stack. You write your own using struct, arrays, pointers and malloc()
- Access is restricted on purpose. You can’t reach into the middle, which prevents a whole class of bugs
- All core operations are O(1)
Stack Data Structure vs. Call Stack: Don’t Mix Them Up
The word “stack” means two related things in C.
| | Stack data structure | Call stack (stack memory) |
Who creates it | You, in your code | The compiler and CPU, automatically |
What it stores | Whatever data you choose | Return addresses, saved registers, local variables |
Size | Your choice (MAX_SIZE or heap) | Set by linker script, OS or RTOS task settings |
“Overflow” means | Pushing into a full stack; you can detect and handle it | Stack memory exhausted; usually a crash or silent corruption |
Same LIFO idea, different jobs. Most of this guide is about the first one. The embedded section covers the second.
How Stack Works in C
A stack in C works by tracking one number, the top index. Push moves top up and stores a value. Pop reads the value and moves top down.
The rules (with top = -1 meaning empty):
- Push: check not full → top++ → store at data[top]
- Pop: check not empty → read data[top] → top–
- Peek: check not empty → read data[top], leave top alone
- Empty when top == -1. Full when top == MAX_SIZE – 1
Trace on a stack with capacity 5:
Step | Operation | top after | Stack (bottom → top) | Result |
0 | start | -1 | (empty) | none |
1 | push(10) | 0 | 10 | OK |
2 | push(20) | 1 | 10, 20 | OK |
3 | push(30) | 2 | 10, 20, 30 | OK |
4 | pop() | 1 | 10, 20 | returns 30 |
5 | peek() | 1 | 10, 20 | returns 20 |
6 | push(40) | 2 | 10, 20, 40 | OK |
Two things worth noticing:
- Pop doesn’t erase. After step 4 the value 30 is still sitting in memory. top just moved. Only indexes 0 to top count as “in the stack”.
- Pick one top convention. Some books start with top = 0 (pointing at the next free slot). Both work, but mixing them is the #1 source of off-by-one bugs. This guide uses top = -1.
Types of Stacks in C
The C standard doesn’t define official “types” of stacks, but in practice you’ll build them in a few ways.
Type | How it’s built | Size | Best for |
Static (array-based) | Fixed array + top index | Fixed at compile time | Embedded and real-time code, predictable memory |
Dynamic (linked-list) | Nodes from malloc() + top pointer | Grows and shrinks per element | Unknown size when a heap is available |
Dynamic array | Array that realloc()s when full | Doubles as needed | Speed and cache-friendliness with unknown size |
Two stacks in one array | Two top indexes growing from opposite ends | Shared fixed array | Squeezing two stacks into limited RAM |
Min/Max stack | Main stack + helper stack tracking min or max | Depends on base | O(1) “get minimum” queries (interview favourite) |
Call (system) stack | Managed by compiler and CPU | Set by linker, OS or RTOS | Function calls; you don’t write this one |
Rule of thumb:
- Size known and small → array-based
- Size unpredictable and heap is safe to use → linked list or dynamic array
- Bare-metal or safety-critical firmware → static array, no malloc()
Implementation of Stack in C
Both versions below use nearly identical function names, so you can swap one for the other without rewriting the code that uses the stack.
Stack Implementation in C Using an Array
c
#include
#include
#define MAX_SIZE 5
typedef struct {
int data[MAX_SIZE];
int top; // index of the top element; -1 means empty
} Stack;
void stack_init(Stack *s) {
s->top = -1;
}
bool stack_is_empty(const Stack *s) {
return s->top == -1;
}
bool stack_is_full(const Stack *s) {
return s->top == MAX_SIZE - 1;
}
bool stack_push(Stack *s, int value) {
if (stack_is_full(s)) {
return false; // overflow
}
s->data[++s->top] = value;
return true;
}
bool stack_pop(Stack *s, int *value) {
if (stack_is_empty(s)) {
return false; // underflow
}
*value = s->data[s->top--];
return true;
}
bool stack_peek(const Stack *s, int *value) {
if (stack_is_empty(s)) {
return false;
}
*value = s->data[s->top];
return true;
}
void stack_display(const Stack *s) {
if (stack_is_empty(s)) {
printf("Stack is empty\n");
return;
}
printf("Stack (top -> bottom): ");
for (int i = s->top; i >= 0; i--) {
printf("%d ", s->data[i]);
}
printf("\n");
}
int main(void) {
Stack s;
int value;
stack_init(&s);
stack_push(&s, 10);
stack_push(&s, 20);
stack_push(&s, 30);
stack_display(&s);
if (stack_peek(&s, &value)) {
printf("Top element: %d\n", value);
}
if (stack_pop(&s, &value)) {
printf("Popped: %d\n", value);
}
stack_display(&s);
stack_push(&s, 40);
stack_display(&s);
return 0;
}
Output:
Stack (top -> bottom): 30 20 10
Top element: 30
Popped: 30
Stack (top -> bottom): 20 10
Stack (top -> bottom): 40 20 10
Why it’s written this way:
- The Stack struct bundles data and top, so there are no globals and you can create as many stacks as you like
- Functions return bool, so the caller knows when overflow or underflow happens
- pop and peek return data through a pointer, because -1 (or any value) could be real data and can’t double as an “empty” signal
- const on read-only functions tells the compiler, and your teammates, that they won’t modify the stack
Stack Implementation in C Using a Linked List
c
#include
#include
#include
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
size_t size;
} Stack;
void stack_init(Stack *s) {
s->top = NULL;
s->size = 0;
}
bool stack_is_empty(const Stack *s) {
return s->top == NULL;
}
bool stack_push(Stack *s, int value) {
Node *node = malloc(sizeof *node);
if (node == NULL) {
return false; // heap exhausted
}
node->data = value;
node->next = s->top; // new node points to the old top
s->top = node; // new node becomes the top
s->size++;
return true;
}
bool stack_pop(Stack *s, int *value) {
if (stack_is_empty(s)) {
return false; // underflow
}
Node *temp = s->top;
*value = temp->data;
s->top = temp->next;
free(temp); // give the node back to the heap
s->size--;
return true;
}
bool stack_peek(const Stack *s, int *value) {
if (stack_is_empty(s)) {
return false;
}
*value = s->top->data;
return true;
}
void stack_destroy(Stack *s) {
int discard;
while (stack_pop(s, &discard)) {
// keep popping until every node is freed
}
}
int main(void) {
Stack s;
int value;
stack_init(&s);
stack_push(&s, 10);
stack_push(&s, 20);
stack_push(&s, 30);
printf("Size after 3 pushes: %zu\n", s.size);
if (stack_pop(&s, &value)) {
printf("Popped: %d\n", value);
}
if (stack_peek(&s, &value)) {
printf("New top: %d\n", value);
}
stack_destroy(&s); // frees whatever is left
return 0;
}
Output:
Size after 3 pushes: 3
Popped: 30
New top: 20
What to remember:
- Push = insert at the head. The new node points at the old top, then becomes the top
- Pop = remove the head. Save the node, move top forward, then free() it
- There’s no isFull. The limit is the heap, so check malloc() for NULL
- Always call stack_destroy(). Every leftover node is a memory leak
Dynamic Array Stack (Grows with realloc)
c
// needs and
typedef struct {
int *data;
int top;
int capacity;
} DynStack;
bool dynstack_init(DynStack *s, int initial_capacity) {
s->data = malloc(initial_capacity * sizeof *s->data);
if (s->data == NULL) {
return false;
}
s->top = -1;
s->capacity = initial_capacity;
return true;
}
bool dynstack_push(DynStack *s, int value) {
if (s->top == s->capacity - 1) { // full, so grow
int new_capacity = s->capacity * 2;
int *tmp = realloc(s->data, new_capacity * sizeof *tmp);
if (tmp == NULL) {
return false; // old buffer is still valid
}
s->data = tmp;
s->capacity = new_capacity;
}
s->data[++s->top] = value;
return true;
}
- Doubling the capacity keeps push amortized O(1). The single push that triggers a resize costs O(n)
- Never write s->data = realloc(s->data, …). If realloc fails you lose the original pointer and leak the buffer. Use a temporary pointer, as above
Array vs. Linked List Stack: Which Should You Pick?
Factor | Array-based | Linked list |
Memory use | Fixed block, may waste space | Exactly what you use + one pointer per node |
Size limit | Fixed (MAX_SIZE) | Limited only by heap |
Push/pop speed | O(1), very fast, cache-friendly | O(1), but malloc/free on every call |
Fragmentation risk | None | Possible over time |
Overflow check | stack_is_full() | malloc() returning NULL |
Best fit | Microcontrollers, real-time systems | PC-side programs with unpredictable sizes |
How to Use Stack in C Programming
To use a stack in C, initialise it, push your data, guard every push and pop against overflow and underflow, and free the memory if it’s linked-list-based.
- Pick the data type. int, char or a struct. Change the type of data[] to match
- Pick the implementation using the comparison table above
- Initialise before use with stack_init(). An uninitialised top is garbage
- Guard every push and pop. Always check the return value
- Peek before you decide. Use stack_peek() when you need to look without removing
- Clean up. Destroy linked-list stacks when finished
Here’s the usage pattern with the array stack from earlier:
c
int main(void) {
Stack s;
int value;
stack_init(&s); // 1. always initialise first
for (int i = 1; i <= 7; i++) { // 2. guard every push
if (!stack_push(&s, i * 10)) {
printf("Overflow! Could not push %d\n", i * 10);
}
}
while (stack_pop(&s, &value)) { // 3. pop until empty
printf("Popped: %d\n", value);
}
if (!stack_pop(&s, &value)) { // 4. underflow handled, not ignored
printf("Underflow! Stack is empty\n");
}
return 0;
}Output:
Overflow! Could not push 60
Overflow! Could not push 70
Popped: 50
Popped: 40
Popped: 30
Popped: 20
Popped: 10
Underflow! Stack is empty
Reach for a stack when:
- Things must be undone in reverse order (undo, backtracking)
- You have nested or paired structures (brackets, tags, function calls)
- You need to reverse a sequence
- You want to save state now and come back to it later
Common Stack Functions in C
A stack in C usually exposes six to eight small functions, each running in constant time (except display and destroy).
Function | What it does | Time | Typical signature |
stack_init() | Sets top = -1 (or NULL) | O(1) | void stack_init(Stack *s) |
stack_push() | Adds an element on top | O(1) | bool stack_push(Stack *s, int value) |
stack_pop() | Removes and returns the top | O(1) | bool stack_pop(Stack *s, int *value) |
stack_peek() | Reads the top without removing | O(1) | bool stack_peek(const Stack *s, int *value) |
stack_is_empty() | Guards against underflow | O(1) | bool stack_is_empty(const Stack *s) |
stack_is_full() | Guards against overflow (array) | O(1) | bool stack_is_full(const Stack *s) |
stack_size() | Number of elements (top + 1, or a counter) | O(1) | int stack_size(const Stack *s) |
stack_display() | Prints top → bottom | O(n) | void stack_display(const Stack *s) |
stack_destroy() | Frees all nodes (linked list) | O(n) | void stack_destroy(Stack *s) |
C++ programmers get push(), pop(), top(), empty() and size() from std::stack. In C you write them yourself, which is exactly why you understand them afterwards.
Stack Overflow and Underflow in C
Stack overflow means pushing onto a full stack. Underflow means popping or peeking at an empty one. C won’t stop you from doing either, so you have to.
- Overflow (array): without an isFull check you write past the array and corrupt neighbouring memory
- Overflow (linked list): malloc() returns NULL when the heap runs out, so check it
- Underflow: without an isEmpty check you read garbage or index -1
Ways to handle it:
- Return status codes, as the code above does. Simple and works everywhere
- Use assert() in debug builds for “this must never happen” conditions
- In firmware, set an error flag or call a fault handler. Never fail silently
- Size from worst-case analysis, not gut feeling
Applications of Stack in Programming
Stacks show up wherever the most recent item must be handled first, or wherever you need to unwind steps in reverse order.
Inside compilers and runtimes
- Function calls and recursion: the call stack tracks where to return
- Expression evaluation: postfix (RPN) expressions are evaluated with a stack
- Infix to postfix conversion: operators wait on a stack until their turn
- Syntax parsing: compilers match brackets and nested blocks
Everyday software
- Undo/redo in editors
- Back/forward navigation in browsers
- Bracket matching in IDEs
Algorithms
- Depth-first search (DFS)
- Backtracking: maze solving, N-Queens, Sudoku
- Next greater element and other monotonic-stack problems
Embedded systems
- Interrupt handling: CPU context is saved on the stack
- RTOS tasks: every task has its own stack
- Command parsers and menus: push a menu to enter, pop to go back
Example: Balanced Brackets Checker
This is the classic use of a stack in C, and a favourite in technical interviews.
c
#include
#include
#define MAX 100
bool is_balanced(const char *expr) {
char stack[MAX];
int top = -1;
for (size_t i = 0; expr[i] != '\0'; i++) {
char ch = expr[i];
if (ch == '(' || ch == '{' || ch == '[') {
if (top == MAX - 1) return false; // nested deeper than our stack
stack[++top] = ch;
} else if (ch == ')' || ch == '}' || ch == ']') {
if (top == -1) return false; // closing bracket with nothing open
char open = stack[top--];
if ((ch == ')' && open != '(') ||
(ch == '}' && open != '{') ||
(ch == ']' && open != '[')) {
return false; // wrong pair
}
}
}
return top == -1; // leftovers mean unbalanced
}
int main(void) {
printf("%s\n", is_balanced("{[a + b] * (c - d)}") ? "Balanced" : "Not balanced");
printf("%s\n", is_balanced("{[(a + b])}") ? "Balanced" : "Not balanced");
printf("%s\n", is_balanced("((a + b)") ? "Balanced" : "Not balanced");
return 0;
}
Output:
Balanced
Not balanced
Not balanced
How it works:
- Opening bracket → push
- Closing bracket → pop and check that the pair matches
- End of string → stack must be empty. The third test fails here because one ( never closed
Example: Evaluating a Postfix Expression
Evaluate 5 3 + 8 *, which is (5 + 3) × 8:
Token | Action | Stack after (bottom → top) |
5 | push | 5 |
3 | push | 5, 3 |
+ | pop 3 and 5, push 5+3 | 8 |
8 | push | 8, 8 |
* | pop 8 and 8, push 8×8 | 64 |
Result: 64. No brackets and no precedence rules needed, because the stack remembers the order.
Stack in Embedded Systems: What Most Tutorials Skip
In embedded systems, “the stack” is also a fixed slice of RAM that your microcontroller uses for function calls and interrupts. Running out of it is one of the hardest bugs to track down.
How the hardware stack behaves:
- It grows downward. On ARM Cortex-M, a push moves the stack pointer (SP) to a lower address
- Function calls build stack frames holding the return address, saved registers and local variables
- Interrupts use it too. On Cortex-M, hardware automatically pushes eight registers (R0–R3, R12, LR, PC, xPSR) before your ISR runs
- Each RTOS task gets its own stack. Undersize one and you get random, hard-to-reproduce crashes
Rules that save you in firmware:
- Avoid recursion. Depth is unpredictable, and standards like MISRA C prohibit it
- Keep big buffers out of local variables. A char buf[1024] inside a function eats stack fast. Make it static or global, and mind reentrancy
- Prefer a fixed-size array stack for your own data. No heap fragmentation, no malloc() failure at 3 AM, and memory use you can calculate up front
- Measure, don’t guess. Fill the stack with a known pattern at startup and check how much is untouched later (stack painting), or use uxTaskGetStackHighWaterMark() in FreeRTOS
- Protect shared stacks. If an ISR and the main loop both push and pop the same stack, wrap those operations in a critical section. Updating top and writing the data isn’t atomic
Common Mistakes to Avoid
- Skipping overflow/underflow checks. Return a status from every push and pop, and check it
- Mixing top = -1 and top = 0. Pick one, write it in a comment
- Using a sentinel like -1 to mean “empty”. It might be valid data. Return a bool and pass the value through a pointer
- Forgetting to free a linked-list stack. Call stack_destroy() before the program ends
- Overwriting a pointer with realloc()‘s result directly. Use a temporary pointer
- Returning the address of a local array. It lives on the call stack and disappears when the function returns
Catch these early: compile test builds with -fsanitize=address,undefined. It flags out-of-bounds writes, leaks and undefined behaviour the moment they happen.
Stack vs Queue
| | Stack | Queue |
Order | LIFO (last in, first out) | FIFO (first in, first out) |
Insert | Push at top | Enqueue at rear |
Remove | Pop from top | Dequeue from front |
Pointers needed | One (top) | Two (front, rear) |
Real-life example | Pile of plates, undo history | Ticket line, print queue |
Typical use | Recursion, parsing, backtracking | Scheduling, buffering, BFS |
In firmware the two often appear side by side: the function-call chain is a stack, while a UART receive buffer is a queue (usually a ring buffer).
Practice Problems
Try these in order. Each one reuses the code above:
- Reverse a string using a stack
- Convert a decimal number to binary using a stack
- Check whether a string is a palindrome
- Evaluate a postfix expression
- Convert an infix expression to postfix
- Implement two stacks in a single array
- Design a min-stack that returns the minimum in O(1)
- Implement a queue using two stacks
- Embedded twist: build a fixed-memory command-history stack for a UART command-line interface
Key Takeaways
- A stack is LIFO, and all action happens at the top
- C has no built-in stack. Build one with an array (fixed, fast, predictable) or a linked list (flexible, uses the heap)
- Push, pop and peek are O(1)
- Always check for overflow and underflow, and return a status instead of guessing
- Linked-list stacks need free(). Dynamic arrays need the safe realloc pattern
- The stack data structure and the call stack are different things
- In firmware: fixed-size stacks, no recursion, and measure real stack usage
Conclusion
Stack in C programming is a small idea with a huge reach. Once push, pop and top feel natural, you’ll spot stacks everywhere: bracket checkers, undo systems, DFS, and the call stack running your own firmware.
Build the array version first, then the linked list, and finish with two practice problems. That is the fastest way to make it stick
