-
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.
Applications
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.
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.
Implementations
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.
See also
In computer science, compare:
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 0262032937. Section 10.1: Stacks and queues, pp.200–204.
|
