Queues

A queue is an abstract data type consisting of an ordered collection of items, called elements. The elements in a queue might be numbers, strings or other data types.

The elements in a queue are accessed on a first in, first out basis (FIFO).

A queue will typically have functions that allow you to add an element to the end of the queue, and fetch an element from the front of the queue. It will also usually have a function to tell you if the queue is empty, and various other functions.

Queue functions and operation

A queue will typically have an enQueue function that adds an element to the queue. Here is how it works:

Starting with an empty queue, we first enQueue the value 7. This value is placed at the back of the queue. Of course, since the queue is empty, the back of the queue is also the front of the queue!

Next we enQueue the value 4, and it is placed at the back of the queue, behind the 7. Then we enQueue the value 9, and it is placed at the back of the queue, behind the 4.

Now there are 3 items in the queue. We can take elements off the queue, in the same order they were added (first in, first out), using deQueue:

The first call to deQueue returns the value at the start of the queue, 7, leaving (4, 9) on the queue.

We can mix enQueue and deQueue calls. To illustrate this, we use enQueue to add 3 to the back of the queue, leaving (4, 9, 3) on the queue.

The next call to deQueue returns the value at the start of the queue, 4, leaving (9, 3) on the queue.

What happens if we try to deQueue an item when the queue is empty? A queue will usually have a method called isEmpty (or similar) that you can call to check if there are any values in the queue before attempting to remove an item.

An example

If you try to print several documents from your computer, they can only be printed one at a time. The printing software uses a queue to store a list of documents that are waiting to be printed, and to make sure that they are printed in the correct order (the order in which they were sent).

Other queue functions

Thinking about the printer queue, it is clear that queues might benefit from other useful methods. The len method, or similar, tells you how many items are in the queue, so that you know how much work your printer has to do.

It is also useful to be able to look at the individual items in the queue, so that you can check how long it might be before a particular document gets printed. You might want to move a document to the front of the queue, if it is very urgent, or you might want to remove a document from the queue if you decide you don't really want to print it after all.

Queues often provide similar functions similar to lists to enable these types of operations.

Queue implementations

Queues are often implemented as list based queues. Alternatively, circular queues can be implemented using an array.

For more complex situations, priority queues allow some items to jump ahead of others.

See also

• Abstract data types
• Arrays
• Lists
• Array lists
• Linked lists
• Static vs dynamic data structures
• List based queues
• Circular queues