preface

A double-enqueued deque supports adding and removing elements from either end. Among them, the stack and the queue are the degenerate form of the two-ended queue, and their input and output are limited at one end.

Basic usage

First, let’s look at the basic use of the container collections.deque() function. The specific code is as follows:

import collections

c = collections.deque('abcdefg')
print("Output dual-end queue:", c)
print("Length of the two-endian queue:".len(c))
print(Front-end value:, c[0])
print("End value:", c[-1])
Copy the code

After running, the effect is as follows:

fill

Because it is a double-endian queue, the queue supports adding or removing elements from either end. Next, we will implement the operation of adding and deleting at both ends respectively. The specific code is as follows:

import collections

c = collections.deque()
# Initialize without constructor
c.extend("abcdefg")
# Right end (end) add
c.append('h')
print(c)
Add left (front) add
c.extendleft('i')
print(c)
# Delete at end
c.pop()
print(c)
# Front end delete
c.popleft()
print(c)
# Delete at will
c.remove('c')
print(c)
Copy the code

After running, the effect is as follows:

As with the list array, append is used. By default append starts at the right end (the end). If you want to start with the front end, you can use the extendleft() function. Deletes can be started from the right end (the end) and popleft() from the left using the pop() function. For arbitrary deletion, use remove().

Thread safety

Dual-ended queues are thread-safe, and in practice they can be consumed from both ends of the queue in different threads. The specific code is as follows:

import collections
import threading
import time

def getItem(lor, method) :
    while True:
        try:
            next = method()
        except IndexError:
            break
        else:
            print("{0}, {1}".format(lor, next))
            time.sleep(0.1)
    print('{0}:None'.format(lor))
    return

c = collections.deque("abcdefg")
t1 = threading.Thread(target=getItem, args=('Left', c.popleft))
t2 = threading.Thread(target=getItem, args=('Right', c.popleft))
t1.start()
t2.start()
t1.join()
t2.join()
Copy the code

After running, the effect is as follows:

In the above code, the two threads alternately delete elements until the double-enqueued deque is empty. As you can see, no duplicate elements have been removed.

rotating

Another useful aspect of a double-enqueued deque is that it can be rotated in either direction to skip some elements.

For example, rotating the deque double-ended queue to the right (using a positive rotation value) takes elements from the right and moves them to the left. Similarly, rotation to the left (negative) moves the element from the left to the right.

Let’s look at one end of the code and it makes sense:

import collections

a = collections.deque("abcdefg")
b = collections.deque("abcdefg")
c = collections.deque("abcdefg")
print(a)
b.rotate(2)
print(b)
c.rotate(2 -)
print(c)
Copy the code

After running, the effect is as follows:

As you can see, the first two letters of B have been moved to the front. The first two letters of C are moved to the back.

Limit the size of the dual-end queue

In an actual dual-enqueued operation, we can set the maximum length of the dual-enqueued deque instance so that it does not exceed this size. This operation is useful for finding the last n elements in a stream of uncertain length.

Let’s look at some code first:

import collections
import random

c1 = collections.deque(maxlen=5)
c2 = collections.deque(maxlen=3)

for i in range(8):
    r = random.randint(1.100)
    print(r)
    c1.append(r)
    c2.append(r)
print(c1)
print(c2)
Copy the code

After running, the effect is as follows:

From the above code, we realize that if we set the maximum length of the dual-endian deque, the length will never change no matter how much data you add. At the same time, additional data will be added in order to replace the first (left) value.