Deque

Çift Uçlu Kuyruk

Okunuşu: dek

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Deque, hem önden hem arkadan sabit sürede öğe eklemeye ve çıkarmaya izin veren çift uçlu bir kuyruktur; hem yığın hem kuyruk gibi davranabilir.

Deque nedir?

Çift uçlu kuyruk (double-ended queue) anlamına gelen ve deck gibi telaffuz edilen deque, her iki uçtan da öğe eklemeyi ve çıkarmayı destekleyen bir dizilimdir. Dört temel işlemi öne ekleme ve önden çıkarma ile arkaya ekleme ve arkadan çıkarmadır; her biri O(1) sürer. Yığının ve kuyruğun yapabildiği her şeyi yapabildiği için, iki uca da hızlı erişime ihtiyaç duyduğunuzda deque çoğu zaman en esnek seçimdir.

Deque'ler genellikle iki yoldan biriyle kurulur. Çift yönlü bağlı liste ya da Python'ın collections.deque yapısındaki gibi sabit boyutlu blokların bağlı bir zinciri, hiçbir şeyi kaydırmadan iki ucun da büyümesine izin verir. Dairesel tampon, yani başı ve sonu başa saran bir dizi, öğeleri bellekte bir arada tutar ve dolduğunda daha büyük bir diziye kopyalanarak büyür; Java'nın ArrayDeque ve Rust'ın VecDeque yapıları bunu yapar. Bağlı tasarımlarda ortadaki öğelere ulaşmak uçlardakilerden daha yavaştır, O(n); dairesel tamponlar ise yine de O(1)'de indeksleyebilir.

Masanın üzerinde, desteden yalnızca üstten ya da alttan kart alıp ekleyebildiğiniz, ortadan asla alamadığınız bir kart destesi düşünün. Deque'ler, son k öğeyi tutan ya da kayan bir maksimumu izleyen kayan pencere algoritmalarında, boyut sınırı olan geri alma geçmişlerinde ve her iş parçacığının kendi deque'sinin bir ucundan görev aldığı, boştaki iş parçacıklarının ise diğer uçtan görev çaldığı iş çalma (work-stealing) zamanlayıcılarında kullanılır. Python'da collections.deque, sıradan bir kuyruk kurmak için de önerilen yoldur.

Deque, bir kuyruktan öğe çıkarma işleminin adı olan dequeue sözcüğüyle kolayca karıştırılır. Ayrıca Python list ya da JavaScript dizisi gibi sıradan dinamik dizilerden de farklıdır: bunlar arkada hızlı, önde yavaştır, çünkü 0 indeksinde ekleme ya da silme diğer tüm öğeleri kaydırır ve bu O(n) sürer. Yalnızca arkaya ekleyen ve önden çıkaran kuyrukla karşılaştırıldığında deque bu kısıtı basitçe kaldırır.

Önemli noktalar

Deque hem önden hem arkadan O(1) sürede ekleme ve çıkarmayı destekler.
Yığın, kuyruk ya da ikisi birden olarak davranabilir.
Genellikle çift yönlü bağlı liste ya da dairesel tampon üzerine kurulur.
Python'da appendleft() ve popleft() içeren collections.deque, list.pop(0)'ın O(n) maliyetinden kaçınır.
Deque veri yapısıdır; dequeue ise bir kuyruktan öğe çıkarma işlemidir.

Örnek

Python'da bir deque'in iki ucunu da kullanmakpython

from collections import deque

d = deque([2, 3])
d.appendleft(1)     # add at the front: O(1)
d.append(4)         # add at the back: O(1)
print(d)            # deque([1, 2, 3, 4])
print(d.popleft())  # remove from the front: 1
print(d.pop())      # remove from the back: 4

# With maxlen, the deque keeps only the most recent items
recent = deque(maxlen=3)
for page in ["home", "docs", "pricing", "blog"]:
    recent.append(page)  # the oldest item falls off the other end
print(list(recent))  # ['docs', 'pricing', 'blog']

Sık sorulan sorular

Deque ile kuyruk arasındaki fark nedir?

Kuyruk öğeleri yalnızca arkaya ekler ve yalnızca önden çıkarır. Deque ise iki işleme de iki uçta izin verir; bu yüzden kuyruk, yığın ya da ikisinin karışımı gibi davranabilir.

Deque nasıl telaffuz edilir?

Genellikle deck gibi telaffuz edilir. Bu, bir kuyruktan öğe çıkarma işlemi olan ve dee-cue diye telaffuz edilen dequeue ile karışmayı önler.

Ne zaman liste yerine deque kullanmalıyım?

Bir kuyruktaki ya da kayan pencerelerdeki gibi öndeki öğeleri ekliyor veya çıkarıyorsanız deque kullanın. Çoğunlukla sonda çalışıyor ve ortaya indeksle hızlı erişim gerekiyorsa liste ya da dizi daha uygundur.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin