queue

A queue is a one-dimensional data structure to which new members or elements are generally added (pushed or enqueued) at the end and removed (popped or dequeued) from the start. (Compare this to a stack).

Obviously a new pushed element gets an index number one higher than the most recently pushed element. It depends on the actual implementation whether elements are re-indexed when the start element is popped. To give two real-world examples:

a. When people queue up at the DMV by getting a number from the Take-A-Number dispenser, they give up their number ticket when they get up to the booth, but the number of the tickets of the people behind them in the queue are not changed to reflect their decreasing distance to the front of the queue. For example, when ticket 47 is called, the person with ticket 48 still has ticket 48 in their hands.

b. When Netflix mails its customers the number 1 DVD on their queue, all the movies remaining in the queue are renumbered accordingly, automatically, by the website. Suppose for example a customer’s queue goes something like this:

1. Proof 2. Good Will Hunting 3. A Beautiful Mind 4. Pi 5. Stand and Deliver etc.

Then Netflix sends them Proof, so the customer’s queue changes like so:

1. Good Will Hunting 2. A Beautiful Mind 3. Pi 4. Stand and Deliver 5. Sneakers etc.

Of course there are always deviations. In a queue to get on a roller-coaster, someone might take cuts. Or it might in some cases even be institutionally permissible to ignore queue order somewhat. For example, in a triage situation, a doctor might choose to treat the second patient to arrive, an old woman who is coughing her lungs out, instead of the first patient, a young man with a paper cut. Or in the Netflix example, if all the copies of Proof are out with other customers, Netflix might send the example customer Good Will Hunting now and then Proof later.

In practice, queues always have capacity limits. For example, a computer that is tied up with a very computationally intensive task (such as factoring a very large prime) might become sluggish in processing the keyboard buffer. The user might quickly type way more than the buffer can accomodate, and when the computer finally can process the keyboard buffer, only a few letters of what the user typed might show up in the output.

Title	queue
Canonical name	Queue
Date of creation	2013-03-22 16:14:50
Last modified on	2013-03-22 16:14:50
Owner	Mravinci (12996)
Last modified by	Mravinci (12996)
Numerical id	4
Author	Mravinci (12996)
Entry type	Definition
Classification	msc 68P05