Deques

Double-ended queues, or deques (usually pronounced decks), are list-like objects that support thread-safe, memory-efficient appends. Deques are mutable and support some of the operations of lists, such as indexing. Deques can be assigned by index, for example, dq[1] = z; however, we cannot directly slice deques. For example, dq[1:2] results in a TypeError (we will look at a way to return a slice from a deque as a list shortly).

The major advantage of deques over lists is that inserting items at the beginning of a deque is much faster than inserting items at the beginning of a list, although inserting items at the end of a deque is very slightly slower than the equivalent operation on a list. Deques are thread, safe and can be serialized using the pickle module.

A useful way of thinking about deques is in terms of populating and consuming items. Items in deques are usually populated and consumed sequentially from either end:

We can use the pop() and popleft() methods for consuming items in the deque, for example:

We can also use the rotate(n) method to move and rotate all items of n steps to the right for positive values of the integer n, or left for negative values of n the left, using positive integers as the argument, for example:

Note that we can use the rotate and pop methods to delete selected elements. Also worth knowing is a simple way to return a slice of a deque, as a list, which can be done as follows:

The itertools.islice method works in the same way that slice works on a list, except rather than taking a list for an argument, it takes an iterable and returns selected values, by start and stop indices, as a list.

A useful feature of deques is that they support a maxlen optional parameter that restricts the size of the deque. This makes it ideally suited to a data structure known as a circular buffer. This is a fixed-size structure that is effectively connected end to end and they are typically used for buffering data streams. The following is a basic example:

dq2=deque([],maxlen=3) 
for i in range(6): 
    dq2.append(i) 
    print(dq2) 

This prints out the following:

In this example, we are populating from the right and consuming from the left. Notice that once the buffer is full, the oldest values are consumed first, and values are replaced from the right. We will look at circular buffers again in Chapter 4, Lists and Pointer Structures, by implementing circular lists.