FACTOID # 25: If you're tired of sitting in traffic on your way to work, move to North Dakota.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW RELATED ARTICLES People who viewed "Queue" also viewed:

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Queue

In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. The most well known operation of the queue is the First-In-First-Out (FIFO) queue process — In a FIFO queue, 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 invoked. 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 simply OR is an interdisciplinary science which deploys scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and execution of the operations within an organization. ... FIFO is an acronym for First In, First Out. ...

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 queue and returns it in item.

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 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. ... A binary tree, a simple type of branching linked data structure. ...

## Contents

### Scheduling and buffering queues

A queue is natural data structure for a system to serve the incoming requests. Most of the process scheduling or disk scheduling algorithms in operating systems use queues. Computer hardware like a processor or a network card also maintain buffers in the form of queues for incoming resource requests. A stack like data structure causes starvation of the first requests, and is not applicable in such cases. A mailbox or port to save messages to communicate between two users or processes in a system is essentially a queue like structure. Look up Stack in Wiktionary, the free dictionary. ...

### Search space exploration

Like stacks, queues can be used to remember the search space that needs to be explored at one point of time in traversing algorithms. Breadth first search of a graph uses a queue to remember the nodes yet to be visited. Look up Stack in Wiktionary, the free dictionary. ...

## Algorithms

In imperative programming languages, queues can be implemented as linked lists. Since new items are appended at the end, a pointer to the last node of the list should be kept. This way, enqueuing and dequeuing an element can both be performed in Θ(1) time. Queues can also be implemented as double-ended dynamic arrays. In computer science, imperative programming, as opposed to declarative programming, is a programming paradigm that describes computation in terms of a program state and statements that change the program state. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... It has been suggested that this article or section be merged into Asymptotic notation. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...

In imperative languages, it is also possible to implement finite-capacity queues as arrays, by having a dynamic pointer to the front and end of the queue and allowing the array to wrap. Thus dequeuing will cause the front pointer to advance, so the data may be stored in any contiguous (possibly wrapping) section of the array. This allows for Θ(1) enqueuing and dequeuing as well, without the overhead of linked lists. In computer science, a pointer is a programming language datatype whose value refers directly to (points to) another value stored elsewhere in the computer memory using its address. ...

C++'s Standard Template Library provides a `std::queue` templated class which is restricted to only enqueue/dequeue operations. Java's library contains a `Queue` interface that is implemented by various classes like LinkedList. The Standard Template Library (STL) is a software library included in the C++ Standard Library. ...

In declarative programming languages, a simple list representation can still be used, but then either enqueuing or dequeuing uses O(n) time and rebuilds the entire queue (the other operation will be O(1) time). This is because adding items to the front of a list is trivial in declarative languages, while adding to the end requires the list to be rebuilt. The following Haskell demonstrates these naïve algorithms. A declarative programming language is a high-level language that describes a problem rather than defining a solution. ... Haskell is a standardized pure functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

` enqueue x q = q ++ [x] dequeue (x:q) = (x,q) `

(Note: the `dequeue` function returns a pair (x,newqueue) where newqueue is the original queue with the first element x removed. `++` denotes append.) In computer programming, append is the name of a procedure for concatenating (linked) lists or arrays in some high-level programming languages. ...

Fortunately, a smarter scheme is available. A queue can be represented by a pair of lists, where the first list is the front of the queue, and the second list is the reversed tail of the list. I.e., if a queue is represented as q = (f,t), then the list of elements in q can be obtained by append(f, reverse(t)). This representation can be used with the following algorithms (in Haskell): In computer programming, append is the name of a procedure for concatenating (linked) lists or arrays in some high-level programming languages. ... Haskell is a standardized pure functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

` enqueue x (f,t) = (f, (x:t)) dequeue ((x:f),t) = (x, (f,t)) dequeue ([],[]) = error "empty queue" dequeue ([],t) = dequeue (reverse t, []) `

The enqueuing algorithm runs in O(1), as can be easily observed. The dequeuing algorithm runs in O(1) amortized time. In computational complexity theory, amortized analysis is the time per operation averaged over a worst_case sequence of operations. ...

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

In computer science, compare:

In computer programming, a group of homogeneous elements of a specific data type is known as an array, one of the simplest data structures. ... 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. ... A priority queue is an ADT (abstract data type) supporting the following two 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 The simplest way to implement a priority queue data type is to... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... 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. ... Congestion is a state of excessive accumulation or overfilling or overcrowding. ... Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues). ... In computer science, spooling is an acronym for simultaneous peripheral operations on-line (although this is thought by some to be a backronym). ... A circular buffer is a method of using memory within a computer program. ... FIFO is an acronym for First In, First Out. ...

## References

Donald Knuth at a reception for the Open Content Alliance. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles 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. ... Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

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