Week 5: Stacks and Queues
Outcomes
You should be able to:
- Explain the main operators of a stack (understand and discuss the ADT description).
- push()
- peek()
- size()
- is_empty()
- pop()
- Explain the pseudocode for the operators of a stack
- Identify the Big-Oh notation for the operators of a stack
- Explain how a Python list based implementation of a stack fulfills the operators (ADT) of the stack
- Provide an example of where a stack could be used in programming
- Given a real world example, indicate if a stack is an appropriate data structure to use with the problem. [Covered next week]
- Explain the main operators of a queue (understand and discuss the ADT description).
- enqueue()
- dequeue()
- size()
- is_empty()
- Explain the pseudocode for the operators of a queue
- Identify the Big-Oh notation for the operators of a queue
- Explain how a Python list based implementation of a queue fulfills the operators (ADT) of the stack
- Provide an example of where a queue could be used in programming
- Given a real world example, indicate if a queue is an appropriate data structure to use with the problem.
Activities - Stack
- Kicking off the next couple of weeks
- Begin by understanding the concept of Linear Data Structures
- Read Section 3.1 through Section 3.2
- While both of these pages are short, they contain some important details.
- Continue by exploring the first linear data structure we will study: the Stack
- Let's make sure that these pieces make sense before continuing
- Watch - What is a Stack [Video, 4 minutes]
- Watch - Understanding the Stack ADT (Understanding the interface) [Video, 9 minutes]
- Watch - Examining the Stack Code (Understanding the implementation) [Video, 10 minutes]
- Watch - Calculating the Big-Oh of a Stack [Video, 8 minutes]
- Note, there are some significant complications trying to use the timeit module to PROVE that my claim in this video is true (that all operators are O(1))
- If you can't see this claim and don't believe it, reach out to me and I will walk you through the timeit code one-on-one.
- Looking at some code based uses of a Stack
- [Optional] Consider Section Section 3.9
- I consider this section to be somewhat boring, not at all motivating, and (to a certain extent) beyond the needs of this course.
- It discusses a classic but very outdated set of algorithms the computer scientists used to use.
- You are welcome to read it to see what it says. But don't worry if you aren't interested and/or don't understand it.
- My non-explanation of 3.9 [Video, 4 minutes]
Activities - Queue
- Let's mix reading and videos
- Read Section 3.13 and Section 3.14
- Again, I do not expect you to be an expert on these examples.
- I only ask you to read about them so you can see some problems where Queues might be used
Additional Resources
- You may have noticed this on the table of contents page for your textbook. Professor Gerry Jenkins is a retired professor from Long Beach City College who made a bunch of videos to correspond with the readings in your textbook. I have NOT viewed all of them. But, I know how helpful it can be to have a wide variety of study resources.