By Martin McBride, 2018-05-05
Tags: queue abstract data type
Categories: data structures

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

Sign up to the Creative Coding Newletter

Join my newsletter to receive occasional emails when new content is added, using the form below:

Popular tags

555 timer abstract data type abstraction addition algorithm and gate array ascii ascii85 base32 base64 battery binary binary encoding binary search bit block cipher block padding byte canvas colour coming soon computer music condition cryptographic attacks cryptography decomposition decryption deduplication dictionary attack encryption file server flash memory hard drive hashing hexadecimal hmac html image insertion sort ip address key derivation lamp linear search list mac mac address mesh network message authentication code music nand gate network storage none nor gate not gate op-amp or gate pixel private key python quantisation queue raid ram relational operator resources rgb rom search sort sound synthesis ssd star network supercollider svg switch symmetric encryption truth table turtle graphics yenc