List based queues

By Martin McBride, 2018-05-05
Tags: queue list based queue
Categories: data structures

A queue can be created from a list. Since a list is a dynamic data structure, the queue created will also be dynamic.

Implementing a queue based on a list is fairly simple. In the list below, element 0 (value 7) represents the front of the queue. Element 2 (value 9) is the back of the queue.

[7, 4, 9]

To enQueue an item (add it to the back of the queue), we just append it to the end of the list. Here we have added value 3 to the queue:

[7, 4, 9, 3]

To deQueue an item (take it from the front of the queue), we must first make a note of the value at the front of the queue (the start of the list, which is always element 0). In this case the value is 7.

We them remove item 0 from the list, and return the previous value, 7. This leaves the list looking like this:

[4, 9, 3]

Since we are adding and removing elements quite frequently, a [[linked lists|linked list]] is a good choice for the list to use for implementing a queue. However, any list will work, it just might not be quite as efficient.

Python implementation

Here is a list based queue in Python. It is for illustration only, you should use the collections.deque implementation if you want an efficient queue in Python.

queue = []

def enQueue(v):
    queue.append(v)

def isEmpty():
    return len(queue)==0

def deQueue():
    if isEmpty():
        print('Error queue is empty')
    else:
        return queue.pop(0)

Here, we define a global list called queue to hold the queue elements.

To enQueue we simply append the value to the end of the list.

To check isEmpty, we test if the list has a length of 0.

To deQueue an element, we use pop(0) which removes element 0 but also returns its value.

Note that Python lists use an array list implementation of lists. Array lists are quite slow at adding and removing elements, so they are not very efficient for implementing queues.

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