What are some good problems which can be solved with a queue?

Question

I am trying to introduce the idea of stacks and queues in a course on data structures.

For stacks, my idea was to show some interesting examples of problems, like evaluating an expression in RPN, or checking whether a bracket sequence is well bracketed.

What would be a good example of a few problems where queues are the canonical objects to use?

One example I could think of is Breadth First Search. But what else? Ideally, I would like some simpler problems which can be presented with even lesser background.

Answer 1

One example I've used for students in the past is a shared printer.

If I have five people using a printer all at once I will have a problem if two of the five attempt to print at the same time. What can I do? I can put up a sign on the printer--"Only One User At A Time Please" and hope everyone sees and follows it. Of course then the users need to coordinate their use.

I can (software) lock it so that only one person can print at any time. But when the second user tries to print he or she is blocked until the printer is free. And the third user is blocked longer etc.

Or I can set up a queue. As each user prints the print job goes to the queue. The printer looks at the queue for jobs to print and as it prints them it removes them from the queue. No one is blocked and the printer doesn't fail because two people try to print at the exact same moment.

Answer 2

The Shunting Yard Algorithm

To go along with your example of evaluating RPN, you can convert infix notation into RPN with the Shunting Yard algorithm It uses both a stack and a queue, although the queue is really only used as an FIFO output; the algorithm never reads from it. This algorithm has the benefit of being practical, and its use is immediately apparent. Plus, combined with an RPN evaluator, the students can create something they could actually use.

Operating system scheduling

Queues are an important part of operating system scheduling, and are the exclusive data structure used in round-robin scheduling. A toy scheduler for cooperative tasks has a simple enough structure that it is almost trivial to implement, and gives an insight to what multi-threading looks like on a single core machine. Talking about scheduling can also provide a lead in into other topics including asynchronous communication and priority queues.

There is an added benefit of this topic: if you are a fan of talking about CS in a historical context, round robin scheduling and queues gives you an excuse to talk about the the moon landings.

Answer 3

Ideally, I would like some simpler problems which can be presented with even lesser background.

Fortunately, queues are used often in everyday scenarios. If you're just trying to teach the general First In First Out (FIFO) concept of a queue (and not necessarily how it solves more complex computing problems), then there are a lot of opportunities to show people "getting in line" / "queueing" such as:

• Buying tickets to a concert (e.g. Ticketmaster)
• Grading students' work in a first-come-first-serve basis
• Processing online orders for Packaging/Shipping (e.g. e-commerce warehouse)

If you want to tie the example back to software, you can discuss any of these as a software application (i.e. online ticket sales, gradebook app, warehouse management app). Some of these examples can also segue into more advanced topics in queueing, such as priority queues or using multiple queues.

Answer 4

• Nearly everything in Unix Gnu/Linux, e.g. ls | less. Queues make it possible to do interprocess communication without semaphores, locks, mutexes, and all that nasty stuff. (If you can't keep it constant, then a queue is the next best thing)
• An ethernet switch: it need to read the first 6 bytes, then route the whole lot to the desired port. To do this is delays the message through a queue, while reading the first 6 bytes, and deciding where to send it.
• Interfacing to (slow/fast) hardware. There will be a mismatch between the speed of hardware and the routines that service them. Therefore but incoming and outgoing data into a queue. e.g. keystrokes are held in a queue until a process in ready to process them.
• A website processes requests in the order received.

Answer 5

One classic type of problem is handling communications - especially asynchronous communications from multiple sources. That may be a bit much in an elementary course if you want to mostly avoid race conditions.

But a problem with a single producer and a single consumer can also be informative, though it doesn't completely avoid race conditions. Have some simple process produce some data (an object, say) and queue it. Have another process dequeue objects when available and handle them. The consumer can busy-wait on the queue in simple cases.

It is most informative when the producer is sometimes a bit faster than the consumer so that the queue normally has something to be processed. But other problems occur if it is consistently faster, of course.

You can also use such things as an introduction to the ideas around race conditions, dropped data, etc, since anomalies will eventually occur without some form of synchronization.

Such a simple setup that introduces a much deeper set of ideas is called a Toy Box in the Pedagogical Patterns community. The application isn't truly realistic, but gets students thinking about deeper issues that will be covered later in their education.

Answer 6

Turn-based games where players can drop out (either voluntarily or by losing) before the game is over. At a high level, you have a queue of players. You pop the player from the head of the queue, process their turn, and then push them back to the end of the queue.

Queues also have applications in simultaneous-move games, as a way of ensuring that each player gets their fair share of processing, but that's more subtle.

Answer 7

You can do level-order traversal of a binary tree using a queue.

Answer 8

Here's a real-life example from a previous job: the Federal Aviation Administration uses queueing models for a ton of their algorithms, from scheduling flight departures to rerouting flights because of severe weather.

Googling "FAA queueing models" will return a ton of research papers that are pretty interesting, although probably too advanced for an introductory class. You could simplify the exercise into a simulation of an airport.

Another real-life example that I think about often are supermarket lines. Maybe make an assignment out of this question: what's the most efficient way to get X people through Y checkout lanes?

Answer 9

The two killer applications that immediate come to mind are event handlers and discrete event simulation. The use of queues in event handling is a little more complicated, as the process also involves interrupts (hardware and/or software) and events can be deleted from the queue before they are ever handled (for example, GUI events that become redundant when the second one happens before the first is handled), but the core mechanism is a queue. For example,

StackExchange: How does an event listener work?

Discrete event simulation shows up in many places throughout the natural sciences, of course. I'm procrastinating from writing right now and need to get back to it, so here's the Wikipedia entry and a very nice tutorial lesson.