Chapter 3 - Stack
1. Stack Definition.
>> A stack is a linear data structure that follows the LIFO (Last In,
First Out) principle, where the last element inserted is the first to
be removed.
Example: A stack of plates.
2. Application of Stack in Computer Science / Programming.
>> •Expression evaluation and conversion (infix, postfix, prefix)
•Function call management (call stack).
•Undo/redo functionality in text editors.
•Syntax parsing in compilers.
•Backtracking algorithms (maze solving, DFS in graphs).
•Memory management (stack memory in program execution).
3. Application of Stack in Real Life
>>•Plate dispensers (last plate added is first taken)
•Books pile on a table
•Back/Forward navigation in browsers
•Reversing a word character-by-character
•Undo feature in word processors
4. Algorithm to Convert Infix to Postfix
Algorithm:
1. Initialize an empty stack for operators.
2. Scan the infix expression from left to right.
3. If the scanned character is an operand, add it to the postfix
expression.
4. If it is an operator:
While stack is not empty and precedence of scanned operator ≤
precedence of top of stack, pop from stack to postfix.
Push the scanned operator to stack.
5. If it is ‘(’, push to stack.
6. If it is ‘)’, pop from stack to postfix until ‘(’ is found, then
remove ‘(’.
7. After scanning, pop remaining operators to postfix.
5. Algorithm to Evaluate Postfix Expression
Algorithm:
1. Initialize an empty stack.
2. Scan postfix expression left to right.
3. If operand, push to stack.
4. If operator:
Pop top two elements, apply operator, push result back.
5. After complete scan, the top of the stack is the result.
6. Infix to Postfix Conversion Problem (Example)
>>Infix: A + B * C
Postfix: A B C * +
7. Evaluate Postfix Expression Problem (Example)
>>Postfix: **6 2 3 + - 3 8 2 / + ***
Step-by-step evaluation → Final Result: -18