Queues
Projected Time
About 60-90 minutes
- Lesson Slides: 15 min
- Medium Article: 15 min
- Video Materials: 10 min
- Group Discussion: 10 min
- Independent Practice: 30 min
Prerequisites
Motivation
Queues are widely used both in programming and in real life. In programming: if you have an array of tasks to
execute and not enough time to do them all as they come in, you’ll need some way to both track the tasks and execute
them in the order they arrived. In real life: in line for a coffee, or on hold for customer support – there are many
everyday scenarios that are real-life implementations of queues.
Application of queue in computer science:
- When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
- When data is transferred asynchronously (data not necessarily received at same rate as sent) between two
processes.
Examples include IO Buffers, pipes, file IO, etc. (geeksforgeeks)
Objectives
Participants will be able to:
- Understand when to use a queue
- Be familiar with common methods
- Implement a queue
- Find and use a queue library
- Discern performance tradeoffs for different implementations of a queue
Specific Things to Learn
- Properties of a queue
- Common use cases for queues
- Review of common implementation(s)
Materials
Lesson
- Read through lesson slides Queue.
- Watch the video and read the article in the materials section.
Common Mistakes / Misconceptions
- There may be an implementation that is very simple, but untenable for larger queues.
Guided Practice
Discuss as a group how a queue differs from other data structures already reviewed. Some suggested questions to
consider:
- What are the methods a queue must have?
- What can be tracked in a queue?
- When would a queue be used?
- What other data structures are used to make a queue?
Independent Practice
Implement a queue in JavaScript with a partner, keeping in mind all methods and helper methods that define a queue.
Consider performance – what happens as you call specific methods you’ve defined?
Challenge
Search online with your partner for a way to implement a queue other than the one you just tried. Is this second
implementation better? Why or why not?
Supplemental Materials
Check for Understanding
Share what you’ve learned and your implementation with another person.