While you can simulate a stack or queue using the.append and.pop methods of Python lists, removing the first element of the list or adding a new element before the first element is time-consuming. Because you need to move all the elements in the list backwards.

Python’s bidirectional queues are implemented using the Collections. deque class. It is a thread-safe class that can quickly add or remove elements from both ends.

A deque ɛ k/d /

Caching can also be implemented using the Collections. deque class. You specify the size of the cache queue first, then remove expired elements from the front of the queue and add new elements at the back.

Luciano Ramalho gave an example to illustrate the basic use of a two-way queue.

from collections import deque

dq = deque(range(10), maxlen=10)
logging.info('dq -> %s', dq)

dq.rotate(3)
logging.info('dq -> %s', dq)

dq.rotate(-4)
logging.info('dq -> %s', dq)

dq.extend([11, 22, 33])
logging.info('dq -> %s', dq)

dq.extendleft([10, 20, 30, 40])
logging.info('dq -> %s', dq)

Copy the code

Running results:

INFO - dq -> deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], maxlen=10)
INFO - dq -> deque([7, 8, 9, 0, 1, 2, 3, 4, 5, 6], maxlen=10)
INFO - dq -> deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 0], maxlen=10)
INFO - dq -> deque([4, 5, 6, 7, 8, 9, 0, 11, 22, 33], maxlen=10)
INFO - dq -> deque([40, 30, 20, 10, 4, 5, 6, 7, 8, 9], maxlen=10)
Copy the code
  1. Maxlen is an optional parameter to the deque that specifies the queue capacity, that is, how many elements can be placed.
  2. The rotate() method rotates the queue. It has an entry parameter, n, and when n >0, the n elements from the right end of the queue are moved to the left. When n <0, the n elements from the left end of the queue are moved to the right.
  3. The extend() method adds new elements to the queue by taking a list as an entry and adding all the elements from the list to the queue. The new element is placed to the right of the queue.
  4. If the queue is full while adding a new element, the element at the head of the queue is automatically deleted.
  5. The extendLeft (iter) method places the new element to the left of the queue. Other features are the same as the extend() method.

The two-way queue is also not perfect, and removing elements from the middle of the queue is slow because it is optimized only for the head and tail of the queue.