How do stacks facilitate backtracking in algorithms?
By optimizing the search space for the algorithm.
By storing the optimal solution found so far.
By providing a mechanism for parallel processing.
By maintaining a record of visited states and enabling the algorithm to revert to previous states.
Imagine a stack is used to track function calls in a recursive program. What happens to the stack when a function returns?
The corresponding function call is pushed onto the stack.
The stack remains unchanged.
The entire stack is cleared.
The corresponding function call is popped from the stack.
What is the purpose of the 'top' pointer in an array-based stack implementation?
To store the maximum size of the stack
To track the index of the next available position for insertion
To store the value of the top element in the stack
To point to the bottom element of the stack
What is the primary difference between 'pop' and 'peek' operations on a stack?
'Pop' and 'peek' are interchangeable terms for the same operation.
'Pop' removes the top element, while 'peek' only retrieves its value without removing it.
'Pop' is used for stacks, while 'peek' is used for queues.
'Pop' retrieves the top element's value, while 'peek' removes it from the stack.
What is the time complexity of the 'peek' operation in a well-implemented stack?
O(n)
O(n log n)
O(1)
O(log n)
In maze-solving algorithms, how does the use of a stack differ between depth-first search (DFS) and breadth-first search (BFS)?
Both DFS and BFS use stacks identically; the difference lies in how they mark visited nodes.
DFS uses a stack to explore as deeply as possible before backtracking, while BFS uses a queue to explore all neighbors at a given level.
BFS uses a stack to prioritize unexplored paths, while DFS uses a queue to systematically explore all directions.
DFS uses a stack only if the maze is solvable, while BFS always uses a queue.
What key advantage does a Deque (Double-ended Queue) offer over a Stack?
Deque is more memory-efficient than a Stack.
Deque allows insertions and deletions at both ends.
Deque allows deletions only at one end.
Deque allows insertions only at one end.
Which real-life scenario most accurately reflects the LIFO (Last In First Out) principle of a stack data structure?
A stack of plates on a table.
A list of tasks sorted by priority.
A queue of people waiting for a bus.
A tree of files and folders on a computer.
What is a potential drawback of using a linked list-based stack compared to an array-based stack?
Higher memory usage due to the overhead of storing pointers
Limited stack size
Inability to handle dynamic resizing
Increased time complexity for push and pop operations
Consider the scenario of undoing actions in a text editor. Which data structure would be most suitable for implementing an 'undo' feature?
Linked List
Binary Tree
Queue
Stack