 | This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(January 2014) (Learn how and when to remove this message) |
| Queue | ||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
 Representation of aFIFO (first in, first out) queue | ||||||||||||||||||||||||
| ||||||||||||||||||||||||
Incomputer science, a queue is an abstract data type that serves as an orderedcollection of entities. By convention, the end of the queue where elements are added, is called the back, tail, or rear of the queue. The end of the queue where elements are removed is called the head or front of the queue. The namequeue is ananalogy to the words used to describe people in line to wait for goods or services. It supports two main operations.
Other operations may also be allowed, often including apeek orfront operation that returns the value of the next element to be dequeued without dequeuing it.
The operations of a queue make it afirst-in-first-out (FIFO) data structure as the first element added to the queue is the first one removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. A queue is an example of alinear data structure, or more abstractly a sequential collection.Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as anabstract data structure or in object-oriented languages as classes. A queue may be implemented ascircular buffers andlinked lists, or by using both thestack pointer and the base pointer.
Queues provide services incomputer science,transport, andoperations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of abuffer.Another usage of queues is in the implementation ofbreadth-first search.
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.
Fixed-length arrays are limited in capacity, but it is not true that items need to be copied towards the head of the queue. The simple trick of turning the array into a closed circle and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in the array. If n is the size of the array, then computing indices modulo n will turn thearray into a circle. This is still the conceptually simplest way to construct a queue in ahigh-level language, but it does admittedly slow things down a little, because the array indices must be compared to zero and the array size, which is comparable to the time taken to check whether an array index is out of bounds, which some languages do, but this will certainly be the method of choice for a quick and dirty implementation, or for any high-level language that does not have pointer syntax. The array size must be declared ahead of time, but some implementations simply double the declared array size when overflow occurs. Most modern languages with objects orpointers can implement or come with libraries for dynamic lists. Suchdata structures may have not specified a fixed capacity limit besides memory constraints. Queueoverflow results from trying to add an element onto a full queue and queueunderflow happens when trying to remove an element from an empty queue.
Abounded queue is a queue limited to a fixed number of items.[1]
There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—inO(1) time.
Queues may be implemented as a separate data type, or maybe considered a special case of adouble-ended queue (deque) and not implemented separately. For example,Perl andRuby allow pushing and popping an array from both ends, so one can usepush andshift functions to enqueue and dequeue a list (or, in reverse, one can useunshift andpop),[2] although in some cases these operations are not efficient.
C++'sStandard Template Library provides a "queue" templated class which is restricted to only push/pop operations. Since J2SE5.0, Java's library contains aQueue interface that specifies queue operations; implementing classes includeLinkedList and (since J2SE 1.6)ArrayDeque. PHP has anSplQueue class and third-party libraries likebeanstalk'd andGearman.
A simple queue implemented inJavaScript:
classQueue{constructor(){this.items=[];}enqueue(element){this.items.push(element);}dequeue(){returnthis.items.shift();}}
Queues can also be implemented as apurely functional data structure.[3] There are two implementations. The first one only achieves per operationon average. That is, theamortized time is, but individual operations can take wheren is the number of elements in the queue. The second implementation is called areal-time queue[4] and it allows the queue to bepersistent with operations in O(1) worst-case time. It is a more complex implementation and requireslazy lists withmemoization.
This queue's data is stored in twosingly-linked lists named and. The list holds the front part of the queue. The list holds the remaining elements (a.k.a., the rear of the queue)in reverse order. It is easy to insert into the front of the queue by adding a node at the head of. And, if is not empty, it is easy to remove from the end of the queue by removing the node at the head of. When is empty, the list is reversed and assigned to and then the head of is removed.
The insert ("enqueue") always takes time. The removal ("dequeue") takes when the list is not empty. When is empty, the reverse takes where is the number of elements in. But, we can say it isamortized time, because every element in had to be inserted and we can assign a constant cost for each element in the reverse to when it was inserted.
The real-time queue achieves time for all operations, without amortization. This discussion will be technical, so recall that, for a list, denotes its length, thatNIL represents an empty list and represents the list whose head ish and whose tail ist.
The data structure used to implement our queues consists of threesingly-linked lists wheref is the front of the queue andr is the rear of the queue in reverse order. The invariant of the structure is thats is the rear off without its first elements, that is. The tail of the queue is then almost andinserting an elementx to is almost. It is said almost, because in both of those results,. An auxiliary function must then be called for the invariant to be satisfied. Two cases must be considered, depending on whether is the empty list, in which case, or not. The formal definition is and where isf followed byr reversed.
Let us call the function which returnsf followed byr reversed. Let us furthermore assume that, since it is the case when this function is called. More precisely, we define a lazy function which takes as input three lists such that, and return the concatenation off, ofr reversed and ofa. Then.The inductive definition of rotate is and. Its running time is, but, since lazy evaluation is used, the computation is delayed until the results are forced by the computation.
The lists in the data structure has two purposes. This list serves as a counter for, indeed, if and only ifs is the empty list. This counter allows us to ensure that the rear is never longer than the front list. Furthermore, usings, which is a tail off, forces the computation of a part of the (lazy) listf during eachtail andinsert operation. Therefore, when, the listf is totally forced. If it was not the case, the internal representation off could be some append of append of... of append, and forcing would not be a constant time operation anymore.
This article incorporatespublic domain material fromPaul E. Black."Bounded queue".Dictionary of Algorithms and Data Structures.NIST.
{{isbn}}: Checkisbn value: length (help). Chapter 4: Stacks and Queues, pp. 137–169.