Queue (data structure)

related topics
{math, number, function}
{system, computer, user}
{car, race, vehicle}
{build, building, house}
{day, year, event}
{line, north, south}
{@card@, make, design}

A queue (pronounced /ˈkjuː/ kew) 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. This makes the queue 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 an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure.

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.

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. Common implementations are circular buffers and linked lists.

Contents

Operations

Common operations from the C++ Standard Template Library include the following:

Example Javascript code

function Queue() {
    var data = [];
 
    this.isEmpty = function() {
        return (data.length == 0);
    };
 
    this.enqueue = function(obj) {
        data.push(obj);
    };
 
    this.dequeue = function() {
        return data.shift();
    };
 
    this.peek = function() {
        return data[0];
    };
 
    this.clear = function() {
        data = [];
    };
}

[edit] Representing a queue

The defining attribute of a queue data structure is the fact that allows access to only the front and back of the structure. Furthermore, elements can only be removed from the front and can only be added to the back. In this way, an appropriate metaphor often used to represent queues is the idea of a checkout line[1]. Other examples of queues are people traveling up an escalator, machine parts on an assembly line, or cars in line at a petrol station. The recurring theme is clear: queues are essentially the same as a queue you would get in a shop waiting to pay.

In each of the cases, the customer or object at the front of the line was the first one to enter, while at the end of the line is the last to have entered. Every time a customer finishes paying for their items (or a person steps off the escalator, or the machine part is removed from the assembly line, etc.) that object leaves the queue from the front. This represents the queue “dequeue” function. Every time another object or customer enters the line to wait, they join the end of the line and represent the “enqueue” function. The queue “size” function would return the length of the line, and the “empty” function would return true only if there was nothing in the line.

[edit] 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.

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.

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

[edit] See also

[edit] References

General
Citations
  1. ^ Ford/Topp p. 385

[edit] External links

 This article incorporates public domain material from the NIST document "Bounded queue" by Paul E. Black (Dictionary of Algorithms and Data Structures).

Full article ▸

related documents
B-tree
XSL Transformations
Oracle machine
Unicity distance
Richard's paradox
Extended real number line
Splitting lemma
Ring (mathematics)
Haar measure
Assignment problem
Idempotence
Axiom of pairing
Presburger arithmetic
Legendre symbol
Preorder
Meromorphic function
Functional analysis
Chain rule
Elementary group theory
Lazy evaluation
Mathematical model
Merkle-Hellman
Examples of groups
Associativity
Boolean ring
Trie
ML (programming language)
Monster group
Lagrange inversion theorem
Extended Backus–Naur Form