Chapter 03 - Stack
3.1 Introduction
In computer science, data structures are used to organize and store data efficiently.
Some commonly used data structures:
- Stack
- Queue
- List
- Tree
- Graph
👉 Stack is a linear data structure where insertion and deletion are allowed only from one end.
3.2 Stack
What is a Stack?
A stack is a linear data structure that follows the principle:
LIFO – Last In, First Out
📌 The last element inserted is the first one removed.
Real-Life Examples
- Stack of books
- Stack of plates
- Browser history
- Undo/Redo operations
- Call stack in programs
Stack Terminology
- Top → Points to the topmost element
- Bottom → First inserted element
- Overflow → Stack is full
- Underflow → Stack is empty
Diagram (Conceptual)
| 30 | ← TOP
| 20 |
| 10 | ← BOTTOM
3.3 Operations on Stack
1️⃣ PUSH (Insertion)
- Adds an element at the top
- Causes overflow if stack is full
2️⃣ POP (Deletion)
- Removes the top element
- Causes underflow if stack is empty
3️⃣ PEEK / TOP
- Returns top element without removing it
4️⃣ DISPLAY
- Shows all stack elements
Error Conditions
| Condition | Meaning |
|---|---|
| Overflow | PUSH on full stack |
| Underflow | POP on empty stack |
3.4 Implementation of Stack in Python
Stacks can be implemented using:
- List
- Collections module
- User-defined functions (NCERT method) ✅
We use list-based implementation (NCERT standard).
🔸 Stack Using List (Menu Driven)
stack = []
MAX = 5
def push():
if len(stack) == MAX:
print("Stack Overflow")
else:
item = int(input("Enter element: "))
stack.append(item)
print("Pushed:", item)
def pop():
if len(stack) == 0:
print("Stack Underflow")
else:
item = stack.pop()
print("Popped:", item)
def peek():
if len(stack) == 0:
print("Stack is empty")
else:
print("Top element:", stack[-1])
def display():
if len(stack) == 0:
print("Stack is empty")
else:
print("Stack elements:")
for i in range(len(stack)-1, -1, -1):
print(stack[i])
while True:
print("\n1.Push 2.Pop 3.Peek 4.Display 5.Exit")
ch = int(input("Enter choice: "))
if ch == 1:
push()
elif ch == 2:
pop()
elif ch == 3:
peek()
elif ch == 4:
display()
elif ch == 5:
break
else:
print("Invalid choice")
📌 Highly important program for boards
3.5 Notations for Arithmetic Expressions
Arithmetic expressions can be written in three notations:
1️⃣ Infix Notation
- Operator between operands
- Most common
Example:
A + B
(5 + 3) * 2
2️⃣ Postfix Notation (Reverse Polish)
- Operator after operands
Example:
AB+
53+2*
3️⃣ Prefix Notation (Polish)
- Operator before operands
Example:
+AB
*+532
Comparison Table
| Notation | Example |
|---|---|
| Infix | A + B |
| Postfix | AB+ |
| Prefix | +AB |
📌 Stacks are mainly used for postfix evaluation
3.6 Conversion from Infix to Postfix Notation
Why Convert?
- Infix needs parentheses and precedence
- Postfix does not need parentheses
- Easy for computer evaluation using stack
Operator Precedence
| Operator | Priority |
|---|---|
^ |
Highest |
*, / |
Medium |
+, - |
Lowest |
Algorithm (Board Theory Points)
- Initialize empty stack and postfix string
- Scan infix expression left to right
- Operand → add to postfix
(→ push to stack)→ pop until(is found- Operator → pop higher/equal precedence operators
- Pop remaining operators at end
Python Program: Infix → Postfix
def precedence(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
if op == '^':
return 3
return 0
def infix_to_postfix(exp):
stack = []
postfix = ""
for ch in exp:
if ch.isalnum():
postfix += ch
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop()
else:
while stack and precedence(ch) <= precedence(stack[-1]):
postfix += stack.pop()
stack.append(ch)
while stack:
postfix += stack.pop()
return postfix
exp = input("Enter infix expression: ")
print("Postfix:", infix_to_postfix(exp))
📌 Very high probability board question
3.7 Evaluation of Postfix Expression
Rules
- Scan postfix expression left to right
- Operand → push to stack
- Operator → pop two operands
- Apply operation
- Push result back
- Final stack value = result
Python Program: Postfix Evaluation
def evaluate_postfix(exp):
stack = []
for ch in exp:
if ch.isdigit():
stack.append(int(ch))
else:
b = stack.pop()
a = stack.pop()
if ch == '+':
stack.append(a + b)
elif ch == '-':
stack.append(a - b)
elif ch == '*':
stack.append(a * b)
elif ch == '/':
stack.append(a / b)
return stack[0]
exp = input("Enter postfix expression: ")
print("Result:", evaluate_postfix(exp))
📌 Example:
Input: 23*54*+9-
Output: 17
📝 NCERT EXAM SUMMARY (Must Learn)
- Stack follows LIFO
- Push → insert
- Pop → delete
- Overflow → full stack
- Underflow → empty stack
Stack used in:
- Expression evaluation
- Function calls
- Undo/Redo
Postfix is most efficient
Board-Level Solved Programs (10 Programs)
Program 1: Implement Stack Using List (Basic)
stack = []
stack.append(10)
stack.append(20)
stack.append(30)
print("Stack:", stack)
📌 Concept: Stack creation using list
Program 2: Push Operation with Overflow Check
stack = []
MAX = 3
def push(item):
if len(stack) == MAX:
print("Stack Overflow")
else:
stack.append(item)
print("Pushed:", item)
push(10)
push(20)
push(30)
push(40)
📌 Concept: Overflow condition
Program 3: Pop Operation with Underflow Check
stack = []
def pop():
if len(stack) == 0:
print("Stack Underflow")
else:
print("Popped:", stack.pop())
pop()
stack.append(5)
pop()
📌 Concept: Underflow condition
Program 4: Peek (Top Element of Stack)
stack = [10, 20, 30]
if len(stack) == 0:
print("Stack is empty")
else:
print("Top element:", stack[-1])
📌 Concept: Accessing top without removal
Program 5: Display Stack Elements
stack = [10, 20, 30, 40]
print("Stack elements:")
for i in range(len(stack)-1, -1, -1):
print(stack[i])
📌 Concept: Stack traversal (top to bottom)
Program 6: Menu-Driven Stack Program
stack = []
while True:
print("\n1.Push 2.Pop 3.Display 4.Exit")
ch = int(input("Enter choice: "))
if ch == 1:
item = int(input("Enter element: "))
stack.append(item)
elif ch == 2:
if len(stack) == 0:
print("Stack Underflow")
else:
print("Popped:", stack.pop())
elif ch == 3:
print(stack[::-1])
elif ch == 4:
break
else:
print("Invalid choice")
📌 VERY IMPORTANT practical program
Program 7: Convert Infix Expression to Postfix
def precedence(op):
if op in '+-':
return 1
if op in '*/':
return 2
return 0
def infix_to_postfix(exp):
stack = []
postfix = ""
for ch in exp:
if ch.isalnum():
postfix += ch
elif ch == '(':
stack.append(ch)
elif ch == ')':
while stack and stack[-1] != '(':
postfix += stack.pop()
stack.pop()
else:
while stack and precedence(ch) <= precedence(stack[-1]):
postfix += stack.pop()
stack.append(ch)
while stack:
postfix += stack.pop()
return postfix
print(infix_to_postfix("A+B*C"))
📌 High-weight board question
Program 8: Evaluate Postfix Expression
def evaluate_postfix(exp):
stack = []
for ch in exp:
if ch.isdigit():
stack.append(int(ch))
else:
b = stack.pop()
a = stack.pop()
if ch == '+':
stack.append(a + b)
elif ch == '-':
stack.append(a - b)
elif ch == '*':
stack.append(a * b)
elif ch == '/':
stack.append(a / b)
return stack[0]
print(evaluate_postfix("23*54*+"))
📌 Concept: Stack-based evaluation
Program 9: Reverse a String Using Stack
stack = []
text = "PYTHON"
for ch in text:
stack.append(ch)
rev = ""
while stack:
rev += stack.pop()
print("Reversed string:", rev)
📌 Application of stack
Program 10: Check Balanced Parentheses
def is_balanced(exp):
stack = []
for ch in exp:
if ch == '(':
stack.append(ch)
elif ch == ')':
if not stack:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("(A+B)*(C+D)"))
📌 Frequently asked logic question
Case-Study Questions (CBSE 2025 Pattern)
Case Study 1: Expression Evaluation System
A calculator application uses stack to evaluate expressions.
Questions:
Which expression notation is easiest for computer evaluation? ✔ Postfix
Which data structure is used? ✔ Stack
Write a Python function to evaluate a postfix expression.
def eval_postfix(exp): stack = [] for ch in exp: if ch.isdigit(): stack.append(int(ch)) else: b = stack.pop() a = stack.pop() if ch == '+': stack.append(a + b) elif ch == '*': stack.append(a * b) return stack[0]
Case Study 2: Browser History Feature
A web browser stores visited pages so that the last visited page is shown first.
Questions:
Which data structure is suitable? ✔ Stack
Which principle does it follow? ✔ LIFO
Why stack is preferred over queue? ✔ Because last page visited must be accessed first.
Case Study 3: Syntax Checker Tool
A compiler checks whether parentheses in a program are balanced.
Questions:
Which stack operation is used when encountering
(? ✔ PushWhich operation is used when encountering
)? ✔ PopWrite a function to check balanced parentheses.
def check_parentheses(exp): stack = [] for ch in exp: if ch == '(': stack.append(ch) elif ch == ')': if not stack: return False stack.pop() return len(stack) == 0