Stacks and Search Survey
Stacks
A stack is a sequence with Last-In-First-Out (LIFO) discipline. The item next to be removed is the one most recently added.
| Operation | Description |
|---|---|
empty | The empty stack |
null s | Test whether s is empty |
top s | Return the element at the top |
pop s | Discard the top element |
push s x | Add x to the top |
Lists as stacks
OCaml lists naturally implement stacks:
| Stack operation | List equivalent |
|---|---|
push s x | x :: s |
top s | List.hd s |
pop s | List.tl s |
Both :: and hd operate on the head in O(1) time.
Imperative stacks
In conventional languages, a stack is typically implemented with an array and a pointer (stack pointer). The pointer tracks how many elements are in use. Most language processors use an internal stack to manage recursive function calls.
Search strategy survey
The choice of data structure determines the search strategy:
| Search strategy | Data structure | Discipline |
|---|---|---|
| Depth-first | Stack | LIFO |
| Breadth-first | Queue | FIFO |
| Best-first | Priority queue | Ordered by heuristic |
| Iterative deepening | Stack (DFS repeated) | LIFO with depth bound |
Best-first search
Store pending nodes in a priority queue ordered by a heuristic ranking function. The function estimates the distance from each node to a solution. If the estimate is good, the solution is located swiftly.
Priority queues can be implemented with sorted lists (slow), binary search trees (O(log n) average), or more sophisticated structures like heaps.
Summary
- DFS: stack-based, space-efficient, incomplete for infinite trees.
- BFS: queue-based, finds shortest path, space-hungry.
- Iterative deepening: DFS repeated with increasing bounds, combines space efficiency of DFS with completeness of BFS.
- Best-first: priority queue, uses domain knowledge for efficiency.