| | |
In the U.S., people stand "in line" to check out at the grocery store, board a plane, or to watch a movie. The British stand in "queues" to do the same thing. What characterizes a queue is that arriving customers always go to the "end of the line", while the next customer to be served is always taken from the "front of the line". More generally, customers are always served in the order in which they arrived.
There are times when data or objects must be similarly stored in a "queue", until they can be processed later. This often happens when one process generates data for another process, but the two processes run independently -- and at possibly different rates of speed. Examples include: print jobs being sent to a printer, or a web server trying to fulfill incoming requests for documents, or even the processing of characters typed from a keyboard.
In computer science, a queue is an abstract data type that can help in these (and other) circumstances. Queues are collections where the data they store are stored sequentially, and additions and removals are done in a First-In-First-Out (FIFO) manner.
In a queue, we call the method that adds something to the queue enqueue() and the method that removes something from the queue dequeue(). Having a method that can check if the queue is empty is also necessary so that one doesn't try to dequeue and element that is not present (an underflow error).
Similar to stacks, a queue should generally not have a fixed capacity. That is to say, regardless of how many elements are in the queue, one should always be able to enqueue another.
When using an array to store the contents of a queue, one should be aware that it is not necessary to copy items towards the head of the queue to accomplish a dequeue. Instead, the simple trick of turning the array into a closed circle by computing indices modulo the size of the array, and letting the head and tail drift around endlessly in that circle makes it unnecessary to ever move items stored in the array. Of course, when the array ultimately fills, it can be resized in much the same way as resizing arrays can be used to implement stacks.
Linked lists provide a very efficient alternative to arrays when implementing a queue.