Stacks are versatile and used in many areas of computer science and real-world applications. Here are some common applications:
1. Expression Evaluation and Conversion
- Infix to Postfix/Prefix Conversion: Stacks are used to convert infix expressions (e.g., A + B * C) to postfix (e.g., ABC*+) or prefix (e.g., +A*BC).
- Expression Evaluation: Postfix or prefix expressions are evaluated using stacks.
2. Function Call Management (Recursion)
- The call stack in programming languages stores information about function calls.
- It tracks return addresses, local variables, and parameters for recursive or nested function calls.
3. Undo and Redo Operations
- Text editors and applications use stacks to manage undo (reverting to the previous state) and redo (reapplying an undone action) operations.
4. Browser History
- A browser’s back and forward navigation system uses two stacks:
- One stack for back history.
- Another stack for forward history.
5. Parsing
- Stacks are used in parsing operations, such as:
- Syntax parsing in compilers to check matching parentheses or braces.
- Processing XML or HTML tags to ensure proper nesting.
6. Tower of Hanoi
- Stacks are used to simulate or solve the Tower of Hanoi puzzle efficiently.
7. Balancing Symbols
- Stacks are employed to check if symbols in a string (e.g., {}, [], ()) are balanced correctly, like in mathematical expressions or code.
8. Depth-First Search (DFS)
- DFS in graph traversal uses stacks to explore nodes and backtrack when needed.
9. Memory Management
- Operating systems use stacks for memory allocation in processes, particularly in managing stack frames for functions.
10. Backtracking Algorithms
- Stacks are used in backtracking problems, such as:
- Solving mazes.
- N-Queens problem.
- Sudoku solving.
Multiple Stacks
Sometimes, applications require maintaining multiple stacks within the same memory space, such as for managing multiple processes or tasks. Instead of creating separate arrays for each stack, a single array can be divided dynamically or statically to store multiple stacks.
Approaches for Multiple Stacks
- Fixed Partitioning:
- Divide the array into fixed sections, one for each stack.
- Requires prior knowledge of the maximum size each stack might need.
- Risk: Some stacks may overflow while others remain underutilized.
- Dynamic Partitioning:
- Allow stacks to grow dynamically by overlapping their boundaries.
- Use additional metadata to manage free space and stack boundaries.
C Implementation of Two Stacks
Two stacks can share the same array. One stack grows from the left, and the other grows from the right.
Code
c
Copy code
#include <stdio.h>
#define MAX 10
typedef struct {
int arr[MAX];
int top1;
int top2;
} TwoStacks;
// Initialize two stacks
void initStacks(TwoStacks *stacks) {
stacks->top1 = -1;
stacks->top2 = MAX;
}
// Push to Stack 1
void push1(TwoStacks *stacks, int value) {
if (stacks->top1 < stacks->top2 – 1) {
stacks->arr[++(stacks->top1)] = value;
printf(“Pushed to Stack 1: %d\n”, value);
} else {
printf(“Stack Overflow\n”);
}
}
// Push to Stack 2
void push2(TwoStacks *stacks, int value) {
if (stacks->top1 < stacks->top2 – 1) {
stacks->arr[–(stacks->top2)] = value;
printf(“Pushed to Stack 2: %d\n”, value);
} else {
printf(“Stack Overflow\n”);
}
}
// Pop from Stack 1
int pop1(TwoStacks *stacks) {
if (stacks->top1 >= 0) {
return stacks->arr[(stacks->top1)–];
} else {
printf(“Stack 1 Underflow\n”);
return -1;
}
}
// Pop from Stack 2
int pop2(TwoStacks *stacks) {
if (stacks->top2 < MAX) {
return stacks->arr[(stacks->top2)++];
} else {
printf(“Stack 2 Underflow\n”);
return -1;
}
}
int main() {
TwoStacks stacks;
initStacks(&stacks);
push1(&stacks, 10);
push1(&stacks, 20);
push2(&stacks, 30);
push2(&stacks, 40);
printf(“Popped from Stack 1: %d\n”, pop1(&stacks));
printf(“Popped from Stack 2: %d\n”, pop2(&stacks));
return 0;
}
Output
plaintext
Copy code
Pushed to Stack 1: 10
Pushed to Stack 1: 20
Pushed to Stack 2: 30
Pushed to Stack 2: 40
Popped from Stack 1: 20
Popped from Stack 2: 40
Applications of Multiple Stacks
- Process Management:
- Maintaining separate stacks for different processes in operating systems.
- Dual Navigation:
- Implementing browser history for back and forward navigation.
- Task Scheduling:
- Managing different priority queues using separate stacks.
- Multi-threading:
- Storing local variables for threads in separate stack segments.
Conclusion
- Stacks are crucial for managing data in various applications like expression evaluation, recursion, and parsing.
- Multiple stacks optimize memory usage and are helpful in scenarios requiring parallel or independent stack management.