The deque is implemented as a doubly-linked list and this makes it fast, i.e. O(1) or constant time, to work at the right and left ends as there are pointers to each end. Away from the ends accessing an element involves following pointers from the initial element to the target element and takes longer, i.e. O(n) or the time increases with n, where n is the length of the deque.
By default the deque is created in an unlimited form and will grow as you add elements. If you specify maxlen in the constructor the deque is limited to that number of elements. The deque will grow to maxlen elements and if you add more the same number of elements are removed from the other end. This allows the deque to be used as a circular buffer where elements are added at the front and lost from the back if the number of elements exceeds the specified size limit, for example:
In this case the deque is limited to three elements. After adding A, B and C adding D causes A to “drop off” the end of the deque and hence the print displays:
deque(['B', 'C', 'D'], maxlen=3)
Typically a circular buffer is used when you can’t process data as fast as it comes in and have to abandon items that have been waiting too long. Depending on which end of the circular buffer you take elements from, you can choose to prioritize either the elements that have been waiting longest or those that have just arrived. You can also use the rotate method to get any element of the deque to the left- or right-hand end where it can be popped, i.e. removed.
In chapter but not in this extract
Named Tuples
Counter
Binary Tree
Complete Listing
Summary
The LIFO stack is a fundamental data structure and it can be implemented using a Python list.
The key feature of a LIFO stack is that it reverses the order of items added to it.
The queue, or FIFO stack, is also fundamental and it too can be implemented using a Python list, or more efficiently using a Python deque.
A queue does not change the order of items added to it.
A double-ended queue or deque is implemented using the Python deque.
A deque has characteristics of a LIFO and a FIFO stack.
Named tuples are similar to structs or records in other languages.
Named tuples are immutable.
The Counter is similar to what other languages call a bag or a multiset. It works like a dictionary or set, but stores the count of the number of times each element has been added.
Python does not have a standard binary tree data structure. However, adding one is easy and an excellent example of using stacks and queues.
