Data Structures: Queues

Why is this important?

This workshop is important because:

Data structures are ways of organizing data that model real-world information movement. A queue is built to simulate any situation where people, tasks, or items get in a line and are addressed one by one in the order they arrived; items are addressed in a first in, first out basis. This is important because it's extremely common in the real world.

What are the objectives?

After this workshop, developers will be able to:

• Describe a queue by its methods and first in, first out (FIFO) behavior.
• Build queue methods using linked list or array methods.
• Compare and contrast stacks and queues and appropriately choose which is better for a given situation.

Where should we be now?

Before this workshop, developers should already be able to:

• Describe arrays, linked lists, and stacks.

Warmup

1. What is a stack, and what behaviors does it have?
2. How would you implement a stack with an array and with a linked list? How would you decide where the top of the stack would be? How would you push something to top of the stack? How would you pop something off the top of the stack?

Queues

You can read about them below or watch this video.

Queues as a data structure are a lot like queues as a physical structure. This makes more sense with British English, where queue means "a line" or "to line up". Think of an orderly line of people waiting to do something. We can remove an item from the front of the queue when its turn comes (by poping, also known as dequeueing), or add an item to the back of the queue when it joins the line (by pushing or enqueueing it). Again, while we may be able to "cut" in line in the real world, the queue data structure only allows us to add to the end of the stack or remove from the beginning. The enqueue and dequeue operations for a queue are both O(1) - constant time. Like with stacks, some implementations of queues also allow us to peek at the value of the first item without dequeueing it.

Queues are "First In, First Out" -- the first item enqueued will be the first to move all the way through the line and get dequeued.

Thinking with Queues

1. What are some real life structures and objects that a queue could simulate?

2. Draw a queue after each of the following operations:

• ENQUEUE 0
• DEQUEUE
• ENQUEUE 2
• ENQUEUE 4
• ENQUEUE 6
• DEQUEUE
• ENQUEUE 8

click for answer...

  * start        []
  * ENQUEUE 0    [0]
  * DEQUEUE      []
  * ENQUEUE 2    [2]
  * ENQUEUE 4    [2, 4]
  * ENQUEUE 6    [2, 4, 6]
  * DEQUEUE      [4, 6]
  * ENQUEUE 8    [4, 6, 8]

2. How would you implement a queue with an array? Where would you decide the front of the queue would be? How would you enqueue something to the end of the queue? How would you dequeue something from the front of the queue?

super stuck? click for an answer...

> The "front" could be the beginning of the array. To enqueue, you'd use JavaScript's handy `push` array method. To dequeue, you could use JavaScript's `shift` method, which removes and returns the first element from an array.

3. How would you implement a queue with a linked list? Where would you decide the front of the queue would be? How would you enqueue something to the end of the queue? How would you dequeue something from the front of the queue?

super stuck? click for an answer...

> The "front" could be the head of the linked list. The "back" could be the tail. You could enqueue by `append`ing to the tail. You could dequeue by deleting and returning the head node.

1. Stretch: How would you implement a queue with a fixed-size array?

Challenges

1. Design Decisions Would you use a stack or a queue to...

• ... print out a list of instructions that must be done in order?

• ... allow a user to undo changes to a document, one by one?

• ... let users create playlists and play back the songs?

• ... display only the 10 most recent messages a user posted, in the order they were posted?

2. Message Queues

Queues are often used to create "buffers" that temporarily store data from one part of a program until another part of a program can process the data. This is common with asynchronous data transfer, or mismatches between how often data is sent and how often it can be processed.

Think of a scenario where restaurant diners order food faster than the chefs can cook it.

Describe how you would use a queue help the chef keep track of meals to make. What should the chef do when the queue is empty?

3. Stretch: Try out this queue challenge to calculate the total price of a purchase.