List based queues

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

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