Deque (növbə və stekin ümumiləşməsi) hər iki ucdan O(1) əlavə və çıxarmağa icazə verir. Bu dərsdə onun Python imkanlarına, sürüşən pəncərənin maksimumunu O(n)-də tapan monoton növbəyə, palindrom yoxlamasına və 0-1 BFS-ə baxırıq.
Deque əməliyyatları
collections.deque (collections) iki ucda append, appendleft, pop, popleft əməliyyatlarını O(1)-də yerinə yetirir. Ortada d[i] O(n)-dir, çünki deque bloklar zənciridir. list ilə fərqi: əvvəldən əlavə və çıxarma orada O(n)-dir (cədvəl).
from collections import deque
d = deque([2, 3])
d.append(4)
d.appendleft(1)
print(d, d[0], d[-1])
print(d.pop(), d.popleft(), len(d))
d.extend([7, 8])
d.extendleft([0, -1])
print(d)deque([1, 2, 3, 4]) 1 4
4 1 2
deque([-1, 0, 2, 3, 7, 8])