Sample Question:

sdfsdfsf

JSR Notes:

Features of the Queue ADT:

Characteristics

- Queues are a particular implementation of lists that operate in a FIFO manner (First in, First Out, or put another way, first-come-first-serve).

- As lists, queues are (like stacks) made up of a "chain" of self-referencing nodes; i.e. nodes of the same type that point to each other.

- Items can be added, or "enqueued" onto one end of the list (usually the end furthest from the head).

- Items can be taken from, or "dequeued" from the OTHER END of the list (so usually the the front, or "head" of the list), and so they operate in a FIFO basis (First In, First Out).

- Note that the processing, then, of queues is at both ends; adding to the one end, and taking from the other.

- It is important that checks can be made to see if the queue is empty, thus preventing the error of trying to access something that is not there.

Simple Summary Diagram

 

 

Applications

General:

- Queues function in much the same way that lines or queues function in most of the civilized world, in that the first one in the line is the first one served; there's no butting into the line.

Analogies:

- Other than queues of people lining up for food, or tickets at a movie theatre, a good common example is airplanes queuing up to take off from an airport. The first one to taxi out to the runway is the first allowed to take off. Once that plane takes off, the next one in line is the one that takes off. New planes line up at the back of the list/queue.

Computing:

- 1. In terms of the functioning of a computer, queues will be used whenever tasks are non-urgent, and at the same level of priority as the other tasks waiting for the CPU to execute them. (A Topic 6 example is CPU polling.)

- 2. And in terms of programs we will make, whenever we have a list of things to do or deal with, and they also are all of equivalent importance and priority, a queue is the most equitable way to deal with them one by one.

- 3. A print queue or a queue for any other network service such as this. It only makes sense that the print jobs etc. are fairly handled in a first come-first serve basis.

- 4. Computer modeling of physical queues (eg. supermarket checkouts). Taking the example mentioned above in the Teaching Note, a simulation to test efficiencies of various arrangements of supermarket checkouts would have to function the way that they do in reality, which is the first one in line is always the next person dealt with.

 

- Note that a queue can function in a linear way, or a circular way as well:

As a general example, how about passing a bowl of chips around a party - as people make their way to the table, it's first-come-first serve, but once everyone has had one handful (....certainly not a pandemic activity!) the bowl is passed back around the same way a second time - passed on from the last person back to the first person again.

And as a computer example, think of the time-slices of various polling requests being a certain time only. So having "gone around" to all the polled request, the CPU goes back to the beginning of the queue and loops through the requests again (and again, as needed).