1. **Stack and Queue Definitions:**
- **Stack:** This is a Last-In-First-Out (LIFO) data structure. A prime example is the undo
operation in text editors.
- **Queue:** This operates as a First-In-First-Out (FIFO) data structure. A common example is
the print queue in operating systems.
2. **Balanced Parentheses:**
- To effectively determine if parentheses are balanced, utilize a stack. Push opening parentheses
onto the stack, and pop them off upon encountering closing parentheses. If the stack is empty at
the end, it is confirmed that the parentheses are balanced.
**Non-Linear Data Structures (Trees, Graphs, Heaps):**
3. **Binary Search Tree (BST) Properties:**
- In a BST, the left child is always less than the parent, and the right child is always greater than
the parent.
- The structure of the BST directly influences search efficiency: balanced trees achieve O(log n)
performance, while unbalanced trees drop to O(n).
4. **Depth-First Search (DFS) vs. Breadth-First Search (BFS):**
- **DFS:** This approach explores as deep as possible before backtracking, employing a stack
(usually implicitly via recursion). It is the preferred method for verifying path existence.
- **BFS:** This method explores level-by-level using a queue, making it the superior choice for
finding the shortest path in unweighted graphs.
5. **Heap:**
- A heap is a tree-based data structure that strictly satisfies the heap property.
- In a min-heap, the parent is always less than or equal to its children. In a max-heap, the parent
is always greater than or equal to its children.
- **Stack:** This is a Last-In-First-Out (LIFO) data structure. A prime example is the undo
operation in text editors.
- **Queue:** This operates as a First-In-First-Out (FIFO) data structure. A common example is
the print queue in operating systems.
2. **Balanced Parentheses:**
- To effectively determine if parentheses are balanced, utilize a stack. Push opening parentheses
onto the stack, and pop them off upon encountering closing parentheses. If the stack is empty at
the end, it is confirmed that the parentheses are balanced.
**Non-Linear Data Structures (Trees, Graphs, Heaps):**
3. **Binary Search Tree (BST) Properties:**
- In a BST, the left child is always less than the parent, and the right child is always greater than
the parent.
- The structure of the BST directly influences search efficiency: balanced trees achieve O(log n)
performance, while unbalanced trees drop to O(n).
4. **Depth-First Search (DFS) vs. Breadth-First Search (BFS):**
- **DFS:** This approach explores as deep as possible before backtracking, employing a stack
(usually implicitly via recursion). It is the preferred method for verifying path existence.
- **BFS:** This method explores level-by-level using a queue, making it the superior choice for
finding the shortest path in unweighted graphs.
5. **Heap:**
- A heap is a tree-based data structure that strictly satisfies the heap property.
- In a min-heap, the parent is always less than or equal to its children. In a max-heap, the parent
is always greater than or equal to its children.
