View source for Queue (abstract data type)

{{short description|Abstract data type}}
{{More footnotes|date=January 2014}}

{{Infobox data structure
|name=Queue
|image=Data Queue.svg
|caption=Representation of a [[FIFO (computing and electronics)|FIFO]] (first in, first out) queue
|space_avg={{math|O(''n'')}}
|space_worst={{math|O(''n'')}}
|search_avg={{math|O(''n'')}}
|search_worst={{math|O(''n'')}}
|insert_avg={{math|O(1)}}
|insert_worst={{math|O(1)}}
|delete_avg={{math|O(1)}}
|delete_worst={{math|O(1)}}
}}
In [[computer science]], a queue is an abstract data type that serves as an ordered [[collection (abstract data type)|collection]] 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 name ''queue'' is an [[analogy]] to the words used to describe people in line to wait for goods or services. It supports two main operations. 

* '''Enqueue,''' which adds one element to the rear of the queue
* '''Dequeue,''' which removes one element from the front of the queue. 

Other operations may also be allowed, often including a ''[[peek (data type operation)|peek]]'' or ''front'' operation that returns the value of the next element to be dequeued without dequeuing it.

The operations of a queue make it a [[FIFO (computing and electronics)|first-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 a [[linear 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 an [[abstract data structure]] or in object-oriented languages as classes. A queue may be implemented as [[circular buffer]]s and [[linked list]]s, or by using both the [[stack pointer]] and the base pointer.

Queues provide services in [[computer science]], [[transport]], and [[operations 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 a [[buffer (computer science)|buffer]].
Another usage of queues is in the implementation of [[breadth-first search]].

=={{Anchor|BOUNDED}}Queue implementation==
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 the [[array]] into a circle. This is still the conceptually simplest way to construct a queue in a [[High-level programming language|high-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 or [[pointer (computer programming)|pointer]]s can implement or come with libraries for dynamic lists. Such [[data structure]]s may have not specified a fixed capacity limit besides memory constraints. 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.

A ''bounded queue'' is a queue limited to a fixed number of items.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html |title=Queue (Java Platform SE 7) |publisher=Docs.oracle.com |date=2014-03-26 |access-date=2014-05-22}}</ref>

There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—in [[Big O notation|O(1) time]].
*[[Linked list]]
**A [[doubly linked list]] has O(1) insertion and deletion at both ends, so it is a natural choice for queues.
**A regular singly linked list only has efficient insertion and deletion at one end. However, a small modification—keeping a pointer to the ''last'' node in addition to the first one—will enable it to implement an efficient queue.
*A [[double-ended queue|deque]] implemented using a modified dynamic array

===Queues and programming languages===
Queues may be implemented as a separate data type, or maybe considered a special case of a [[double-ended queue]] (deque) and not implemented separately. For example, [[Perl]] and [[Ruby (programming language)|Ruby]] allow pushing and popping an array from both ends, so one can use '''push''' and '''shift''' functions to enqueue and dequeue a list (or, in reverse, one can use '''unshift''' and '''pop'''),<ref>{{cite web|url=https://docs.ruby-lang.org/en/master/Array.html#class-Array-label-Adding+Items+to+an+Array |title=Class Array}}</ref> although in some cases these operations are not efficient.

C++'s [[Standard Template Library]] provides a "<code>queue</code>" templated class which is restricted to only push/pop operations. Since J2SE5.0, Java's library contains a {{Javadoc:SE|java/util|Queue}} interface that specifies queue operations; implementing classes include {{Javadoc:SE|java/util|LinkedList}} and (since J2SE 1.6) {{Javadoc:SE|java/util|ArrayDeque}}. PHP has an [http://www.php.net/manual/en/class.splqueue.php SplQueue] class and third-party libraries like [[beanstalk'd]] and [[Gearman]].

[[File:UML queue class.svg|UML queue class.svg]]

===Example===
A simple queue implemented in [[TypeScript]]:

<syntaxhighlight lang="typescript">
class Queue<T> {
    private items: T[] = [];

    enqueue(element: T): void {
        this.items.push(element);
    }

    dequeue(): T | undefined {
        return this.items.shift();
    }

    isEmpty(): boolean {
        return this.items.length === 0;
    }
}
</syntaxhighlight>

==Purely functional implementation==
Queues can also be implemented as a [[purely functional data structure]].<ref>{{cite web |last1=Okasaki|first1=Chris|title=Purely Functional Data Structures|url=https://doc.lagout.org/programmation/Functional%20Programming/Chris_Okasaki-Purely_Functional_Data_Structures-Cambridge_University_Press%281998%29.pdf}}</ref> There are two implementations. The first one only achieves <math>O(1)</math> per operation ''on average''.  That is, the [[amortized analysis|amortized]] time is <math>O(1)</math>, but individual operations can take <math>O(n)</math> where ''n'' is the number of elements in the queue.  The second implementation is called a '''real-time queue'''<ref>{{cite journal|last1=Hood|first1=Robert|last2=Melville|first2=Robert|title=Real-time queue operations in pure Lisp|journal=Information Processing Letters|date=November 1981|volume=13|issue=2|pages=50–54 |doi=10.1016/0020-0190(81)90030-2 |hdl=1813/6273|hdl-access=free}}</ref> and it allows the queue to be [[persistent data structure|persistent]] with operations in O(1) worst-case time. It is a more complex implementation and requires [[lazy evaluation|lazy]] lists with [[memoization]]. 

===Amortized queue===

This queue's data is stored in two [[Linked_list#Singly_linked_list|singly-linked lists]] named <math>f</math> and <math>r</math>.  The list <math>f</math> holds the front part of the queue.  The list <math>r</math> 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 <math>f</math>.  And, if <math>r</math> is not empty, it is easy to remove from the end of the queue by removing the node at the head of <math>r</math>.  When <math>r</math> is empty, the list <math>f</math> is reversed and assigned to <math>r</math> and then the head of <math>r</math> is removed.  

The insert ("enqueue") always takes <math>O(1)</math> time.  The removal ("dequeue") takes <math>O(1)</math> when the list <math>r</math> is not empty.  When <math>r</math> is empty, the reverse takes <math>O(n)</math> where <math>n</math> is the number of elements in <math>f</math>.  But, we can say it is <math>O(1)</math> [[amortized analysis|amortized]] time, because every element in <math>f</math> had to be inserted and we can assign a constant cost for each element in the reverse to when it was inserted.  

===Real-time queue===

The real-time queue achieves <math>O(1)</math> time for all operations, without amortization.  This discussion will be technical, so recall that, for <math>l</math> a list, <math>|l|</math> denotes its length, that ''NIL'' represents an empty list and <math>\operatorname{CONS}(h,t)</math> represents the list whose head is ''h'' and whose tail is ''t''.

The data structure used to implement our queues consists of three [[Linked_list#Singly_linked_list|singly-linked lists]] <math>(f,r,s)</math> where ''f'' is the front of the queue and ''r'' is the rear of the queue in reverse order. The invariant of the structure is that ''s'' is the rear of ''f'' without its <math>|r|</math> first elements, that is <math>|s|=|f|-|r|</math>. The tail of the queue <math>(\operatorname{CONS}(x,f),r,s)</math> is then almost <math>(f,r,s)</math> and
inserting an element ''x'' to <math>(f,r,s)</math> is almost <math>(f,\operatorname{CONS}(x,r),s)</math>. It is said almost, because in both of those results, <math>|s|=|f|-|r|+1</math>. An auxiliary function <math>aux</math> must then be called for the invariant to be satisfied. Two cases must be considered, depending on whether <math>s</math> is the empty list, in which case <math>|r|=|f|+1</math>, or not. The formal definition is <math>\operatorname{aux}(f,r,\operatorname{Cons}(\_,s))=(f,r,s)</math> and <math>\operatorname{aux}(f,r,\text{NIL})=(f',\text{NIL},f')</math> where <math>f'</math> is ''f'' followed by ''r'' reversed.

Let us call <math>\operatorname{reverse}(f,r)</math> the function which returns ''f'' followed by ''r'' reversed. Let us furthermore assume that <math>|r|=|f|+1</math>, since it is the case when this function is called. More precisely, we define a lazy function <math>\operatorname{rotate}(f,r,a)</math> which takes as input three lists such that <math>|r|=|f|+1</math>, and return the concatenation of ''f'', of ''r'' reversed and of ''a''. Then <math>\operatorname{reverse}(f,r)=\operatorname{rotate}(f,r,\text{NIL})</math>.
The inductive definition of rotate is <math>\operatorname{rotate}(\text{NIL},\operatorname{Cons}(y,\text{NIL}),a)=\operatorname{Cons}(y,a)</math> and <math>\operatorname{rotate}(\operatorname{CONS}(x,f),\operatorname{CONS}(y,r),a)=\operatorname{Cons}(x,\operatorname{rotate}(f,r,\operatorname{CONS}(y,a)))</math>. Its running time is <math>O(r)</math>, but, since lazy evaluation is used, the computation is delayed until the results are forced by the computation.

The list ''s'' in the data structure has two purposes. This list serves as a counter for <math>|f|-|r|</math>, indeed, <math>|f|=|r|</math> if and only if ''s'' is the empty list. This counter allows us to ensure that the rear is never longer than the front list. Furthermore, using ''s'', which is a tail of ''f'', forces the computation of a part of the (lazy) list ''f'' during each ''tail'' and ''insert'' operation. Therefore, when <math>|f|=|r|</math>, the list ''f'' is totally forced. If it was not the case, the internal representation of ''f'' could be some append of append of... of append, and forcing would not be a constant time operation anymore.

==See also==
{{Portal|Computer programming}}
*[[Event loop]] - events are stored in a queue
*[[Message queue]]
*[[Priority queue]]
*[[Queueing theory|Queuing theory]]
*[[Stack (abstract data type)]] – the "opposite" of a queue: LIFO (Last In First Out)

==References==
{{Reflist}}

===General references===
* {{DADS|Bounded queue|boundedqueue}}

==Further reading==
*[[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 Dequeues, pp.&nbsp;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.&nbsp;200–204.
*William Ford, [[William Topp]]. ''Data Structures with C++ and STL'', Second Edition. Prentice Hall, 2002. {{ISBN|0-13-085850-1}}. Chapter 8: Queues and Priority Queues, pp.&nbsp;386–390.
*[[Adam Drozdek]]. ''Data Structures and Algorithms in C++'', Third Edition. Thomson Course Technology, 2005. {{ISBN|0-534--0}}. Chapter 4: Stacks and Queues, pp.&nbsp;137–169.

==External links==
{{Commons category|Queue data structure}}
*[http://www.halpernwightsoftware.com/stdlib-scratch/quickref.html#containers14 STL Quick Reference]
*[https://web.archive.org/web/20110714000645/http://www.ludvikjerabek.com/downloads.html VBScript implementation of stack, queue, deque, and Red-Black Tree]

{{Data structures}}

{{DEFAULTSORT:Queue (Data Structure)}}
[[Category:Abstract data types]]
[[Category:Articles with example C++ code]]