PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
queue (Definition)

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.

"queue" is owned by Mravinci.
(view preamble)

View style:

Cross-references: type, prime, limits, order, even, cuts, pi, distance, index, stack, structure
There are 6 references to this entry.

This is version 1 of queue, born on 2006-09-15.
Object id is 8351, canonical name is Queue.
Accessed 378 times total.

AMS MSC68P05 (Computer science :: Theory of data :: Data structures)

Pending Errata and Addenda
Style: Expand: Order:
forum policy
Needs greater abstraction by Mravinci on 2006-09-15 15:15:38
Yeah, I know this needs greater abstraction. CWoo, who filed this request, also wrote in regards to Cooper's {\it Introduction to Queueing Theory} that its "emphasis is on the application of queueing theory, rather than the theoretical aspect of it." What I've written is way less theoretical than Cooper's book.
[ reply | up ]

rate | post | correct | update request | add derivation | add example | add (any)