Stack Implementation Using List

Prerequisites: Lists, functions, loops

---

1. What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

• The last element added is the first one removed., Think of a stack of plates: you add plates on top and remove from the top.

Key Terminology

Term	Meaning
Push	Add an element to the top of the stack
Pop	Remove and return the top element
Peek / Top	View the top element without removing it
Underflow	Trying to pop from an empty stack
Overflow	Trying to push to a full stack (not applicable in Python lists)

---

2. Stack Operations Using Python List

Stack Operation	Python List Method
Push	stack.append(element)
Pop	stack.pop
Peek	stack[-1] or stack[len(stack)-1]
isEmpty	len(stack) == 0
Size	len(stack)
Display	Print the list

---

3. Applications of Stack

• Undo operation in text editors
• Browser back button - history of pages
• Parenthesis matching in compilers
• Infix to Postfix expression conversion
• Postfix expression evaluation
• Function call management (call stack)
• Reversing a string or list

---

4. Stack Implementation

# Complete Stack Implementation

def push(stack, element):
 """Push an element onto the stack."""
 stack.append(element)
 print(f"Pushed: {element}")

def pop(stack):
 """Pop and return the top element."""
 if isEmpty(stack):
 print("Underflow! Stack is empty.")
 return None
 else:
 return stack.pop

def peek(stack):
 """Return the top element without removing it."""
 if isEmpty(stack):
 print("Stack is empty - nothing to peek.")
 return None
 else:
 return stack[-1]

def isEmpty(stack):
 """Check if stack is empty."""
 return len(stack) == 0

def size(stack):
 """Return the number of elements."""
 return len(stack)

def display(stack):
 """Display the stack from top to bottom."""
 if isEmpty(stack):
 print("Stack is empty.")
 else:
 print("Stack (top to bottom):")
 for i in range(len(stack) - 1, -1, -1):
 if i == len(stack) - 1:
 print(f" | {stack[i]} | <-- TOP")
 else:
 print(f" | {stack[i]} |")
 print(" +-----+")

Usage Example

stack = []

push(stack, 10) # Pushed: 10
push(stack, 20) # Pushed: 20
push(stack, 30) # Pushed: 30

display(stack)
# Stack (top to bottom):
# | 30 | <-- TOP
# | 20 |
# | 10 |
# +-----+

print("Top:", peek(stack)) # Top: 30
print("Size:", size(stack)) # Size: 3

val = pop(stack)
print("Popped:", val) # Popped: 30

display(stack)
# Stack (top to bottom):
# | 20 | <-- TOP
# | 10 |
# +-----+

---

Practice Programs

Program 1: Complete Menu-Driven Stack Program

def push(stack, element):
 stack.append(element)
 print(f" {element} pushed to stack.")

def pop(stack):
 if len(stack) == 0:
 print(" Underflow! Stack is empty.")
 return None
 else:
 return stack.pop

def peek(stack):
 if len(stack) == 0:
 print(" Stack is empty.")
 return None
 else:
 return stack[-1]

def display(stack):
 if len(stack) == 0:
 print(" Stack is empty.")
 else:
 print(" Stack (top to bottom):", end=" ")
 for i in range(len(stack) - 1, -1, -1):
 print(stack[i], end=" ")
 print

# Main program
stack = []

while True:
 print("\n===== STACK MENU =====")
 print("1. Push")
 print("2. Pop")
 print("3. Peek")
 print("4. Display")
 print("5. Size")
 print("6. Exit")
 print("======================")

 choice = input("Enter choice (1-6): ")

 if choice == "1":
 element = input(" Enter element to push: ")
 push(stack, element)
 elif choice == "2":
 val = pop(stack)
 if val is not None:
 print(f" Popped: {val}")
 elif choice == "3":
 val = peek(stack)
 if val is not None:
 print(f" Top element: {val}")
 elif choice == "4":
 display(stack)
 elif choice == "5":
 print(f" Stack size: {len(stack)}")
 elif choice == "6":
 print("Exiting. Goodbye!")
 break
 else:
 print(" Invalid choice!")

# Sample Interaction:
# ===== STACK MENU =====
# 1. Push
# 2. Pop
# 3. Peek
# 4. Display
# 5. Size
# 6. Exit
# ======================
# Enter choice (1-6): 1
# Enter element to push: 10
# 10 pushed to stack.
#
# Enter choice (1-6): 1
# Enter element to push: 20
# 20 pushed to stack.
#
# Enter choice (1-6): 4
# Stack (top to bottom): 20 10
#
# Enter choice (1-6): 2
# Popped: 20

Program 2: Reverse a String Using Stack

def reverse_string(text):
 stack = []

 # Push all characters
 for char in text:
 stack.append(char)

 # Pop all characters
 reversed_text = ""
 while len(stack) > 0:
 reversed_text += stack.pop

 return reversed_text

# Test
original = input("Enter a string: ")
reversed_str = reverse_string(original)
print(f"Original : {original}")
print(f"Reversed : {reversed_str}")

# Test Run:
# Enter a string: PYTHON
# Original : PYTHON
# Reversed : NOHTYP

# Trace for "PYTHON":
# Push: P -> Y -> T -> H -> O -> N
# Stack: ['P', 'Y', 'T', 'H', 'O', 'N']
# Pop: N -> O -> H -> T -> Y -> P
# Result: "NOHTYP"

Program 3: Check Balanced Parentheses

def is_balanced(expression):
 stack = []
 opening = "({["
 closing = ")}]"
 pairs = {")": "(", "}": "{", "]": "["}

 for char in expression:
 if char in opening:
 stack.append(char)
 elif char in closing:
 if len(stack) == 0:
 return False
 if stack[-1] == pairs[char]:
 stack.pop
 else:
 return False

 return len(stack) == 0

# Test cases
expressions = [
 "{(a+b)*[c-d]}",
 "((a+b)",
 "{[a+b}]",
 "(a+b)*(c-d)",
 "(())",
 "(",
]

for expr in expressions:
 result = "Balanced" if is_balanced(expr) else "NOT Balanced"
 print(f" {expr:<20} -> {result}")

# Output:
# {(a+b)*[c-d]} -> Balanced
# ((a+b) -> NOT Balanced
# {[a+b}] -> NOT Balanced
# (a+b)*(c-d) -> Balanced
# (()) -> Balanced
# ( -> NOT Balanced

# Trace for "{(a+b)*[c-d]}":
# Char Action Stack
# { Push { ['{']
# ( Push ( ['{', '(']
# a Ignore ['{', '(']
# + Ignore ['{', '(']
# b Ignore ['{', '(']
# ) Pop ( matches ['{']
# * Ignore ['{']
# [ Push [ ['{', '[']
# c Ignore ['{', '[']
# - Ignore ['{', '[']
# d Ignore ['{', '[']
# ] Pop [ matches ['{']
# } Pop { matches []
# Stack empty -> Balanced!

Program 4: Stack of Odd Numbers, Find Largest

def push(stack, element):
 stack.append(element)

def find_largest(stack):
 if len(stack) == 0:
 return None
 largest = stack[0]
 for item in stack:
 if item > largest:
 largest = item
 return largest

# Main program
stack = []

# Push numbers and keep only odd ones
numbers = [12, 7, 34, 19, 5, 42, 27, 8, 31, 14]
print("Input numbers:", numbers)

for num in numbers:
 if num % 2 != 0: # Odd number
 push(stack, num)

print("Stack of odd numbers:", stack)
print("Largest odd number:", find_largest(stack))

# Output:
# Input numbers: [12, 7, 34, 19, 5, 42, 27, 8, 31, 14]
# Stack of odd numbers: [7, 19, 5, 27, 31]
# Largest odd number: 31

Program 5: Infix to Postfix Conversion

def precedence(op):
 """Return precedence of operator."""
 if op in ('+', '-'):
 return 1
 elif op in ('*', '/'):
 return 2
 elif op == '^':
 return 3
 return 0

def infix_to_postfix(expression):
 """Convert infix expression to postfix."""
 stack = [] # Operator stack
 postfix = "" # Result string
 
 print(f"\nConverting: {expression}")
 print(f"{'Symbol':<10}{'Stack':<20}{'Postfix':<20}")
 print("-" * 50)
 
 for char in expression:
 if char.isalnum:
 # Operand - add to output
 postfix += char
 elif char == '(':
 # Left parenthesis - push to stack
 stack.append(char)
 elif char == ')':
 # Right parenthesis - pop until '('
 while len(stack) > 0 and stack[-1] != '(':
 postfix += stack.pop
 if len(stack) > 0:
 stack.pop # Remove '('
 else:
 # Operator - pop higher/equal precedence operators
 while (len(stack) > 0 and
 stack[-1] != '(' and
 precedence(stack[-1]) >= precedence(char)):
 postfix += stack.pop
 stack.append(char)
 
 print(f"{char:<10}{str(stack):<20}{postfix:<20}")
 
 # Pop remaining operators
 while len(stack) > 0:
 postfix += stack.pop
 
 print(f"{'Pop all':<10}{str(stack):<20}{postfix:<20}")
 return postfix

# Test cases
expr1 = "A+B*C"
result1 = infix_to_postfix(expr1)
print(f"\nResult: {expr1} -> {result1}")

# Output:
# Converting: A+B*C
# Symbol Stack Postfix
# --------------------------------------------------
# A [] A
# + ['+'] A
# B ['+'] AB
# * ['+', '*'] AB
# C ['+', '*'] ABC
# Pop all [] ABC*+
#
# Result: A+B*C -> ABC*+

expr2 = "(A+B)*C-D"
result2 = infix_to_postfix(expr2)
print(f"\nResult: {expr2} -> {result2}")

# Output:
# Converting: (A+B)*C-D
# Symbol Stack Postfix
# --------------------------------------------------
# ( ['('] 
# A ['('] A
# + ['(', '+'] A
# B ['(', '+'] AB
# ) [] AB+
# * ['*'] AB+
# C ['*'] AB+C
# - ['-'] AB+C*
# D ['-'] AB+C*D
# Pop all [] AB+C*D-
#
# Result: (A+B)*C-D -> AB+C*D-

expr3 = "A*(B+C)/D"
result3 = infix_to_postfix(expr3)
print(f"\nResult: {expr3} -> {result3}")

# Output:
# Converting: A*(B+C)/D
# Symbol Stack Postfix
# --------------------------------------------------
# A [] A
# * ['*'] A
# ( ['*', '('] A
# B ['*', '('] AB
# + ['*', '(', '+'] AB
# C ['*', '(', '+'] ABC
# ) ['*'] ABC+
# / ['/'] ABC+*
# D ['/'] ABC+*D
# Pop all [] ABC+*D/
#
# Result: A*(B+C)/D -> ABC+*D/

Program 6: Postfix Expression Evaluation

def evaluate_postfix(expression):
 """Evaluate a postfix expression."""
 stack = []
 
 print(f"\nEvaluating: {expression}")
 print(f"{'Symbol':<10}{'Action':<25}{'Stack':<20}")
 print("-" * 55)
 
 for char in expression:
 if char.isdigit:
 stack.append(int(char))
 print(f"{char:<10}{'Push ' + char:<25}{str(stack):<20}")
 else:
 # Operator - pop two operands
 op2 = stack.pop
 op1 = stack.pop
 
 if char == '+':
 result = op1 + op2
 elif char == '-':
 result = op1 - op2
 elif char == '*':
 result = op1 * op2
 elif char == '/':
 result = op1 / op2
 elif char == '^':
 result = op1 ** op2
 
 stack.append(result)
 action = f"{op1} {char} {op2} = {result}"
 print(f"{char:<10}{action:<25}{str(stack):<20}")
 
 return stack.pop

# Test 1: 2 3 + 5 * = (2+3)*5 = 25
expr1 = "23+5*"
result1 = evaluate_postfix(expr1)
print(f"\nResult: {result1}")

# Output:
# Evaluating: 23+5*
# Symbol Action Stack
# -------------------------------------------------------
# 2 Push 2 [2]
# 3 Push 3 [2, 3]
# + 2 + 3 = 5 [5]
# 5 Push 5 [5, 5]
# * 5 * 5 = 25 [25]
#
# Result: 25

# Test 2: 5 3 2 * + 4 - = 5+(3*2)-4 = 7
expr2 = "532*+4-"
result2 = evaluate_postfix(expr2)
print(f"\nResult: {result2}")

# Output:
# Evaluating: 532*+4-
# Symbol Action Stack
# -------------------------------------------------------
# 5 Push 5 [5]
# 3 Push 3 [5, 3]
# 2 Push 2 [5, 3, 2]
# * 3 * 2 = 6 [5, 6]
# + 5 + 6 = 11 [11]
# 4 Push 4 [11, 4]
# - 11 - 4 = 7 [7]
#
# Result: 7

# Test 3: 6 2 / 3 + 4 2 * - = (6/2)+3-(4*2) = 3+3-8 = -2
expr3 = "62/3+42*-"
result3 = evaluate_postfix(expr3)
print(f"\nResult: {result3}")

# Output:
# Evaluating: 62/3+42*-
# Symbol Action Stack
# -------------------------------------------------------
# 6 Push 6 [6]
# 2 Push 2 [6, 2]
# / 6 / 2 = 3.0 [3.0]
# 3 Push 3 [3.0, 3]
# + 3.0 + 3 = 6.0 [6.0]
# 4 Push 4 [6.0, 4]
# 2 Push 2 [6.0, 4, 2]
# * 4 * 2 = 8 [6.0, 8]
# - 6.0 - 8 = -2.0 [-2.0]
#
# Result: -2.0

---

Common Mistakes

Mistake	Correct Approach
Using stack.pop(0) for stack	pop(0) removes from bottom (queue); use pop for stack
Not checking for empty stack before pop	Always check len(stack) == 0 before popping
Using stack[0] for peek	Top element is stack[-1] or stack[len(stack)-1]
Confusing stack (LIFO) with queue (FIFO)	Stack = LIFO (Last In First Out)
Forgetting to return the popped value	pop returns the removed element; use it
Display order wrong	Display from top (last index) to bottom (index 0)

---

$1$2 Quick Tips

1. push = append, pop = pop - this mapping is asked in almost every exam.
2. Menu-driven program is a very common 5-mark question. Practice the complete implementation.
3. Underflow condition: Always check if the stack is empty before pop. Print "Underflow" or "Stack is empty".
4. Trace questions: You may be asked to show the stack state after each push/pop operation. Practice tracing step by step.
5. Applications of stack: Know at least 3-4 applications (undo, browser back, parenthesis matching, infix to postfix).
6. LIFO: Be very clear, Last In First Out. Draw a diagram if needed.
7. Infix to Postfix: Know the algorithm and practice with at least 3 expressions. Remember operator precedence: ^ > *, / > +, -.
8. Postfix Evaluation: Know the algorithm: push operands, pop two when operator encountered, push result.
9. In code, display stack from top to bottom (reverse order of list) to show correct stack visualization.