A stack is one of the simplest and most useful data structures. Think of a pile of plates: you add to the top and take from the top. This lesson explains the stack’s rules and shows how to implement it.
LIFO
A stack follows LIFO: Last In, First Out. The most recently added item is the first removed. Only the top is accessible.
Operations
- push(item): add an item to the top.
- pop(): remove and return the top item.
- peek(): return the top item without removing it.
- isEmpty(): true if the stack has no items.
- isFull(): true if a fixed-size stack has no room (array-based).
Example sequence:
push(5) // [5]
push(8) // [5, 8]
push(2) // [5, 8, 2] top is 2
pop() // returns 2, stack is [5, 8]
peek() // returns 8, stack unchanged
Trying to pop from an empty stack causes stack underflow. Pushing onto a full stack causes stack overflow.
Array implementation
Keep an array and a variable top that stores the index of the top item (start at -1 when empty).
STACK = new array[10]
top = -1
PROCEDURE push(item)
if top = 9 then
output "Stack overflow"
else
top = top + 1
STACK[top] = item
end if
END PROCEDURE
FUNCTION pop()
if top = -1 then
output "Stack underflow"
else
item = STACK[top]
top = top - 1
return item
end if
END FUNCTION
FUNCTION peek()
return STACK[top]
END FUNCTION
Note that pop only moves top down; the old value still sits in the array but is ignored and will be overwritten.
Linked-list implementation
Use a linked list where the head is the top. Push inserts at the head and pop removes the head. Both are O(1), and the stack can grow without a fixed limit.
Complexity
All the main operations (push, pop, peek, isEmpty) are O(1). That is a major reason stacks are popular.
Everyday analogy
Pressing the back button in a browser steps back through pages in reverse order of visiting, which is stack behaviour. Undo in a text editor works the same way.
Check your understanding
What does LIFO stand for?
- Last In, First Out
- Last In, First Over
- Linear In, Fixed Out
- Least In, First Out
Answer: Last In, First Out. The newest item leaves first.
Starting with an empty stack, after push(1), push(2), push(3), pop(), what does peek() return?
- 1
- 2
- 3
- Nothing
Answer: 2. The 3 was removed, leaving 2 on top.
What is stack underflow?
- Popping from an empty stack
- Pushing onto a full stack
- Peeking twice
- Deleting the array
Answer: Popping from an empty stack. There is nothing to remove.
What is the complexity of push on an array-based stack?
- O(1)
- O(n)
- O(log n)
- O(n squared)
Answer: O(1). It only increments top and stores one value.
