Stack
CHAPTER 3: STACKS
CHAPTER NOTES
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
Girisha Chandrashekhar
Stack
def isEmpty(glassStack):
return len(glassStack) == 0
# PUSH operation
def opPush(glassStack, element):
[Link](element)
# POP operation
def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
return [Link]()
# 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))
Girisha Chandrashekhar
Stack
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
1. Create empty string postExp and stack stack.
2. 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
3. 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
Summary Points
• Stack = Linear structure, LIFO principle.
• Core ops: PUSH, POP; special cases: Overflow, Underflow.
Girisha Chandrashekhar
Stack
• Python list + append() and pop() can simulate stack.
• Notations: Infix, Prefix, Postfix
• Stacks are essential in converting and evaluating arithmetic expressions.
Girisha Chandrashekhar