What are some good, simple examples for queues? [closed]

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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?

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 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."