The Queue

The queue data structure behaves is a similar way to a queue in the real world – people join at the end and leave at the front. The first element added to the queue is the first to leave and so it is also known as a First In First Out or FIFO stack. A queue doesn’t alter the order of items and is essentially nothing more than a buffer of items waiting to be processed.

You can create the equivalent of a queue in Python using a list, but while appending an element to the end of the queue is fast, removing an element from the start is slow due to the need to move all of the elements up by one.

For example, in:

queue = []
queue.append("A")
queue.append("B")
queue.append("C")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

the three appends add the elements to the end of the list as before, but now the pop operation takes the element at the start of the list. The result is:

A
B
C

which, as can be seen, is not reversed.

A more efficient queue can be implemented using the deque object in the collections module - the reason for the name will become clear in the next section. The deque object has an append method that adds elements to the end of the queue (considered to be the right-hand end) and a popleft method which removes an element from the front of the queue (considered to be the left-hand end). Using the deque object we can implement the previous example as:

from collections import deque
queue = deque()
queue.append("A")
queue.append("B")
queue.append("C")
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())

and it displays the items in the order that they joined the queue. The deque is faster than using a list and it also has methods that allow us to implement the next data structure – the double-ended queue.

Double-Ended Queue

A double-ended queue or deque is simply a queue that can accept new elements at either its start or its end and can pop elements from both ends. It is the most general of the stack or buffer objects and is capable of being used as a LIFO or FIFO stack by simply restricting where elements can be added and removed. It is is so called both as an abbreviation of double-ended queue and in reference to a deck of cards where you can place or take a card from either the top or the bottom of the deck.

The methods related to adding and removing elements from a deque are:

• append append to the right

• appendleft append to the left

• pop remove from the right

• popleft remove from the left-hand

Using these we can implement a LIFO stack by only using append and pop:

from collections import deque
stack = deque()
stack.append("A")
stack.append("B")
stack.append("C")
print(stack.pop())
print(stack.pop())
print(stack.pop())

and we have already used a deque to implement a simple queue in the previous section.

As well as the simple append and pop methods there are also:

• clear()
  removes all elements

• copy()
  creates a shallow copy

• count(x)
  counts the number of elements equal to x

• extend(iterable)
  extends the right side by appending elements in the iterable

• extendleft(iterable)
  extends the left side by appending elements in the iterable

• index(x[, start[, stop]])
  returns the position of x in the index (at or after start and before stop) and reports the first match or raises ValueError if not found

• insert(i, x)
  inserts x at position i

• remove(value)
  removes the first occurrence of value and if not found, raises a ValueError

• Reverse()
  reverses the elements in-place

• rotate(n = 1)
  rotates n steps to the right or the left if n is negative

• Maxlen
  reports maximum size or None if unbounded.

You can also use the deque as if it was a limited form of sequence, which means you can use in and indexing, but not slicing.