When we start learning Data Structures and Algorithms, Stack is one of the first data structures we usually encounter.
At first, Stack looks very simple. It basically follows one rule:
Last In, First Out (LIFO)
But understanding why it works this way, how its operations work, and how to implement it efficiently is important because Stack appears everywhere in programming—from function calls and recursion to undo/redo operations, expression evaluation, and even browser history.
In this article, we will understand Stack from the basics and implement it mainly using Python, with a look at how the same idea can be implemented in C.
What is a Stack?
A Stack is a linear data structure in which elements are added and removed from the same end, called the top.
It follows the LIFO (Last In, First Out) principle.
Think about a stack of plates.
If you place plates one on top of another:
┌───────┐
│ Plate │ ← Top
├───────┤
│ Plate │
├───────┤
│ Plate │
└───────┘
The last plate you put on the stack is the first plate you can take out.
The same thing happens in a Stack data structure.
If we insert:
10 → 20 → 30
our Stack looks like:
When we remove an element, 30 is removed first.
This is why Stack is called LIFO.
Basic Operations of a Stack
A Stack mainly has three important operations:
1. Push
Push adds an element to the top of the Stack.
Push(10)
10
Then:
Push(20)
20 ← Top
10
Then:
Push(30)
30 ← Top
20
10
2. Pop
Pop removes the element from the top of the Stack.
If our Stack is:
30 ← Top
20
10
and we perform:
Pop()
30 is removed:
20 ← Top
10
The important thing to remember is that Pop usually returns the removed element as well.
3. Peek
Peek returns the element at the top without removing it.
For example:
30 ← Top
20
10
Calling:
Peek()
returns:
30
but the Stack remains:
30 ← Top
20
10
Stack Overflow and Stack Underflow
There are two common problems associated with Stack.
Stack Overflow
Stack Overflow happens when we try to insert an element into a Stack that has reached its maximum capacity.
For example, suppose a Stack can store only 3 elements:
30
20
10
Trying to perform:
Push(40)
would cause Stack Overflow in a fixed-size implementation.
In Python lists, this generally isn't something we need to manually handle because Python lists can dynamically grow. But i C, C++ languages the arrays need to be declared with a specific size
Stack Underflow
Stack Underflow happens when we try to remove an element from an empty Stack.
For example:
Stack = []
Calling:
Pop()
would result in an underflow condition.
This is why a good Stack implementation checks whether the Stack is empty before performing Pop or Peek.
Implementing Stack in Python
Python already provides a very convenient way to implement a Stack using a list.
The end of the list can be treated as the top of our Stack.
class Stack:
def __init__(self):
self.s = []
def push(self, value):
self.s.append(value)
def peek(self):
if len(self.s) == 0:
print("The stack is empty")
return
return self.s[-1]
def pop(self):
if len(self.s) == 0:
print("The stack is empty")
return
return self.s.pop()
Let's understand this step by step.
Creating the Stack
def __init__(self):
self.s = []
When we create a Stack object, an empty Python list is created.
For example:
stack = Stack()
Initially:
s = []
Push Operation
def push(self, value):
self.s.append(value)
We use append() to add the element to the end of the list.
For example:
stack.push(10)
stack.push(20)
stack.push(30)
The internal list becomes:
[10, 20, 30]
We treat 30 as the top.
30 ← Top
20
10
Peek Operation
return self.s[-1]
Python allows negative indexing.
-1 refers to the last element of a list.
So:
self.s[-1]
returns the top element without removing it.
because of:
pyhton indexing looks like;
positive index 0 1 2 3 4 5
10 20 30 40 50 60
negative index -6 -5 -4 -3 -2 -1
^
|
Top
Pop Operation
return self.s.pop()
Python's pop() removes and returns the last element.
For example:
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.pop())
Output:
30
The Stack now contains:
20 ← Top
10
Note: (method) def pop( index: SupportsIndex = -1, / ) -> Any
Remove and return item at index (default last).
Raises IndexError if list is empty or index is out of range.
The default of pop() will always points at index = -1
Why Use the End of the List?
You might wonder why we don't insert elements at index 0.
For example:
self.s.insert(0, value)
and remove them using:
self.s.pop(0)
This works logically, but it isn't efficient.
When we insert or remove an element from the beginning of a Python list, the other elements may need to be shifted.
Therefore, these operations take O(n) time.
Instead, we use:
append()
pop()
at the end of the list.
These operations are O(1) amortized.
So our Stack implementation becomes much more efficient.
Time Complexity of Stack Operations in Python
For the list-based implementation:
| Operation | Time Complexity |
|---|---|
| Push | O(1) amortized |
| Pop | O(1) |
| Peek | O(1) |
| Checking Empty | O(1) |
| Space | O(n) |
This is exactly what we generally want from a Stack.
A Complete Example
Here is a simple example using all three operations:
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Top:", stack.peek())
print("Removed:", stack.pop())
print("Removed:", stack.pop())
print("Top:", stack.peek())
Output:
Top: 30
Removed: 30
Removed: 20
Top: 10
Notice how the elements come out in reverse order:
Input:
10 → 20 → 30
Output:
30 → 20 → 10
That's LIFO in action.
Implementing Stack in C
Python makes Stack implementation very easy because its list can grow dynamically.
In C, we usually implement a Stack using an array and keep track of the top using an integer variable.
For example:
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
top++;
stack[top] = value;
}
int pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
int peek() {
if (top == -1) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
Here, top = -1 means the Stack is initially empty.
When we perform:
push(10);
top becomes 0:
Index: 0
Value: 10
After:
push(20);
push(30);
we have:
Index: 0 1 2
Value: 10 20 30
↑
top
When we call:
pop();
the element at top is returned and top is decreased.
This gives us the same LIFO behavior as our Python implementation.
Stack Using Linked List
A Stack can also be implemented using a Linked List.
In that implementation, the head of the linked list is generally treated as the top of the Stack.
For example:
Top
↓
30 → 20 → 10 → NULL
A push operation adds a node at the beginning, while pop removes the first node.
This is useful when we don't want a fixed maximum capacity like a traditional array-based Stack.
The important point is that the underlying implementation can change, but the Stack behavior remains the same.
Real-World Applications of Stack
Stacks aren't just theoretical DSA concepts. They are used in many practical situations.
1. Function Calls
Programming languages use a call stack to keep track of function calls.
For example:
main()
↓
functionA()
↓
functionB()
When functionB() finishes, it returns first because it was the most recently called function.
2. Undo/Redo
Text editors can maintain previous actions using stacks.
For example:
Type A
Type B
Type C
An Undo operation can remove C first.
3. Browser History
Browser navigation can be modeled using Stack-like behavior.
Going back generally means returning to the most recently visited page.
4. Recursion
Recursion heavily relies on the call stack.
For example:
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
Each recursive call is placed on the call stack until the base condition is reached.
5. Expression Evaluation
Stacks are commonly used for:
Parentheses matching
Infix to postfix conversion
Postfix expression evaluation
Syntax parsing
For example:
( A + B )
A Stack can help determine whether the parentheses are properly matched.
Common Mistakes While Implementing Stack
When implementing a Stack yourself, keep an eye on these mistakes:
1. Removing from the wrong end
If you add elements at the end, remove them from the end as well.
append()
pop()
should work together.
2. Forgetting the empty condition
Always consider what happens when someone calls pop() on an empty Stack.
3. Confusing Peek and Pop
peek() only looks at the top.
pop() removes the top.
4. Ignoring time complexity
Two implementations can behave the same way but have different performance.
For example:
insert(0, value)
pop(0)
works, but is less efficient than:
append(value)
pop()
Final Thoughts
Stack is one of the simplest data structures to understand, but it is also one of the most useful.
The main idea is easy:
The last element added is the first element removed.
Once you understand Push, Pop, and Peek, you have the foundation needed for many more advanced DSA problems.
For Python, a list provides an efficient and simple way to implement a Stack:
stack.append(value)
stack.pop()
stack[-1]
But the real goal while learning DSA isn't just remembering these methods. It's understanding why they work, their time complexity, and how the same Stack can be implemented using arrays or linked lists in languages such as C.
That understanding becomes much more valuable when we start solving actual Stack-based problems.
