| TOPIC: Stack |
|
|
| DEFINITION: A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added to the stack will be the first one to be removed. This data structure is useful for solving problems that require reversing the order of elements or parsing expressions with nested structures. |
|
|
| TIME_COMPLEXITY: O(1) for push and pop operations, as they involve adding or removing elements from the top of the stack, making them constant time operations. |
|
|
| SPACE_COMPLEXITY: O(n), where n is the number of elements in the stack, as each element occupies a portion of memory. |
|
|
| USE_WHEN: Use a stack when you need to parse expressions with nested structures, such as evaluating postfix expressions or parsing XML/HTML tags, or when you need to implement recursive algorithms iteratively. |
|
|
| AVOID_WHEN: Avoid using a stack when you need to frequently access elements in the middle of the data structure, as this would require popping all the elements above it, and then pushing them back; in such cases, a different data structure like a list or array would be more suitable. |
|
|
| EXAMPLE: |
| Initial stack: [ ] |
| 1. Push 1: [1] |
| 2. Push 2: [1, 2] |
| 3. Push 3: [1, 2, 3] |
| 4. Pop: [1, 2] -> 3 |
| 5. Pop: [1] -> 2 |
| 6. Pop: [] -> 1 |
| Result: All elements have been popped in reverse order: 3, 2, 1 |
|
|
| REAL_WORLD_ANALOGY: A stack can be thought of as a pile of plates, where you add and remove plates from the top of the pile, following the LIFO principle. |
|
|
| SOURCE_NOTE: |
