FACTOID # 15: A mere 0.8% of West Virginians were born in a foreign country.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > Queues

For queueing people, see queue area. A queue is also a style of braided hair.

In providing services to people, and in computer science, transportation, and operations research a queue is a First-In-First-Out FIFO process — the first element 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 removed.

This article discusses the queue data structure.

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 usually 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. For a waiting queue of people, eventually there might not be enough space to squeeze into, or people might decide that the queue is alredy too long and not bother adding themselves to it.

In computer science, compare:

Implementation in Scheme

The following functional implements queues as a persistent data structure, representing the queue as a pair of lists. The queue elements are the elements in the front followed by (in reverse order) the elements in the back. The time for enqueue and dequeue are O(1) amortized time.

 (define make-queue cons) (define queue-front car) (define queue-back cdr) (define empty-queue (cons '() '())) (define (enqueue Q x) (make-queue (queue-front Q) (cons x (queue-back Q)))) (define (dequeue Q) (cond [(and (null? (queue-front Q)) (null? (queue-back Q))) (error "dequeue: The queue is empty")] [(null? (queue-front Q)) (dequeue (make-queue (reverse (queue-back Q)) '()))] [else (values (car (queue-front Q)) (make-queue (cdr (queue-front Q)) (queue-back Q)))])) 

See also

The Oroogu programming language relies on queues as its only data structure

External links

  • Queue Implementation (http://www.greatsnakes.com/savannah/queue.asp)

  Results from FactBites:
Queue (Java 2 Platform SE 5.0) (531 words)
Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out).
In a FIFO queue, all new elements are inserted at the tail of the queue.
Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation.
PlanetMath: queue (380 words)
A queue is a one-dimensional data structure to which new members or elements are generally added (pushed or enqueued) at the end and removed (popped or dequeued) from the start.
For example, in a triage situation, a doctor might choose to treat the second patient to arrive, an old woman who is coughing her lungs out, instead of the first patient, a young man with a paper cut.
This is version 1 of queue, born on 2006-09-15.
  More results at FactBites »



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m