STACKS
Definition:A Stack is an abstract data structure that operates on the LIFO (Last-In, First-Out) principle. This implies that the element which is inserted last is the first to be removed. Stacks are quintessential in various computational processes, including expression evaluation, memory management, and algorithmic problem solving.
Implementation of Single Stack using Array
A single stack can be efficiently realized using a one-dimensional array alongside a variable termed as top, which signifies the index of the current topmost element in the stack.
Core Operations:
Push: Inserts an element at the top of the stack.
Pop: Removes the element present at the top.
Peek (Top): Returns the top element without deletion.
isEmpty: Validates if the stack is vacant.
isFull: Checks if the stack has reached its storage capacity.
C Implementation:
#define MAX 100
int stack[MAX];
int top = -1;
void push(int val) {
if(top == MAX – 1)
printf(“Stack Overflow\n”);
else
stack[++top] = val;
}
void pop() {
if(top == -1)
printf(“Stack Underflow\n”);
else
top–;
}
Implementation of Multiple Stacks within a Single Array
To optimize memory utilization, multiple stacks can be constructed within a common array structure. For example, two stacks can simultaneously inhabit a single array space:
Stack1: Expands from the starting index (0) towards higher indices.
Stack2: Expands from the terminating index (MAX-1) towards lower indices.
Key Condition for Safe Insertion:
if (top1 < top2 – 1)
This ensures that the two stacks do not overlap, thus preventing overflow errors.
Expression Notations: Prefix, Infix, and Postfix
Expression conversion and evaluation is a principal application of stacks in compilers and interpreters.
Infix Expression
An Infix Expression is a mathematical notation in which every operator is written between the operands it operates upon. This is the most common and natural way humans write and interpret arithmetic expressions.
Structure:
Operand1 Operator Operand2
For example:
A + B
Here, A and B are operands and + is the operator.
Examples of Infix Expressions:
- A + B
- (A + B) * C
- (A + B) * (C – D)
In these expressions, brackets () are often required to maintain operator precedence and associativity.
Operator Precedence & Associativity in Infix:
| Operator | Precedence | Associativity |
| () (Parentheses) | Highest | Left to Right |
| * / % | Higher | Left to Right |
| + – | Lower | Left to Right |
Brackets are essential to override natural precedence and force a desired order of evaluation.
Drawbacks of Infix Expressions:
Requires Parentheses to specify the intended order of operations.
Difficult for computer evaluation due to ambiguity without explicit order, hence compilers convert infix to postfix or prefix for processing.
Conversion to Other Notations (Using Stack):
Infix to Prefix (Polish Notation): Operator comes before operands.
Infix to Postfix (Reverse Polish Notation): Operator comes after operands.
For example:
Infix: (A + B) * C
Prefix: * + A B C
Postfix: A B + C *
Summary:
Infix is human-readable but complex for machines to evaluate directly.
Compilers convert infix expressions to prefix or postfix for execution simplicity.
If you want an example of Infix to Postfix conversion using Stack (with algorithm or C code), I can provide that too!
Tools
Operators are written between operands.
Example: A + B
P|refix Expression (Polish Notation)
A Prefix Expression, also known as Polish Notation, is a form of mathematical expression where operators precede their operands. In this notation, the operator is written before the two operands it will operate upon.
Structure:
Operator Operand1 Operand2
For example:
+ A B
This is equivalent to A + B in Infix form.
Examples of Prefix Expressions:
- + A B → Equivalent to A + B
- * + A B C → Equivalent to (A + B) * C
- – * A B / C D → Equivalent to (A * B) – (C / D)
Evaluation of Prefix Expression:
Scan the expression from right to left.
When an operand is encountered, push it onto a stack.
When an operator is encountered, pop two operands, apply the operator, and push the result back onto the stack.
Example Evaluation:
Expression: + 5 * 4 3
Equivalent Infix: 5 + (4 * 3)
Evaluation Process:
- Read 3 → push
- Read 4 → push
- Read * → Pop 4, 3 → Calculate 4*3=12 → push 12
- Read 5 → push
- Read + → Pop 5, 12 → Calculate 5+12=17
Result = 17
Advantages of Prefix Notation:
No need for parentheses — precedence is implicit.
Easier and faster for computers to evaluate.
Evaluation is straightforward using a stack.
Disadvantages:
Difficult for humans to read and understand compared to Infix notation.
Conversion is required when displaying results to end users.
Infix to Prefix Conversion Example:
Infix: (A + B) * C
Prefix: * + A B C
Summary:
In Prefix (Polish) Notation, operators appear before operands.
No brackets or parentheses are required.
Evaluation uses a stack and scanning is done from right to left.
If you want the algorithm or C program for Infix to Prefix conversion or evaluation, let me know!
Postfix Expression (Reverse Polish Notation):
Definition:
A Postfix Expression, also known as Reverse Polish Notation (RPN), is a mathematical notation in which the operator follows the operands. This eliminates the need for parentheses to define the order of operations.
Structure:
Operand1 Operand2 Operator
For example:
A B +
This is equivalent to A + B in Infix form.
Examples of Postfix Expressions:
- A B + → Equivalent to A + B
- A B C + * → Equivalent to A * (B + C)
- A B * C D / – → Equivalent to (A * B) – (C / D)
Evaluation of Postfix Expression:
Scan the expression from left to right.
When an operand is encountered, push it onto a stack.
When an operator is encountered, pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.
Example Evaluation:
Expression: 5 6 2 + *
Equivalent Infix: 5 * (6 + 2)
Evaluation Process:
- Read 5 → push
- Read 6 → push
- Read 2 → push
- Read + → Pop 2, 6 → Compute 6 + 2 = 8 → push 8
- Read * → Pop 8, 5 → Compute 5 * 8 = 40 → push 40
Final Result = 40
Advantages of Postfix Notation:
No parentheses required — operator precedence is inherently managed.
Simplifies evaluation algorithm — ideal for stack-based computation.
Efficient for computer processing — widely used in compilers and calculators.
Disadvantages:
Less intuitive for humans compared to Infix.
Requires conversion from Infix for user input.
Infix to Postfix Conversion Example:
Infix: (A + B) * C
Postfix: A B + C *
Summary:
Postfix (RPN) places the operator after operands.
Evaluation is straightforward and uses a stack data structure.
No need for brackets or parentheses.
Applications of Stack
A stack is a versatile and fundamental data structure extensively used in computer science and programming. Its LIFO (Last In, First Out) nature makes it highly suitable for solving various real-world and computational problems.
1. Expression Evaluation:
Postfix, Prefix, and Infix Expression Evaluation is efficiently performed using stacks.
Used in designing compilers and calculators.
2. Expression Conversion:
Conversion between different expression formats such as Infix to Prefix, Infix to Postfix, and vice versa is performed using stacks.
3. Function Call Management:
The stack manages function calls, returns, and recursion by maintaining the call stack.
Each recursive call pushes the current state onto the stack until the base case is reached.
- Syntax Parsing and Parenthesis Matching:
Used in parsing expressions and checking balanced parentheses in compilers, interpreters, and code editors.
5. Backtracking Algorithms:
Employed in backtracking problems like maze solving, puzzle solving (e.g., Sudoku), and the N-Queens problem.
Previous states are stored in a stack to retrace steps if required.
Undo/Redo Operations:
Implemented in text editors, word processors, and design software where the last action is stored to allow undoing or redoing operations.
7. Browser History Navigation:
Maintains the visited URLs in a stack to allow the user to go back (Back operation) or forward (Forward operation).
- Memory Management:
Used in runtime memory management where stack frames store local variables, function parameters, and return addresses.
Additional Applications:
Depth-First Search (DFS) in Graphs
String Reversal
Arithmetic expression compilation
Postfix calculators
Limitations of Stack
Despite its extensive utility, stacks have the following constraints:
1. Restricted Access:
Access is limited only to the top element.
Random access or direct retrieval of any element is not possible.
- Overflow Condition:
In static (array-based) stack, the stack may overflow if the maximum size is reached and there is no room for further elements.
3. Underflow Condition:
When trying to pop an element from an empty stack, an underflow error occurs.
4. Fixed Size Limitation (in Arrays):
In array implementation, the size of the stack is fixed at compile time and cannot be changed dynamically, which may lead to inefficient memory usage.
5. Memory Wastage:
In situations where the maximum defined stack size is not fully utilized, memory gets wasted, especially in array-based implementations.
6. Inappropriate for Certain Problems:
Problems that require random access, searching, or sorting are not suitable to be solved using stacks.