In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a queue is a
collection
Collection or Collections may refer to:
* Cash collection, the function of an accounts receivable department
* Collection (church), money donated by the congregation during a church service
* Collection agency, agency to collect cash
* Collectio ...
of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.
The operation of adding an element to the rear of the queue is known as ''enqueue'', and the operation of removing an element from the front is known as ''dequeue''. Other operations may also be allowed, often including a ''
peek
Polyether ether ketone (PEEK) is a colourless organic thermoplastic polymer in the polyaryletherketone (PAEK) family, used in engineering applications. The polymer was first developed in November 1978, later being introduced to the market by Vic ...
'' 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
first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be 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
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a '' user'', of the data, specifically in terms of possible values, ...
or in object-oriented languages as classes. Common implementations are
circular buffer
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
s and
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
s.
Queues provide services in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
,
transport
Transport (in British English), or transportation (in American English), is the intentional movement of humans, animals, and goods from one location to another. Modes of transport include air, land (rail and road), water, cable, pipeline, an ...
, and
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
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
Buffer may refer to:
Science
* Buffer gas, an inert or nonflammable gas
* Buffer solution, a solution used to prevent changes in pH
* Buffering agent, the weak acid or base in a buffer solution
* Lysis buffer, in cell biology
* Metal ion buffer
* ...
.
Another usage of queues is in the implementation of
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
.
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
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
into a circle. This is still the conceptually simplest way to construct a queue in a 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
pointers can implement or come with libraries for dynamic lists. Such
data structure
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
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.
There are several efficient implementations of FIFO queues. An efficient implementation is one that can perform the operations—en-queuing and de-queuing—in
O(1) time.
*
Linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
**A
doubly linked list
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked record (computer science), records called node (computer science), nodes. Each node contains three field (computer science), fields: ...
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
deque
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). ...
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
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). I ...
(deque) and not implemented separately. For example,
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
and
Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
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), although in some cases these operations are not efficient.
C++'s
Standard Template Library
The Standard Template Library (STL) is a Library (computer science), software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components ...
provides a "
queue
" templated class which is restricted to only push/pop operations. Since J2SE5.0, Java's library contains a interface that specifies queue operations; implementing classes include and (since J2SE 1.6) . PHP has a
SplQueueclass and third party libraries like
beanstalk'd and
Gearman
Gearman is an open-source application framework designed to distribute appropriate computer tasks to multiple computers, so large tasks can be done more quickly. In some cases, load balancing rather than raw speed may be the main goal; a Web serv ...
.
Example
A simple queue implemented in
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
:
class Queue
Purely functional implementation
Queues can also be implemented as a
purely functional data structure
In computer science, a purely functional data structure is a data structure that can be implemented in a purely functional language. The main difference between an arbitrary data structure and a purely functional one is that the latter is (strongl ...
. There are two implementations. The first one only achieves
per operation ''on average''. That is, the
amortized
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...
time is
, but individual operations can take
where ''n'' is the number of elements in the queue. The second implementation is called a real-time queue
and it allows the queue to be
persistent with operations in O(1) worst-case time. It is a more complex implementation and requires
lazy lists with
memoization
In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. Memoization ...
.
Amortized queue
This queue's data is stored in two
singly-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 is
amortized
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case ...
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.
Real-time queue
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, that ''NIL'' represents an empty list and
represents the list whose head is ''h'' and whose tail is ''t''.
The data structure used to implement our queues consists of three
singly-linked lists where ''f'' is the front of the queue, ''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
first elements, that is
. The tail of the queue
is then almost
and
inserting an element ''x'' 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
is ''f'' followed by ''r'' reversed.
Let us call
the function which returns ''f'' followed by ''r'' 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 list such that
, and return the concatenation of ''f'', of ''r'' reversed and of ''a''. 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 is forced by the computation.
The list ''s'' in the data structure has two purposes. This list serves as a counter for
, indeed,
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
, 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
*
Circular buffer
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. Ther ...
*
Double-ended queue
In computer science, a double-ended queue (abbreviated to deque, pronounced ''deck'', like "cheque") is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). I ...
(deque)
*
Priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
*
Queuing theory
Queueing theory is the mathematical study of waiting lines, or queues. A queueing model is constructed so that queue lengths and waiting time can be predicted. Queueing theory is generally considered a branch of operations research because the ...
*
Stack (abstract data type) – the "opposite" of a queue: LIFO (Last In First Out)
References
General references
*
Further reading
*
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
. ''
The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
'', Volume 1: ''Fundamental Algorithms'', Third Edition. Addison-Wesley, 1997. . Section 2.2.1: Stacks, Queues, and Dequeues, pp. 238–243.
*
Thomas H. Cormen
Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmout ...
,
Charles E. Leiserson
Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof. As part of this effort, he developed the Cilk multithreaded language. ...
,
Ronald L. Rivest
Ronald Linn Rivest (; born May 6, 1947) is a cryptographer and an Institute Professor at MIT. He is a member of MIT's Department of Electrical Engineering and Computer Science (EECS) and a member of MIT's Computer Science and Artificial Inte ...
, and
Clifford Stein
Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Scien ...
. ''
Introduction to Algorithms
''Introduction to Algorithms'' is a book on computer programming by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The book has been widely used as the textbook for algorithms courses at many universities and is co ...
'', Second Edition. MIT Press and McGraw-Hill, 2001. . Section 10.1: Stacks and queues, pp. 200–204.
*William Ford,
William Topp
William is a male given name of Germanic origin.Hanks, Hardcastle and Hodges, ''Oxford Dictionary of First Names'', Oxford University Press, 2nd edition, , p. 276. It became very popular in the English language after the Norman conquest of Engl ...
. ''Data Structures with C++ and STL'', Second Edition. Prentice Hall, 2002. . Chapter 8: Queues and Priority Queues, pp. 386–390.
*
Adam Drozdek. ''Data Structures and Algorithms in C++'', Third Edition. Thomson Course Technology, 2005. . Chapter 4: Stacks and Queues, pp. 137–169.
External links
STL Quick Reference
{{DEFAULTSORT:Queue (Data Structure)
Abstract data types
Articles with example C++ code