Revision Summary: Stack (NCERT Class 12 Computer Science)
1. Chapter at a Glance
- A stack is a linear data structure in which elements are added and removed only from one end called TOP, following the Last-In-First-Out (LIFO) principle.
- The two fundamental operations are PUSH (insertion at TOP) and POP (deletion from TOP).
- Attempting PUSH on a full stack causes overflow; attempting POP on an empty stack causes underflow.
- In Python, a stack is implemented using a list with
append() for PUSH and pop() for POP; TOP need not be declared explicitly.
- Arithmetic expressions can be written in three notations: Infix (operators between operands), Prefix (operators before operands), and Postfix (operators after operands).
- Stack is used to convert an infix expression to postfix by pushing operators and parentheses and appending operands and popped operators to a result string.
- Stack evaluates a postfix expression by pushing operands and popping two operands for each operator, then pushing the result back.
- Applications include reversing strings, handling undo/redo, browser history, and matching parentheses.
2. Key Terms and Definitions
- Stack: A data structure in which elements are organised in a sequence and insertion/deletion occurs only at one end (TOP), following LIFO.
- LIFO (Last-In-First-Out): The principle that the element inserted last is the first one to be removed.
- TOP: The end of the stack from which elements are added or deleted.
- PUSH: The operation that adds a new element at the TOP of the stack (insertion).
- POP: The operation that removes the topmost element from the stack (deletion).
- Overflow: The exception that occurs when trying to add an element to a full stack.
- Underflow: The exception that occurs when trying to delete an element from an empty stack.
- Infix notation: Expression form where operators are placed between operands (e.g., x + y).
- Prefix notation (Polish): Expression form where operators are placed before operands (e.g., +xy).
- Postfix notation (Reverse Polish): Expression form where operators are placed after operands (e.g., xy+).
3. Syntax and Constructs
python
glassStack = list() # create empty stack
opPush(glassStack, element) # PUSH using list.append()
element = opPop(glassStack) # POP using list.pop()
python
def isEmpty(glassStack):
return len(glassStack) == 0
python
def size(glassStack):
return len(glassStack)
python
def top(glassStack):
if isEmpty(glassStack):
return None
return glassStack[-1]
python
def display(glassStack):
for i in range(len(glassStack)-1, -1, -1):
print(glassStack[i])
4. Algorithms and Worked Logic
Infix to Postfix Conversion (Algorithm 3.1)
- Create empty string postExp.
- For each character in infix expression:
– Left parenthesis → PUSH on stack.
– Right parenthesis → POP until matching left parenthesis, append popped items to postExp.
– Operator → POP higher/equal precedence operators to postExp, then PUSH current operator.
– Operand → append directly to postExp.
- After scanning, POP remaining stack contents to postExp.
Postfix Evaluation (Algorithm 3.2)
- For each character in postfix expression:
– Operand → PUSH on stack.
– Operator → POP two operands, apply operator, PUSH result.
- At end, the single remaining stack element is the result (or expression is invalid).
5. Common Errors and Exam Pitfalls
- Forgetting to check
isEmpty() before POP, leading to underflow.
- Assuming the stack can overflow in Python list implementation (it cannot, as lists are dynamic).
- Reversing precedence logic while converting infix to postfix (lower precedence must be popped first).
- Not discarding both parentheses after matching during conversion.
- In evaluation, pushing operators or popping only one operand.
- Writing code that prints “underflow” but does not return
None, causing further errors.
- Confusing the order of operands while applying an operator during postfix evaluation.