A queue (pronounced /kuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. 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. In computer science, a collection is a grouping of some variable number of data items (possibly zero) that have some shared significance to the problem being solved and need to be operated upon together in some controlled fashion. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Operations Research or Operational Research (OR) is an interdisciplinary branch of mathematics which uses methods like mathematical modeling, statistics, and algorithms to arrive at optimal or good decisions in complex problems which are concerned with optimizing the maxima (profit, faster assembly line, greater crop yield, higher bandwidth, etc) or minima... In computing, a buffer is a region of memory used to temporarily hold output or input data, comparable to buffers in telecommunication. ...

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. In theoretical computer science, an abstract data structure is an abstract storage for data defined in terms of the set of operations to be performed on data and computational complexity for performing these operations, regardless the implementation in a concrete data structure. ...

The most well known operation of the queue is the First-In-First-Out (FIFO) queue process. In a FIFO queue, the first element added to 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. FIFO is an acronym for First In, First Out. ... A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing...

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 the queue and returning it to the calling entity.

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. Capacity may mean one of the following: Capacity, when used with the mathematics meaning, is another word for volume Legal capacity refers to the legal ability to engage in certain acts, such as making a contract Cranial capacity is a measure of the volume of the interior of the skull...

A practical implementation of a queue e.g. with pointers 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. Look up Implementation in Wiktionary, the free dictionary. ... It has been suggested that Software pointer be merged into this article or section. ... A binary tree, a simple type of branching linked data structure. ...

A bounded queue is a queue limited to a fixed number of items.

See also

• Array
• Circular buffer
• Congestion
• Deque
• Linked list
• Pipeline
• Priority queue
• Queueing theory
• Spooling
• Stack (data structure) - the "opposite" of a queue: LIFO (Last In First Out)

This article does not cite any references or sources. ... A circular buffer is a method of using memory within a computer program. ... Congestion is a state of excessive accumulation or overfilling or overcrowding. ... In computer science, a deque (short for double-ended queue) is a data structure for which elements can be added to or removed from the front or back. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... A priority queue is an abstract data type in computer programming, supporting the following three operations: add an element to the queue with an associated priority remove the element from the queue that has the highest priority, and return it (optionally) peek at the element with highest priority without removing... Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues). ... In computer science, spooling refers to putting jobs in a buffer, a special area in memory, or on a disk where a device can access them when it is ready. ... Simple representation of a stack In computer science, a stack is a temporary abstract data type and data structure based on the principle of Last In First Out (LIFO). ... In a stack, the topmost item, which is added last, is taken out first. ...

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.

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. 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. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

• Pointers to queue visualizations
• Queue program in c++ Queue
• STL Quick Reference: Queue
• Paul E. Black, Bounded queue at the NIST Dictionary of Algorithms and Data Structures.
• Queues Guide hosted at FrozenEther