What is a stack?
A data structure is a way to store and organise data so it can be used well. A stack is a linear data structure where both adding and removing happen at one end only, called the top.
So the item added last is removed first. This rule is called LIFO (Last In, First Out).
Everyday stacks: plates in a pile, bangles on an arm, books kept one on another.
Operations on a stack: push, pop, peek, isEmpty
- PUSH: add an item at the top.
- POP: remove the top item and return it.
- PEEK (or TOP): read the top item without removing it.
- isEmpty: check if the stack has no items.
- size: number of items.
Overflow and underflow
Underflow: trying to pop (or peek) from an empty stack. Overflow: trying to push into a stack that is full (only when the stack has a fixed size). A Python list grows by itself, so we mostly check for underflow.
Implementing a stack with a Python list
Treat the end of the list as the top. Then both operations are fast.
def isEmpty(stk):
return len(stk) == 0
def push(stk, item):
stk.append(item)
def pop(stk):
if isEmpty(stk):
return 'Underflow'
return stk.pop()
def peek(stk):
if isEmpty(stk):
return 'Underflow'
return stk[-1]
def display(stk):
for i in range(len(stk) - 1, -1, -1):
print(stk[i]) # top first
s = []
push(s, 10); push(s, 20); push(s, 30)
print(pop(s)) # 30
print(peek(s)) # 20display prints from the top down, so we loop from the last index back to 0.
Board-style task: push records that match a condition
Many questions ask you to push only some items and then pop them all.
# push names of students with marks above 75, then pop all
D = {'Asha': 92, 'Ravi': 70, 'Zoya': 81, 'Om': 64}
st = []
def push_top(D):
for name in D:
if D[name] > 75:
st.append(name)
def pop_all():
while st:
print(st.pop(), end=' ')
print('\nStack empty')
push_top(D); pop_all() # Zoya AshaNotice: Asha was pushed first, so she comes out last.
Where are stacks used?
- Undo/redo in editors.
- Back button in browsers.
- Reversing a word or list: push each letter, then pop them all.
- Checking brackets are balanced in code or expressions.
- Function calls: Python keeps a call stack; the latest called function finishes first.
Try it: reverse your name with a stack
Take 5 coins or books. Write one letter of your name on each slip and put them in a pile, one by one. Now take them off the top one by one and read the letters. Your name comes out reversed! Then write the same in Python: push each letter with append, and pop until the list is empty. Use the free-play step in the 3D to check your guess before each pop.
Key formulas and definitions
- LIFO: last in, first out
- push → L.append(x) · pop → L.pop() · peek → L[-1] · isEmpty → len(L) == 0
- Underflow: pop/peek on an empty stack · Overflow: push on a full fixed-size stack
Worked examples
1. Start with an empty stack. Do push(5), push(8), pop(), push(3), push(9), pop(), pop(). What is left and what was popped?
[5] → [5,8] → pop 8 → [5] → [5,3] → [5,3,9] → pop 9 → pop 3 → [5]. Popped in order: 8, 9, 3. Left: [5].
2. Write a function that reverses a string using a stack.
def rev(s): st = [] for ch in s: st.append(ch) out = '' while st: out += st.pop() return out print(rev('CODE')) # EDOC
3. What does this print? st = [1, 2, 3]; st.append(4); st.pop(); print(st[-1], len(st))
After append: [1,2,3,4]. pop removes 4 → [1,2,3]. st[-1] = 3, len = 3. Output: 3 3.
4. A list NUM has numbers. Push the even ones onto a stack EVEN, then pop and print them all.
NUM = [12, 7, 4, 9, 20] EVEN = [] for n in NUM: if n % 2 == 0: EVEN.append(n) while EVEN: print(EVEN.pop(), end=' ') # 20 4 12 print('Stack Empty')
5. Why do we use append()/pop() at the end, and not insert(0, x)/pop(0) at the front?
Both work as a stack, but adding or removing at the end is fast. At the front Python must shift every other item one place, which is slow for big lists.
6. Write a function to check if brackets in '(a+b)*(c-d))' are balanced.
def balanced(e): st = [] for ch in e: if ch == '(': st.append(ch) elif ch == ')': if not st: return False # underflow: extra ')' st.pop() return len(st) == 0 print(balanced('(a+b)*(c-d))')) # False
Common mistakes
- Using pop(0), which removes the bottom item, not the top.
- Popping without checking if the stack is empty (IndexError: pop from empty list).
- Thinking peek removes the item; it only reads stk[-1].
- Printing the stack from index 0 and calling it top-first; the top is the last index.