Lesson 4.1: Stacks
Class Meeting:
| Section | Slides | Annotated Slides | Video |
| 12–1PM | 4.1-stack-203-1221.pdf Download 4.1-stack-203-1221.pdf | PDF Download PDF |
On Zoom Cloud Recordings |
| 1–2PM | 4.1-stacks-1pm.pdf Download 4.1-stacks-1pm.pdf | 4.1-stacks-1pm-annotated.pdf Download 4.1-stacks-1pm-annotated.pdf |
On Zoom Cloud Recordings |
| 4–5PM | 4.1-stacks-4pm.pdf Download 4.1-stacks-4pm.pdf | 4.1-stacks-4pm-annotated.pdf Download 4.1-stacks-4pm-annotated.pdf |
On Zoom Cloud Recordings |
Readings:
- Carrano & Henry: Chapter 6
- Carrano & Henry: Chapter 1.1-1.4
Summary:
This is our first special purpose abstract data type! We examine two reasonable implementations: singly linked lists, and arrays. The use of linked lists is straightforward, but a stack implementation using arrays requires discussion of array resizing. We examine two different options for array resizing, and argue that the strategy of doubling the size of the array whenever it fills is efficient.
Learning Outcomes:
- Examine several simple applications of stacks, including Pez dispensers.
- Implement the stack ADT with a singly linked lists.
- Implement the stack ADT with an array.
- Analyze an array-resizing strategy which increases the size of the array by a constant amount every time the array fills.
- Analyze an array-resizing strategy which doubles the size of the array every time the array fills.