List based queues

From Schoolcoders wiki
Jump to: navigation, search
Level: A Level Computing

A queue data structure 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, 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, 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 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):

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

def deQueue():
    if isEmpty():
        print('Error queue is empty')
        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, so they are not very efficient for implementing queues.

See also