Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm teaching CS2 (Java and data structures), and am having some difficulty coming up with good examples to use when teaching queues. The two major applications I use them for are multithreaded message passing (but MT programming is out of scope for the course), and BFS-style algorithms (and I won't be covering graphs until later in the term).

I also want to avoid contrived examples. Most things that I think of, if I were actually going to solve them in a single-threaded fashion I would just use a list rather than a queue. I tend to only use queues when processing and discovery are interleaved (e.g. search), or in other special cases like length-limited buffers (e.g. maintaining last N items). To the extent practical, I am trying to teach my students good ways to actually do things in real programs, not just toys to show off a feature.

Any suggestions of good, simple algorithms or applications of queues that I can use as examples but that require a minimum of other prior knowledge?

share|improve this question
    
+1, but I'd refrain from creating the tag 'queue', considering it contains only yours question. I'd have used 'data-structures'. –  K.Steff Jun 22 '12 at 15:46
    
@K.Steff, you can have both :-) Note that any new tag is associated with only a single question at the beginning. –  Péter Török Jun 22 '12 at 15:49
1  
It is natural to cover Queues when you cover BFS. Why not save Queues until then? You don't have to cover Queues with linked lists and array lists just because they also have a linear representation. –  kevin cline Jun 22 '12 at 15:52
    
@PéterTörök I realize that all tags start empty, but a 'queue' search yields 313 questions, and no other has created the 'queue' tag. This is just IMO, anyway –  K.Steff Jun 22 '12 at 15:54
    
A recurring theme in the answers seems to be simulations of real-world queues. My thinking so far has been that I'd prefer to use examples of things where I would use a queue to solve a problem that actually arises in programming, and that a lot of the physical-world examples shine best in concurrent environments. However, given the repetition of this theme, it could well be that I am not on a useful line of thinking. Keep the suggestions coming! And thanks all for your great help. –  Michael Ekstrand Jun 22 '12 at 16:00

13 Answers 13

Any scheduling algorithm almost always involves a queue.

This can range from a simple first come first served queue to buffer request for a single consumer.

To a complex job scheduling queue where "tasks" can have priorities and "workers" have different capabilities.

A good use case to play around with could be "You have a central print server with four printers attached two capable of color, one capable of printing double sided and one capable of printing on larger paper. Users can pay extra for a rush job, or, less if they don't mind waiting longer. You can incur penalties if you deliver late so you want as much throughput as possible."

share|improve this answer

In teaching data structures, I usually use the application of the bank queue simulation where customers wait in a queue and there are a number of service windows.

The problem is to simulate the process in order to find out statistics of the following: customers waiting time in the queue (max, min, average), and numbers of customers waiting in the queue. I use a predefined frequency of arriving new customer every minute of a day and an average service time of a customer on the service window with values from the random number generator.

The result will be recommendations for the optimal number of service windows and the optimal number of chairs in the waiting hall that would guarantee customer satisfaction. Very interesting application to students.

share|improve this answer

Manufacturing lines are full of queues. Think of a line of empty bottles heading for a filling machine. First-in-first-out is a natural way to apply a process sequentially to many objects. Queues are also used to decouple one process from another: the filling machine doesn't have to stop immediately if there's a short-term problem with the labeling machine.

Queues are used in software in about the same ways. The output of one process can be queued for input to another process. This is true whether you're talking about inter-process communication, inter-thread communication, or simply breaking a complicated process into parts that might all be handled by the same thread.

In operating systems, queues are often used to process inputs in order. The file system might read blocks from a storage device and add them to a queue, for example. Or interrupts that handle things like key presses and mouse movements create events that are added to an event queue so that you don't get "uqeeu" instead of "queue" when you're typing.

For a simple student assignment, I think any task that accepts some number of inputs and then processes them would work. For example, you could have them write a simple postfix expression evaluator. It'd have three parts:

  • read an input, add it to the input queue, and repeat until there are no more inputs

  • get an item from the queue

    • if the item is a number, push it onto the argument stack
    • if the item is an operator, pop the necessary arguments and evaluate
    • add the result to the output queue
    • repeat until the stack is empty
  • read an item from the output queue, print it, and repeat until the output queue is empty

share|improve this answer

The obvious Real-World examples would be things like checkout lines, and such, but since you're looking for an example rooted strictly in computing, might I suggest job scheduling queues?

I don't know how many of your students have taken an Operating Systems class, but it's a good bet that all of them have used the Task Manager to check their processes at some point or other. You could introduce a simplified example of a scheduling queue, and assign them some homework to write a program that generates (or accepts) a "task" of a given size, and processes them in FIFO order when they "start" it.

It's a fairly easy concept to understand, demonstrates the idea that queue operates on its contents in the order that it accepts them, and gives them a (very rudimentary and simplified) introduction to CPU scheduling. Just my two bits.

You might bring up their application in multithreading, but unless the students have had some experience writing threaded programs already I wouldn't assign work to them that might get two frustrating. I remember I had trouble learning data structures (especially in Java, having not done C++ and not learned a thing about pointers) in my second year of college, so a simple but practical example directly related to computing is probably best.

share|improve this answer

I used to be a telecom programmer so this comes to mind:

A Customer Service hotline. A call comes in, there are not enough operators to handle the call and it is placed in a queue. The next call comes in and it is also placed in the queue. Then when the next operator becomes available the first call that entered the queue gets assigned to the available operator.

share|improve this answer

Some examples I can think of:

  • Calculator - can introduce prefix and postfix at the same time
  • Instructions to tie shoes. Can't complete the next operation until you have done the last one
  • Buffers - Maybe a telephone buffer used to store numbers that the user has entered but have not made the tone sound yet
  • Digestion
share|improve this answer

I like to use games as an example because it is generally a little more exciting than file IO or whatever else you can come up with.

So when you want to issue several commands in a row to a unit in a strategy game (eg. Have a Zergling to scout 4 corners of a base in order, then suicide into the center of the base, a queue would be a good choice.)

Or maybe you have an application that can only process 30 frames per second, but you might get 4 or 5 inputs between frames. If you have a change weapon input and a shoot input, you want to make sure those get handled in the order they were received otherwise you may grenade when you wanted to knife. And if you grenade when you want to knife, you are gonna have a bad time. (put that on the ski instructor meme and throw it in your slides) :)

A server handling requests is another good one.

A CNC machine taking input. The machine can only go so fast, so it needs to queue up input.

share|improve this answer

Real world:

  • Any time that people line up: cashier at the grocery store, in the restaurant waiting for a table (you can work in those beepers that they sometimes give out into the analogy), etc. It's helpful when you notice that in the UK they often call these queues instead of lines (common in NA)
  • Reading book series', author.publish => queue.push and student.read => queue.pop

Non-Real World:

  • Processing any submitted data in a single-threaded environment where the processing takes longer than the submitting (checkout operations for online stores for eg.)
  • Any FIFO collection that can be iterated over can use queues and use while(queue.peek) instead of an iterator.
share|improve this answer

A perfect example of a queue would be a bank processing transactions against an account. Usually you'll see a list of "pending" transactions at the end of the day. When the accounting is done those transactions are applied to the account. You could even get into the area of priority queues with this. It seems most banks put priority on debits when processing nightly transactions so they can ding you with over draft fees before they apply any pending credits.

The transactions are inserted into the queue by order of time executed and dequeued and applied to the account by the accounting process.

share|improve this answer

I thought about using Amazon as an example, somewhere in their massive system there must be a queue of orders that needs to be handled. which could be handled by a simple enqueue and dequeue. the system would enqueue an order in the system every time a customer bought a book, and a storage house person would then dequeue it in order to pick it and post it.

It would then be easy to start talking about priority queues, by introducing prime customers, which might jump the queue, you could introduce priority queues.

What textbook are you using?

share|improve this answer
    
Carrano — Data Structures and Abstraction with Java. –  Michael Ekstrand Jun 22 '12 at 16:18

When I was learning queues, my professor always used the example of a store. There are 1 or more registers open at any given time, and the Customers enter one queue or another and move through that queue to purchase all of their items.

We actually had to implement a simple program that could move Customers through a RegisterQueue, so if you are actually looking for a program you can give the students this example is simple and straightforward, but also something that every student has seen in real life and so it may help them understand the concept better.

share|improve this answer
    
As I said, this example is both very intuitive and also almost too often used ;) –  mcwise Jun 22 '12 at 15:54
1  
You can add complexity by having a priority queue for customers with perks (Aero plan). –  sixtyfootersdude Jun 22 '12 at 20:26
1  
IMO, the easiest examples are the ones we encounter in life. A 'line' example is a great representation of a queue and should help your students learn. In fact, when I think of queue's and how their operations are defined, I often think of the 'line' example to help me visual it better. –  Nicholas Jun 22 '12 at 20:30
    
This is also a great opportunity to briefly touch on queuing theory: why a single line serving multiple registers is better than a line per register. Let them build a simulation and play with it. The Engineer Guy has a great, simple explanation: engineerguy.com/videos/video-lines.htm –  jpeacock Jun 22 '12 at 23:34

When I learned queues my teacher introduced them to me using a line-up for cars at a police control. There was a queue holding the cars ("waiting-queue") and the police man would always control the next car in the queue and either send it to his colleague for further inspections or let the car pass.

An example very often used is the queue in the super-market...

Why don't you ask your students to give some examples themselves?

share|improve this answer
    
+1 for supermarket example. You mentioned it while I was writing my answer up! –  Sum Deos Jun 22 '12 at 15:53

One example which comes to my mind is a hamburger processing line in e.g. McDonalds. Ther are several kinds of different burgers, each may be produced by several different workers and each has its own queue. From there, after a while the ready burgers are taken, in FIFO order, by one of the cashiers who ordered that kind of a burger.

So there are multiple producers and consumers, and each queue is bounded.

share|improve this answer
    
I recall classmates back in college comparing the different styles of fast food register arrangements to processor designs. One queue handled by multiple registers? Each register with its own queue? Multiple workers on the same line - super scalar processing. It was amusing. –  MichaelT Jun 22 '12 at 20:00

protected by gnat Apr 22 at 9:14

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.