root@vm-learning
~
$
open
ch-1-8
UNIT 1 ▪ CHAPTER 8
08
Data Structures — Stack
LIFO · push · pop · peek · isEmpty · List-based Implementation · Applications
A data structure is an organised way to store and manage data so that specific operations (insert, delete, search, sort…) can be done efficiently. The stack is the first — and simplest — data structure on the CBSE syllabus.
Real-life analogy. A stack is like a pile of plates in your kitchen. You place a new plate on the top; when you need one, you also take it from the top. You never grab a plate from the middle — that would bring the whole tower down. This rule — “the last plate in is the first plate out” — is called LIFO: Last-In, First-Out.
8.1 What is a Data Structure?
You already know several data structures from Class XI: list, tuple, dict, set, str. Each one organises its items in a particular way and offers specific operations:
| Structure | How it is organised | Access |
|---|---|---|
| List | Ordered, mutable | By index |
| Tuple | Ordered, immutable | By index |
| Dictionary | Key → value pairs | By key |
| Set | Unordered, unique | Membership test |
| Stack | Linear, last-in-first-out | Only at the top |
Beyond these, computer scientists define many more — queue, linked list, tree, graph, hash table — each tuned for a particular job. CBSE Class XII introduces only one: Stack.
8.2 What is a Stack?
A stack is a linear data structure in which insertion and deletion both happen at the same end, called the top. Elements follow a strict LIFO order — the last element pushed in is the first one to come out.
8.2.1 Everyday examples of a stack
- 🥞 Pile of plates — add or remove only from the top.
- 📚 Stack of books on a table.
- 🌀 Pringles tube / Smarties tube — chips come out in reverse order of the one you put in.
- ⬅️ Browser back-button — the pages you visited are kept in a stack.
- ↩️ Undo in Word, Photoshop, text editors — the most recent action is reversed first.
- 📞 Function call stack — the last function called returns first.
8.2.2 Visualising a Stack
In the picture above, the plates (10, 20, 30, 40) were pushed in that order. A push(50) would place 50 on top; a pop() would remove and return 40 (the most recent plate).
8.3 Stack Operations — the Core Four
| Operation | Does | Returns |
|---|---|---|
push(item) | Insert item on top of the stack | — |
pop() | Remove and return the top item | The removed item |
peek() (or top()) | Look at the top item without removing it | The top item |
isEmpty() | Test whether the stack has no items | True or False |
Many textbooks add a fifth operation —
size() — that returns the number of items. It is handy but not strictly required by CBSE.
8.4 Stack Overflow and Underflow
| Stack Overflow | Stack Underflow | |
|---|---|---|
| When does it happen | Trying to push when the stack is already full | Trying to pop or peek when the stack is empty |
| In a fixed-size stack | Return an error / raise exception | Return an error / raise exception |
| In Python’s list-based stack | Effectively never (list grows automatically) | Must be prevented by checking isEmpty() first |
Because Python’s
list can grow as large as the RAM allows, overflow is rarely a concern in practice. Underflow, however, is a real bug — always check isEmpty() before pop or peek.
8.5 Implementing a Stack Using a Python List
A Python list already supports the two operations we need — append() (adds at the end) and pop() (removes from the end). We treat the end of the list as the top of the stack.
| Stack operation | List method |
|---|---|
push(item) | stack.append(item) |
pop() | stack.pop() |
peek() | stack[-1] |
isEmpty() | len(stack) == 0 |
size() | len(stack) |
8.5.1 Using a list directly
stack = [] # empty stack
stack.append(10) # push 10
stack.append(20) # push 20
stack.append(30) # push 30
print(stack) # [10, 20, 30] — 30 is TOP
top = stack[-1] # peek → 30
item = stack.pop() # pop → 30
print(stack, "popped", item)
[10, 20, 30]
[10, 20] popped 30
8.6 Stack as Functions (CBSE format)
CBSE expects you to write the stack operations as named functions. The stack itself is a normal list that you pass to each function.
def isEmpty(stk):
return len(stk) == 0
def push(stk, item):
stk.append(item)
print(f"pushed {item}")
def pop(stk):
if isEmpty(stk):
print("Underflow — stack is empty")
return None
return stk.pop()
def peek(stk):
if isEmpty(stk):
print("Stack is empty")
return None
return stk[-1]
def display(stk):
if isEmpty(stk):
print("(empty stack)")
return
# print top-to-bottom
for item in reversed(stk):
print("|", item, "|")
print("+---+")
8.6.1 Using the functions
s = []
push(s, 10)
push(s, 20)
push(s, 30)
display(s)
print("peek =", peek(s))
print("pop =", pop(s))
display(s)
print("pop =", pop(s))
print("pop =", pop(s))
print("pop =", pop(s)) # stack is empty here
pushed 10
pushed 20
pushed 30
| 30 |
| 20 |
| 10 |
+---+
peek = 30
pop = 30
| 20 |
| 10 |
+---+
pop = 20
pop = 10
Underflow — stack is empty
pop = None
8.6.2 Stack as a class (optional, for reference)
class Stack:
def __init__(self):
self.items = []
def isEmpty(self): return len(self.items) == 0
def push(self, x): self.items.append(x)
def pop(self): return None if self.isEmpty() else self.items.pop()
def peek(self): return None if self.isEmpty() else self.items[-1]
def size(self): return len(self.items)
def __repr__(self): return "Stack(" + str(self.items) + ")"
s = Stack()
s.push(10); s.push(20); s.push(30)
print(s) # Stack([10, 20, 30])
print(s.pop()) # 30
For CBSE board answers, the function style of §8.6 is the safest choice. Classes (OOP) are not required for Class XII.
8.7 Applications of Stacks
Stacks appear in many places in computer science:
- Reversing a sequence (string, list, number).
- Checking balanced parentheses — compilers use this on every program.
- Converting infix expressions (like
a + b * c) to postfix. - The browser’s Back button and the Forward button (two stacks).
- Undo / Redo in editors.
- Python’s own function-call mechanism — every call pushes a frame.
- Depth-First Search (DFS) in trees and graphs.
8.8 CBSE-style Worked Programs
8.8.1 Menu-driven program for stack operations
def isEmpty(s): return len(s) == 0
def push(s, x): s.append(x)
def pop(s): return None if isEmpty(s) else s.pop()
def peek(s): return None if isEmpty(s) else s[-1]
def display(s):
if isEmpty(s):
print("(empty)"); return
for x in reversed(s):
print("|", x, "|")
print("+---+")
stack = []
while True:
print("\n1. Push 2. Pop 3. Peek 4. Display 5. Quit")
c = input("Choice: ")
if c == "1":
push(stack, input("Item: "))
elif c == "2":
print("Popped:", pop(stack))
elif c == "3":
print("Top :", peek(stack))
elif c == "4":
display(stack)
else:
break
8.8.2 Reverse a string using a stack
def reverse(text):
stack = []
for ch in text:
stack.append(ch) # push every character
result = ""
while stack:
result += stack.pop() # pop one at a time
return result
print(reverse("CBSE 2026")) # '6202 ESBC'
8.8.3 Check if a string of parentheses is balanced
This is the classic stack problem: for every opening bracket we push; for every closing bracket we pop and check whether the pair matches.
def is_balanced(expr):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in expr:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack.pop() != pairs[ch]:
return False
return not stack # stack must be empty at the end
print(is_balanced("(a+b)*(c-d)")) # True
print(is_balanced("{[a+b]*(c-d)}")) # True
print(is_balanced("(a+b*(c-d)")) # False — missing ')'
print(is_balanced("([)]")) # False — mismatched
8.8.4 Push every even number from a list into a stack, then display
def push_evens(nums):
s = []
for n in nums:
if n % 2 == 0:
s.append(n)
return s
print(push_evens([5, 12, 7, 8, 11, 4])) # [12, 8, 4]
8.8.5 Push every word longer than N letters into a stack
def push_long(sentence, n):
s = []
for word in sentence.split():
if len(word) > n:
s.append(word)
return s
print(push_long("Computer Science is fun", 4))
# ['Computer', 'Science']
8.8.6 Reverse a list using a stack
def reverse_list(lst):
stack = list(lst) # copy into a stack
reversed_ = []
while stack:
reversed_.append(stack.pop())
return reversed_
print(reverse_list([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1]
8.8.7 Convert a decimal number to binary using a stack
def to_binary(n):
if n == 0: return "0"
s = []
while n > 0:
s.append(n % 2) # push remainders
n //= 2
# pop in reverse order to build the binary string
bits = ""
while s:
bits += str(s.pop())
return bits
print(to_binary(13)) # '1101'
print(to_binary(29)) # '11101'
8.8.8 Undo-simulator for a simple text editor
text = "" # current text
history = [] # stack of previous states
def type_char(ch):
global text
history.append(text) # push current state
text += ch
def undo():
global text
if history:
text = history.pop()
for ch in "HELLO":
type_char(ch)
print("Typed :", text) # HELLO
undo(); undo()
print("After undo × 2:", text) # HEL
8.9 Common Mistakes to Avoid
| # | Mistake | Fix |
|---|---|---|
| 1 | Calling pop() on an empty stack | Always check isEmpty() first |
| 2 | Treating the start of the list as the top | Use append() / pop() at the end — it is O(1); inserting at index 0 is slow |
| 3 | Forgetting that pop returns the removed item | Store it: x = stack.pop() |
| 4 | Using stack[0] instead of stack[-1] for peek | Top = last element = [-1] |
| 5 | Displaying the stack bottom-to-top in the exam | Convention is top first — use reversed(stack) |
| 6 | Not resetting the stack between test cases | Create a fresh stack = [] for each |
Quick-revision summary
- A stack is a linear, LIFO data structure — insertion and deletion happen only at the top.
- Four core operations:
push,pop,peek,isEmpty. - In Python, a plain
listis a stack:append()=push,pop()=pop,[-1]=peek,len(s)==0=isEmpty. - CBSE style: write the four operations as named functions that take the list as a parameter.
- Overflow is unlikely with a Python list; underflow must be prevented by checking
isEmpty()first. - Classic applications: reversing sequences, checking balanced parentheses, decimal-to-binary conversion, undo operations, browser back button.
Unit 2
Computer
Networks
Networks
Evolution · Media · Devices · Topologies · Protocols · Internet
Chapter 9 • Computer Networks