Back to: Python Data Structure and Algorithims
Introduction
When learning data structures, one of the simplest yet most powerful concepts you’ll encounter is the Stack.
A stack follows a simple rule: Last In, First Out (LIFO).
This means that the last item you add to the stack will be the first one to come out — just like a can of tennis balls.
🎾 The Tennis Ball Analogy
Imagine you have a can of tennis balls.
- You first put one ball in — that’s your first item.
- Then you put the second ball — now it sits on top of the first.
- Finally, you add a third ball — this one is now at the very top.
If you want to take a ball out, which one can you access first?
👉 Only the topmost ball (the last one you added).
You cannot reach the first or second ball until you remove the ones above it.
That’s LIFO: Last In, First Out.
💻 Real-Life Example: Web Browser History
Let’s say you are browsing the internet:
- You visit Facebook.
- Then go to YouTube.
- Then Instagram.
- Finally, open your Email.
Now your browsing history stack looks like this:
Top → Email
Instagram
YouTube
Bottom → Facebook
When you press the Back button:
- First click → goes back to Instagram (removes Email)
- Second click → goes back to YouTube
- Third click → goes back to Facebook
Each “back” operation is like popping the last item from the stack.
🧩 Stack Operations
A Stack mainly supports two operations:
- Push: Add an item to the top of the stack.
Example: adding a new tennis ball to the can. - Pop: Remove the item from the top of the stack.
Example: taking the topmost ball out of the can.
🧠 Implementing a Stack Using Python List
Python lists can behave like stacks if we only use one end for both adding and removing.
stack = []
# Push elements onto the stack
stack.append('Facebook')
stack.append('YouTube')
stack.append('Instagram')
print("Current Stack:", stack)
# Pop element from the stack
top = stack.pop()
print("Popped:", top)
print("Stack after pop:", stack)
Output:
Current Stack: ['Facebook', 'YouTube', 'Instagram']
Popped: Instagram
Stack after pop: ['Facebook', 'YouTube']
💡 Note: Always use the end of the list for adding and removing to maintain efficiency (O(1) time complexity).
If you try to add or remove from the beginning of the list, it becomes O(n) because all other items need to be re-indexed.
🔗 Stack Using Linked List
You can also implement a stack using a linked list.
In this method, each node points to the next one, and you only perform operations at the head (top) of the list.
Here’s a conceptual diagram:
Top → [Node3] → [Node2] → [Node1] → None
We can define:
- push() → add node at the head (O(1))
- pop() → remove node from the head (O(1))
If you try to add or remove from the tail, it becomes O(n), which is inefficient.
Example (Conceptual Code)
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.top = None
self.height = 0
def push(self, value):
new_node = Node(value)
if self.height == 0:
self.top = new_node
else:
new_node.next = self.top
self.top = new_node
self.height += 1
def pop(self):
if self.height == 0:
return None
temp = self.top
self.top = self.top.next
self.height -= 1
return temp.value
# Example Usage
stack = Stack()
stack.push('Facebook')
stack.push('YouTube')
stack.push('Instagram')
print(stack.pop()) # Instagram
print(stack.pop()) # YouTube
🧾 Summary
| Operation | Description | Time Complexity |
|---|---|---|
| Push | Add item to top | O(1) |
| Pop | Remove item from top | O(1) |
| Peek | Look at top item without removing | O(1) |
| isEmpty | Check if stack is empty | O(1) |
💡 Key Takeaways
- A Stack follows the LIFO principle.
- Use lists or linked lists to implement stacks.
- Only interact with one end — the top.
- Real-world examples:
- Browser back button
- Undo/Redo in text editors
- Function call stacks in programming
🌟 Final Thoughts
Stacks might look simple, but they form the foundation for recursion, parsing, memory management, and expression evaluation in programming.