Source: COP 3502c Lecture Notes, Computer Science I (UCF)
Tags: stack, stacks in C, LIFO, last in first out, push, pop, peek, array stack, linked list stack, COP 3502c, data structures, abstract data type, ADT
Difficulty: Beginner to Intermediate
Prerequisites: Basic C programming, pointers, dynamic memory allocation (malloc/free), structs, linked lists.
Stacks are one of the foundational abstract data types in computer science, and they appear everywhere: function call management, undo/redo systems, expression parsing, backtracking algorithms. In COP 3502c, stacks sit alongside queues as your introduction to constrained-access data structures, where the rules about how you add and remove elements define the structure's behaviour. You should already be comfortable with arrays, pointers, and basic linked list operations before tackling this material.
A stack is a linear data structure that enforces last-in, first-out (LIFO) access. You add (push) and remove (pop) elements from the same end, called the "top." In C, stacks can be built on either a fixed-size array or a dynamically allocated linked list, each with different trade-offs around memory and flexibility.
Stack
A linear data structure where elements are added and removed from the same end. Think of it as a spring-loaded plate dispenser in a cafeteria: the last plate placed on top is the first one taken off.
LIFO (Last-In, First-Out)
The access pattern that defines a stack. The most recently added element is always the first to be removed. In simple terms, "last on, first off."
Push
The operation that adds a new element to the top of the stack. If the stack is full (in an array implementation), the push fails.
Pop
The operation that removes and returns the element at the top of the stack. If the stack is empty, the pop fails.
Peek (Top)
Returns the value of the top element without removing it. Useful when you need to inspect what's next without altering the stack's contents. In simple terms, you're "looking" at the top without touching it.
Overflow
Occurs when you attempt to push onto a stack that has reached its maximum capacity (array-based). Think of it as trying to stack one more plate when the dispenser is completely full.
Underflow
Occurs when you attempt to pop from an empty stack. There is nothing to remove.
top (index / pointer)
In an array-based stack, top is the integer index of the current top element. In a linked-list stack, head serves the same role as a pointer to the top node.
The simplest way to implement a stack in C is with a fixed-size array and an integer index (top) that tracks the position of the current top element.
top is initialised to -1, which signals an empty stack
On push, top is incremented first, then the value is stored at stack[top]
On pop, the value at stack[top] is saved, then top is decremented
is_empty() returns true when top == -1
is_full() returns true when top == MAX_SIZE - 1
All four core operations (push, pop, peek, is_empty) run in O(1) time.
Key code pattern:
#define MAX_SIZE 10
int stack[MAX_SIZE];
int top = -1;
void push(int value) {
if (top == MAX_SIZE - 1) {
printf("Error: Stack is full\n");
return;
}
top++;
stack[top] = value;
}
int pop() {
if (top == -1) {
printf("Error: Stack is empty\n");
return -1;
}
int value = stack[top];
top--;
return value;
}
Limitations of the array approach:
Fixed maximum size decided at compile time
Unused array slots waste memory if the stack rarely fills up
No way to grow the stack beyond MAX_SIZE without reallocating
A linked list removes the fixed-size constraint. Each element is a dynamically allocated node, and the head pointer always points to the top of the stack.
On push, a new node is created with malloc, its next pointer is set to the current head, and head is updated to the new node
On pop, the value in the head node is saved, head advances to head->next, and the old node is freed
There is no fixed capacity; the stack grows and shrinks with each push and pop
Memory is allocated per element, so there is a small overhead per node (the next pointer)
Key code pattern:
typedef struct node {
int value;
struct node *next;
} node;
node *head = NULL;
void push(int value) {
node *new_node = (node*) malloc(sizeof(node));
new_node->value = value;
new_node->next = head;
head = new_node;
}
int pop() {
if (head == NULL) {
printf("Error: Stack is empty\n");
return -1;
}
int value = head->value;
node *temp = head;
head = head->next;
free(temp);
return value;
}
Key detail: every pop must free the removed node. Forgetting this causes a memory leak. Every malloc needs a matching free.
Use an array-based stack when you know the maximum size in advance and want simpler, cache-friendly code
Use a linked-list stack when the number of elements is unpredictable or when memory efficiency per unused slot matters more than per-node overhead
Operation | Array-Based | Linked-List |
|---|---|---|
Push | O(1) | O(1) |
Pop | O(1) | O(1) |
Peek | O(1) | O(1) |
is_empty | O(1) | O(1) |
Space | O(n) fixed | O(n) dynamic |
Function calls in any running C programme are managed by the call stack: each function call pushes a frame, each return pops one. This is why infinite recursion causes a "stack overflow." Stacks also power the undo feature in text editors, where each action is pushed and each Ctrl+Z pops the most recent one.
"A stack can only be implemented with an array." Both arrays and linked lists work. The choice is about trade-offs, not necessity.
"Pop deletes the element." Pop removes and returns the element. If you need the value, capture the return. If you just want to discard it, you can ignore the return, but the operation still returns it.
"Peek modifies the stack." Peek is read-only. The stack is unchanged after a peek call.
"An array-based stack with top = 0 is empty." With the standard initialisation (top = -1), top = 0 means there is one element. Empty is top == -1. Getting this off by one wrong is a classic exam error.
⚠️ You will almost certainly be asked to trace through a sequence of push/pop operations and state the final contents of the stack or the output printed. Practise these by hand.
⚠️ Know the difference between top = -1 (empty) and top = 0 (one element). Off-by-one errors here are heavily tested.
⚠️ Be prepared to write or identify overflow and underflow checks in code. Exam questions often ask what happens when you push onto a full stack or pop from an empty one.
⚠️ Linked-list implementations: expect questions about memory leaks. If free(temp) is missing from pop, that is a bug worth pointing out.
1. True or False: In a LIFO structure, the first element added is the first one removed.
A: False. LIFO means the last element added is the first removed.
2. Fill in the blank: In an array-based stack initialised with top = -1, the stack is empty when top == ______.
A: -1
3. True or False: peek() removes the top element and returns it.
A: False. peek() returns the top element without removing it.
4. Fill in the blank: In a linked-list stack, every call to malloc during push should have a corresponding call to ______ during pop.
A: free
5. True or False: An array-based stack can grow beyond MAX_SIZE without reallocation.
A: False.
Q: You push the values 10, 20, 30, 40 onto a stack, then pop twice. What value does peek() return?
A: 20. After pushing 10, 20, 30, 40, the top is 40. Two pops remove 40 then 30. Peek returns the current top, which is 20.
Q: What is the output of the following code?
push(5); push(10); push(15);
printf("%d ", pop());
printf("%d ", peek());
printf("%d ", pop());
A: 15 10 10. The first pop returns 15 (top). Peek returns 10 without removing it. The second pop then returns 10.
Q: In the array-based implementation, what happens if you call push() when top == MAX_SIZE - 1?
A: The function prints "Error: Stack is full" and returns without modifying the stack. This is the overflow condition.
Q: Why does the linked-list pop() function save the head pointer in a temporary variable before advancing head?
A: Because head moves to head->next before the old node is freed. Without the temp pointer, you would lose the reference to the node that needs to be freed, causing a memory leak.
Q: Compare the memory trade-offs of array-based vs. linked-list stacks.
A: An array-based stack allocates a fixed block of memory upfront, which wastes space if the stack is rarely full but avoids per-element allocation overhead. A linked-list stack allocates memory per node (value + pointer), so it uses only what it needs but has higher per-element overhead due to the extra pointer field and the cost of individual malloc/free calls.
This material connects directly to queues (the next major data structure in COP 3502c), which use the same building blocks (arrays, linked lists) but enforce FIFO instead of LIFO ordering. Stacks also underpin recursion, which you will encounter throughout the course, since every recursive call pushes a frame onto the programme's call stack. Later, when you study tree traversals and graph algorithms, stacks power depth-first search (DFS), the counterpart to the queue-driven breadth-first search (BFS).
stack, LIFO, last in first out, push, pop, peek, top, overflow, underflow, array stack, linked list stack, stack in C, stack data structure, abstract data type, ADT, call stack, depth-first search, DFS, stack operations, COP 3502c, computer science 1, UCF, stack implementation C programming