A double-ended queue, or dequeue, supports adding and removing elements from either end of the queue.



In [2]:

    
import collections

d = collections.deque('abcdefg')
print('Deque:', d)
print('Length:', len(d))
print('Left end:', d[0])
print('Right end:', d[-1])

# !! c is not at either end of queue
d.remove('c')
print('remove(c):', d)









    



Deque: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
Length: 7
Left end: a
Right end: g
remove(c): deque(['a', 'b', 'd', 'e', 'f', 'g'])

Populating

A dequeue can be populated from either end, termed "left" and "right" in the python implementation



In [4]:

    
import collections

# Add to the right
d1 = collections.deque()
d1.extend('abcdefg')
print('extend    :', d1)
d1.append('h')
print('append    :', d1)

# Add to the left
d2 = collections.deque()
d2.extendleft(range(6))
print('extendleft:', d2)
d2.appendleft(6)
print('appendleft:', d2)









    



extend    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
append    : deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
extendleft: deque([5, 4, 3, 2, 1, 0])
appendleft: deque([6, 5, 4, 3, 2, 1, 0])

extend, extendleft, append, appendleft

difference between extend and append is same as list

insert(x,i)

Insert an element at position i

Consuming and Modifying

Similarly, the elements of the dequeue can be consumed from both ends or either end.



In [5]:

    
import collections

print('From the right:')
d = collections.deque('abcdefg')
while True:
    try:
        print(d.pop(), end='')
    except IndexError:
        break
print()

print('\nFrom the left:')
d = collections.deque(range(6))
while True:
    try:
        print(d.popleft(), end='')
    except IndexError:
        break
print()









    



From the right:
gfedcba

From the left:
012345

pop(), popleft()

Remove and return an element from the right side of the deque.

remove

remove the first occurence of a value|

clear

Remove all the elements from the deque leaving it with length 0

Rotating and Reversing

rotate(n)

rotate the deque n steps to the right. if n is negtive, rotate to he left. Rotating one step to the right is equivalent to: d.appendleft(d.pop())



In [6]:

    
import collections

d = collections.deque(range(10))
print('Normal        :', d)

d = collections.deque(range(10))
d.rotate(2)
print('Right rotation:', d)

d = collections.deque(range(10))
d.rotate(-2)
print('Left rotation :', d)









    



Normal        : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Right rotation: deque([8, 9, 0, 1, 2, 3, 4, 5, 6, 7])
Left rotation : deque([2, 3, 4, 5, 6, 7, 8, 9, 0, 1])

reverse()



In [7]:

    
import collections

d = collections.deque(range(10))
print('Normal        :', d)

d.reverse()
print('Reverse       :', d)









    



Normal        : deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
Reverse       : deque([9, 8, 7, 6, 5, 4, 3, 2, 1, 0])

Constraining the Queue Size

A dequeue can be configured with a maximum length so that it never grows beyond that size. When the queue reaches the specified length, existing items are discarded as new items are added. This behavior is useful for finding the last n items in a stream of undetermined length.



In [10]:

    
import collections
import random

# Set the random seed so we see the same output each time
# the script is run.
random.seed(1)

d1 = collections.deque(maxlen=3)
d2 = collections.deque(maxlen=3)

for i in range(5):
    n = random.randint(0, 100)
    print('n =', n)
    d1.append(n)
    d2.appendleft(n)
    print('D1 append     :', d1)
    print('D2 append left:', d2)









    



n = 17
D1 append     : deque([17], maxlen=3)
D2 append left: deque([17], maxlen=3)
n = 72
D1 append     : deque([17, 72], maxlen=3)
D2 append left: deque([72, 17], maxlen=3)
n = 97
D1 append     : deque([17, 72, 97], maxlen=3)
D2 append left: deque([97, 72, 17], maxlen=3)
n = 8
D1 append     : deque([72, 97, 8], maxlen=3)
D2 append left: deque([8, 97, 72], maxlen=3)
n = 32
D1 append     : deque([97, 8, 32], maxlen=3)
D2 append left: deque([32, 8, 97], maxlen=3)