Java MCQ: Which of the following applications may use a Stack?
Answer:
Explanation:
All of the listed applications—recursion, parsing, and browser history—use stacks as an underlying data structure to manage their operations. The stack’s Last-In-First-Out (LIFO) behavior is particularly useful in these scenarios, enabling efficient management of data where the most recent item needs to be accessed or removed first.
In recursion, each function call is pushed onto the call stack, and when the function completes, it is popped off the stack, allowing the program to return to the previous state. This is essential for managing the execution flow in recursive algorithms:
public int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1); // Each call is pushed onto the stack
}
}
In parsing, particularly in compilers and interpreters, stacks are used to manage the syntax structure of programming languages. For instance, stacks are employed in the parsing of expressions and matching of parentheses:
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
}
// Other conditions for '}' and ']'
}
return stack.isEmpty();
}
Browser history uses a stack to manage the user’s navigation. When a user visits a new page, the current page is pushed onto the history stack, allowing the user to return to it by popping the stack:
Stack<String> history = new Stack<>();
history.push("www.example.com");
history.push("www.example2.com");
history.pop(); // Goes back to "www.example.com"
These examples demonstrate how the stack’s LIFO principle is applied in various real-world scenarios, making it an indispensable data structure in computer science.