Queue

From Free net encyclopedia

(Redirected from Queue (computing))
For other uses, see Queue (disambiguation).

In providing services to people, and in computer science, transport 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.

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.

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

For a waiting queue of people, eventually there might not be enough space to squeeze into, or people might decide that the queue is already too long and not bother adding themselves to it.

Contents

[edit]

Applications

[edit]

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.

[edit]

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.

[edit]

Implementations

[edit]

Scheme

The following functional implements queues in Scheme 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 enqueue and dequeue operations require amortized O(1) 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)))]))

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

[edit]

See also

In computer science, compare:

[edit]

References

da:Kø (datastruktur) de:Warteschlange (Datenstruktur) es:Cola (estructura de datos) fr:File he:תור (מבנה נתונים) ja:キュー nl:Wachtrij pl:Kolejka fi:Jono sv:Kö (datastruktur) uk:Черга (структура даних) zh:队列

Retrieved from "http://www.netipedia.com/index.php/Queue"