Queue

In providing services in computer science, transport, and operations research a queue is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. The most well known operation of the queue is the First-In-First-Out (FIFO) queue process — In a FIFO queue, the first element in the queue will be the first one out; this is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked.

There are two basic operations associated with a queue: enqueue and dequeue. Enqueue means adding a new item to the rear of the queue while dequeue refers to removing the front item from queue and returns it in item.

Theoretically, one characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.

A practical implementation of a queue of course does have some capacity limit, that depends on the concrete situation it is used in. For a data structure the executing computer will eventually run out of memory, thus limiting the queue size. Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue

Applications

Scheduling and buffering queues

A queue is natural data structure for a system to serve the incoming requests. Most of the process scheduling or disk scheduling algorithms in operating systems use queues. Computer hardware like a processor or a network card also maintain buffers in the form of queues for incoming resource requests. A stack like data structure causes starvation of the first requests, and is not applicable in such cases. A mailbox or port to save messages to communicate between two users or processes in a system is essentially a queue like structure.

Search space exploration

Like stacks, queues can be used to remember the search space that needs to be explored at one point of time in traversing algorithms. Breadth first search of a graph uses a queue to remember the nodes yet to be visited.

Algorithms

In imperative programming languages, queues can be implemented as linked lists. Since new items are appended at the end, a pointer to the last node of the list should be kept. This way, enqueuing and dequeuing an element can both be performed in Θ(1) time.

In declarative programming languages, a simple list representation can still be used, but then either enqueuing or dequeuing uses O(n) time and rebuilds the entire queue. The following Haskell demonstrates these naïve algorithms.

enqueue x q = q ++ ^* dequeue (x:q) = (x,q)

(Note: the dequeue function returns a pair (x,newqueue) where newqueue is the original queue with the first element x removed. ++ denotes append.)

Fortunately, a smarter scheme is available. A queue can be represented by a pair of lists, where the first list is the front of the queue, and the second list is the reversed tail of the list. I.e., if a queue is represented as q = (f,t), then the list of elements in q can be obtained by append(x, reverse(y)). This representation can be used with the following algorithms (in Haskell):

enqueue x (f,t) = (f, (x:t)) dequeue ((x:f),t) = (x, (f,t)) dequeue (^*,^*) = error "empty queue" dequeue ( = dequeue (reverse t, [)

The enqueuing algorithm runs in O(1), as can be easily observed. The dequeuing algorithm runs in O(1) amortized time.

The Oroogu programming language relies on queues as its only data structure.

References

Donald Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238–243.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 10.1: Stacks and queues, pp.200–204.

External links

Pointers to queue visualizations

data structures