CHAPTER 3: STACKS
3.1 Introduction
Data Structures: Ways to store, organize, and access data efficiently.
Examples: String, List, Set, Tuple, Array, Linked List, Stack, Queue, Trees, Graphs, etc.
Stack and Queue are not built-in Python structures but can be implemented using lists.
3.2 Stack
Definition: A linear data structure where elements are added/removed from one end (TOP).
LIFO Principle: Last In, First Out – the last element added is the first to be removed.
Analogy: Stack of plates or books – add/remove only from the top.
3.2.1 Applications of Stack
Real-life Scenarios
1. Pile of clothes in an almirah – Clothes are added or removed from the top of the pile,
following the LIFO order.
2. Multiple chairs in a vertical pile – Chairs are stacked one on top of the other, and removed in
reverse order.
3. Bangles worn on the wrist – The last bangle worn is the first to be removed.
4. Boxes of eatables in pantry – Boxes are added and removed from the top for convenience.
Programming Applications
1. String Reversal
Characters are added to a stack and popped in reverse order to reverse the string.
2. Undo/Redo in Editors
Each edit (text/image) is pushed onto a stack. Undo removes the last change, redo re-applies it.
3. Back Function in Web Browsers
Navigated pages are pushed onto a stack. Pressing 'Back' pops the last visited page and returns
to the previous one.
4. Parentheses Matching in Expressions
During program execution, a stack is used to ensure every opening parenthesis has a matching
closing one. It helps identify syntax errors like unmatched or misnested parentheses.
3.3 Operations on Stack
PUSH: Add an element to the TOP of the stack.
POP: Remove the topmost element.
Overflow: Trying to PUSH to a full stack (not typically an issue in Python).
Underflow: Trying to POP from an empty stack.
3.4 Implementation of Stack in Python
Functions:
# Create an empty stack
glassStack = list()
# Check if stack is empty
def isEmpty(glassStack):
return len(glassStack) == 0
# PUSH operation
def opPush(glassStack, element):
glassStack.append(element)
# POP operation
def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
return glassStack.pop()
# Return stack size
def size(glassStack):
return len(glassStack)
# Return top element
def top(glassStack):
if isEmpty(glassStack):
print("Stack is empty")
return None
else:
return glassStack[-1]
# Display all elements (from TOP to bottom)
def display(glassStack):
print("Current elements in the stack are:")
for i in range(len(glassStack)-1, -1, -1):
print(glassStack[i])
Sample Program:
glassStack = list() # create empty stack
element = 'glass1'
print("Pushing element", element)
opPush(glassStack, element)
element = 'glass2'
print("Pushing element", element)
opPush(glassStack, element)
print("Current number of elements in stack is", size(glassStack))
element = opPop(glassStack)
print("Popped element is", element)
element = 'glass3'
print("Pushing element", element)
opPush(glassStack, element)
print("Top element is", top(glassStack))
display(glassStack)
# delete all elements
while True:
item = opPop(glassStack)
if item is None:
break
print("Popped element is", item)
print("Stack is empty now")
3.5 Notations for Arithmetic Expressions
Notation Description Example
Infix Operator between operands (x +y) / (z * 5)
Prefix Operator before operands /+xy*z5
Postfix Operator after operands Xy+z5*/
Prefix (Polish) and Postfix (Reverse Polish) do not require parentheses.
Infix needs BODMAS and parentheses for clarity.
3.6 Conversion from Infix to Postfix
Why? Computers struggle with operator precedence in infix; postfix avoids this.
Algorithm 3.1: Infix to Postfix
Create empty string postExp and stack stack.
For each character in infix expression:
If ( → PUSH to stack
If ) → POP and add to postExp until ( is found
If operator:
POP higher or equal precedence operators and append to postExp
PUSH current operator
If operand → Append to postExp
POP remaining operators to postExp.
Example: (x + y)/(z * 8) → xy+z8/
3.7 Evaluation of Postfix Expression
Algorithm 3.2:
1. For each character in postfix expression:
If operand → PUSH to stack
If operator → POP two operands, apply operation, PUSH result
2. At the end, if one item in stack → Result
3.Else → Invalid expression
Example: 7 8 2 * 4 / + → Result: 11
Convert the following infix expression into postfix
1. (A + B) * (C + D) - E
2. A – (B + C) * D + E / F
3. ((A + B) / (C – D) + E) * F – G
4. A + B * (C + D) – E / F * G + H
5. ((A – (B + C). D) / (E + F))
Evaluate the following postfix expressions:
1. 82 + 3 * 164 / -
2. 12 25 5 1 / / * 8 7 + -
3. 70 14 4 5 15 3 / * - - / 6 +
4. 3 5 6 * + 13 – 18 2 / +
