🧱 Unit 1 – Data Structures & Algorithms · Lesson 09
Stack: PUSH, POP using a List
What is a stack?
A stack is a linear data structure where items are added and removed from one end only, called the top. The rule is LIFO – Last In, First Out.
Stacks in real life
🍽️
PlatesYou take the top plate first.↩️
UndoCtrl+Z undoes the latest change first.🌐
Back buttonThe browser returns to the last page visited.📚
Books pileThe last book kept is picked first.Stack operations
| Operation | Meaning | Python |
|---|---|---|
| PUSH | Add item on top | stk.append(x) |
| POP | Remove and return top item | stk.pop() |
| PEEK / TOP | See top item without removing | stk[-1] |
| isEmpty | Is the stack empty? | len(stk) == 0 |
- 1push(10) → [10]
- 2push(20) → [10, 20]
- 3push(30) → [10, 20, 30]
- 4pop() → 30, stack [10, 20]
Stack using a Python list
Python
stack = []
stack.append(10) # push
stack.append(20)
stack.append(30)
print('Stack:', stack, '| top =', stack[-1])
print('Popped:', stack.pop()) # removes the LAST item added
print('Stack now:', stack)Stack: [10, 20, 30] | top = 30
Popped: 30
Stack now: [10, 20]
Stack with functions
Python
def isEmpty(stk):
return len(stk) == 0
def push(stk, item):
stk.append(item)
def pop(stk):
if isEmpty(stk):
return 'Underflow' # nothing to remove
return stk.pop()
def peek(stk):
if isEmpty(stk):
return 'Underflow'
return stk[-1]
def display(stk):
if isEmpty(stk):
print('Stack is empty')
else:
for item in reversed(stk): # top first
print(item)
s = []
push(s, 'A'); push(s, 'B'); push(s, 'C')
display(s)
print('Peek:', peek(s))
print('Pop:', pop(s), pop(s), pop(s))
print('Pop on empty:', pop(s))C
B
A
Peek: C
Pop: C B A
Pop on empty: Underflow
Overflow & underflow
Underflow: popping from an empty stack. Overflow: pushing into a full stack. A Python list grows automatically, so overflow happens only if we set a size limit ourselves.
Python
MAX = 3
def push(stk, item):
if len(stk) == MAX:
print('Overflow! cannot push', item)
else:
stk.append(item)
s = []
for x in [5, 6, 7, 8]:
push(s, x)
print(s)Overflow! cannot push 8
[5, 6, 7]
Applications
Reversing data, checking balanced brackets, undo/redo, function calls (call stack) and converting/evaluating expressions (next lesson).
Python
def reverse_string(text):
stk = []
for ch in text:
stk.append(ch) # push every character
out = ''
while stk:
out += stk.pop() # pop gives them back in reverse
return out
print(reverse_string('PYTHON'))NOHTYP
Python
def balanced(expr):
pairs = {')': '(', ']': '[', '}': '{'}
stk = []
for ch in expr:
if ch in '([{':
stk.append(ch)
elif ch in ')]}':
if not stk or stk.pop() != pairs[ch]:
return False
return len(stk) == 0
for e in ['(a+b)*[c-d]', '((a+b)', '{[()]}', '(]']:
print(e, '->', balanced(e))(a+b)*[c-d] -> True
((a+b) -> False
{[()]} -> True
(] -> False
Board-pattern programs
Python
# Board pattern: push numbers divisible by 5 from a list; then pop & display
N = [12, 15, 30, 7, 45, 9]
stack = []
def PUSH_FIVE(lst):
for n in lst:
if n % 5 == 0:
stack.append(n)
def POP_ALL():
while stack:
print(stack.pop(), end=' ')
print()
print('Stack Empty')
PUSH_FIVE(N)
print(stack)
POP_ALL()[15, 30, 45]
45 30 15
Stack Empty
Python
# Board pattern: dictionary of students -> push names with marks > 75
R = {'Om': 76, 'Jai': 45, 'Bob': 89, 'Ali': 65, 'Anu': 90, 'Tom': 82}
ST = []
def PUSH(S, R):
for name in R:
if R[name] > 75:
S.append(name)
def POP(S):
if S:
return S.pop()
return None
PUSH(ST, R)
while True:
x = POP(ST)
if x is None:
break
print(x, end=' ')
print()Tom Anu Bob Om
Menu-driven stack
Python
def menu():
stk = []
while True:
print('1.Push 2.Pop 3.Peek 4.Display 5.Exit')
ch = int(input('Choice: '))
if ch == 1:
stk.append(input('Item: '))
elif ch == 2:
print('Popped:', stk.pop() if stk else 'Underflow')
elif ch == 3:
print('Top:', stk[-1] if stk else 'Underflow')
elif ch == 4:
print(stk[::-1])
else:
break
menu()1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 1
Item: Pen
1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 1
Item: Book
1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 4
['Book', 'Pen']
1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 2
Popped: Book
1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 3
Top: Pen
1.Push 2.Pop 3.Peek 4.Display 5.Exit
Choice: 5
Summary
- Stack = LIFO, one open end (top).
- push → append(), pop → pop(), peek → [-1].
- Always check empty before pop/peek (underflow).
Frequently Asked Questions
What does LIFO mean?
Last In, First Out: the item pushed last is the first one popped.
What is stack underflow?
Trying to pop or peek from an empty stack. A program should check isEmpty first.
Which list methods implement a stack?
append() for push, pop() for pop, and stk[-1] for peek. All work at the end of the list.
