Queue (data structure)
From Wikipedia, the free encyclopedia
In providing services in computer science, transport, and operations research a queue (pronounced 'Q') is a buffer abstract data structure 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. Unless otherwise specified, the remainder of the article will refer to FIFO queues. There are also non-FIFO queue data structures, like priority queues.
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
Contents |
[edit] Applications
[edit] 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.
[edit] 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.
[edit] 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. Queues can also be implemented as double-ended dynamic arrays.
In imperative languages, it is also possible to implement finite-capacity queues as arrays, by having a dynamic pointer to the front and end of the queue and allowing the array to wrap. Thus dequeuing will cause the front pointer to advance, so the data may be stored in any contiguous (possibly wrapping) section of the array. This allows for Θ(1) enqueuing and dequeuing as well, without the overhead of linked lists.
C++'s Standard Template Library provides a std::queue templated class which is restricted to only enqueue/dequeue operations. Java's library contains a Queue interface that is implemented by various classes like LinkedList.
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 other operation will be O(1) time). This is because adding items to the front of a list is trivial in declarative languages, while adding to the end requires the list to be rebuilt. The following Haskell demonstrates these naïve algorithms.
enqueue x q = q ++ [x] 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(f, reverse(t)). 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 ([],t) = 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.
[edit] See also
In computer science, compare:
- Array
- Deque
- Priority queue
- Linked list
- Stack (the "opposite" of a queue — Last In First Out (LIFO))
- Congestion
- Pipeline
- Queueing theory
- Spooling
- For details of a common implementation, see Circular buffer.
- For a description of the behaviour, see FIFO.
[edit] 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 0-262-03293-7. Section 10.1: Stacks and queues, pp.200–204.
[edit] External links
- Pointers to queue visualizations
- Queue program in c++ Queue
