Kuyruk ve `deque`

Bazı problemlerde en son gelenin değil, ilk gelenin önce işlenmesi gerekir. Banka sırası, yazdırma kuyruğu, müşteri talepleri ve görev planlama bu davranışa örnektir. Bu veri modeline kuyruk (queue) denir.

Bu hafta kuyruk davranışını FIFO (First In, First Out) ilkesiyle inceleyecek ve Python’da bu iş için neden collections.deque yapısının uygun olduğunu göreceğiz.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

FIFO ilkesini açıklayabilmeli,
enqueue ve dequeue işlemlerini yorumlayabilmeli,
collections.deque ile kuyruk oluşturabilmeli,
list.pop(0) yerine neden deque.popleft() tercih edildiğini maliyet açısından açıklayabilmeli,
basit hizmet/görev kuyruğu simülasyonu yapabilmeli,
boş kuyruk durumunu yönetebilmeli,
BFS kavramının kuyrukla ilişkisini tanıma düzeyinde açıklayabilmelisiniz.

2 FIFO: ilk giren ilk çıkar

FIFO (First In, First Out), önce gelen öğenin önce çıkarılması demektir.

flowchart LR
    A["Giriş"] --> B["Ayşe"] --> C["Bora"] --> D["Cem"] --> E["Çıkış"]

Bir kuyruğun temel işlemleri:

Soyut işlem	Anlamı	`deque` ile
enqueue	kuyruğun sonuna ekle	`queue.append(x)`
dequeue	kuyruğun başından çıkar	`queue.popleft()`
front/peek	sıradaki elemana bak	`queue[0]`
boş mu?	eleman var mı?	`not queue`

3 Neden normal liste değil?

İlk akla gelen çözüm şu olabilir:

queue = []
queue.append("Ayşe")
queue.append("Bora")
first = queue.pop(0)

Bu kod doğrudur, fakat listenin başından eleman çıkarıldığında kalan elemanların konumları kaydırılır. Veri büyüdükçe bu işlem pahalılaşır.

Python standart kütüphanesindeki deque, iki uçtan ekleme ve çıkarma için tasarlanmıştır.

4 `deque` ile ilk kuyruk

#| edit: false
#| completion: false
from collections import deque

queue = deque()
queue.append("Ayşe")
queue.append("Bora")
queue.append("Cem")

print("Kuyruk:", list(queue))
print("Sıradaki:", queue[0])
print("Hizmet alan:", queue.popleft())
print("Kalan:", list(queue))

deque çıktısını bazı örneklerde daha sade görmek için list(queue) dönüşümü kullanıyoruz; kuyruk yine deque olarak kalır.

5 Yığın ile kuyruk arasındaki fark

Aynı üç öğeyi iki yapıda kullanalım:

#| edit: false
#| completion: false
from collections import deque

stack = []
queue = deque()

for item in ["A", "B", "C"]:
    stack.append(item)
    queue.append(item)

print("Yığından çıkan:", stack.pop())
print("Kuyruktan çıkan:", queue.popleft())

Aynı ekleme sırası olmasına rağmen:

yığın → C,
kuyruk → A

çıkarır. Veri yapısının davranışı, problemin anlamını değiştirir.

6 Hizmet kuyruğu simülasyonu

#| edit: false
#| completion: false
from collections import deque

customers = deque(["Ayşe", "Bora", "Cem"])

while customers:
    customer = customers.popleft()
    print(customer, "işleniyor")

print("Kuyruk boş")

Bu örnekte while customers: ifadesi, kuyruk boşalana kadar devam eder.

7 Alıştırma — yazdırma kuyruğu

Aşağıdaki fonksiyon, iş isimlerini verilen sırayla işlemeli ve işlenenleri processed listesinde döndürmelidir.

#| exercise: hafta06-print-queue
#| completion: false
#| persist: true
from collections import deque

def process_jobs(jobs):
    queue = deque(jobs)
    processed = []

    while queue:
        # Sıradaki işi kuyruktan çıkarıp processed listesine ekleyin.
        pass

    return processed

print(process_jobs(["rapor.pdf", "notlar.pdf", "form.pdf"]))

#| exercise: hafta06-print-queue
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("process_jobs")
    correct = (
        callable(fn)
        and fn(["a", "b", "c"]) == ["a", "b", "c"]
        and fn([]) == []
        and fn(["tek"]) == ["tek"]
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Görevler FIFO sırasıyla işlendi."}
    if correct
    else {"correct": False, "message": "queue.popleft() ile sıradaki işi çıkarıp processed.append(...) ile ekleyin."}
)
feedback

Döngü içinde job = queue.popleft() ve ardından processed.append(job) kullanabilirsiniz.

Solution.

def process_jobs(jobs):
    queue = deque(jobs)
    processed = []

    while queue:
        job = queue.popleft()
        processed.append(job)

    return processed

8 Kuyrukta yeni işler gelebilir

Gerçek kuyruklarda işleme devam ederken yeni işler de eklenebilir:

#| edit: false
#| completion: false
from collections import deque

queue = deque(["A", "B"])

current = queue.popleft()
print("İşlendi:", current)

queue.append("C")
print("Yeni kuyruk:", list(queue))

while queue:
    print("İşlendi:", queue.popleft())

Kuyruk, sırayı koruyarak dinamik biçimde büyüyebilir ve küçülebilir.

9 `deque` iki uçlu bir yapıdır

Adındaki double-ended queue ifadesi, iki uçtan da işlem yapılabildiğini anlatır:

#| edit: false
#| completion: false
from collections import deque

d = deque([20, 30])
d.append(40)
d.appendleft(10)

print(list(d))
print("soldan:", d.popleft())
print("sağdan:", d.pop())
print(list(d))

Bu özellik, hem kuyruk hem de bazı yığın benzeri kullanımlar için deque’i esnek hâle getirir.

10 Sınırlı uzunlukta `deque`

maxlen parametresi, yalnızca son n öğeyi tutmak için yararlıdır:

#| edit: false
#| completion: false
from collections import deque

recent = deque(maxlen=3)

for value in [10, 20, 30, 40, 50]:
    recent.append(value)
    print(list(recent))

Bu davranış örneğin “son üç ölçüm” veya “son beş olay” gibi problemlerde kullanılabilir.

11 Mini simülasyon: tek gişe

Bir gişede her turda bir müşteri işleniyor; bazı turlarda yeni müşteri geliyor:

#| edit: false
#| completion: false
from collections import deque

queue = deque(["M1", "M2"])
new_arrivals = {
    1: "M3",
    3: "M4",
}

for minute in range(5):
    print("Dakika", minute)

    if minute in new_arrivals:
        queue.append(new_arrivals[minute])
        print("  Geldi:", new_arrivals[minute])

    if queue:
        print("  İşlendi:", queue.popleft())
    else:
        print("  Bekleyen yok")

    print("  Kuyruk:", list(queue))

Bu tür simülasyonlarda kuyruk veri modelinin problemle doğrudan eşleştiğini görebilirsiniz.

12 Maliyet sezgisi

Python listesinde:

append() → sona ekleme çoğu durumda ucuz,
pop() → sondan çıkarma çoğu durumda ucuz,
pop(0) → baştan çıkarma, elemanları kaydırdığı için O(n) sezgisi taşır.

deque ise iki uçtan ekleme/çıkarma için tasarlanmıştır; append(), appendleft(), pop() ve popleft() işlemleri bu kullanımda uygundur.

Important

Bir yapı “kuyruk olarak kullanılabilir” diye her gerçekleştirim eşit derecede uygun değildir. Doğruluk kadar işlem maliyeti de veri yapısı seçimimizin parçasıdır.

13 Kavram köşesi: BFS

Breadth-First Search (BFS), ağaç veya graf üzerinde önce yakın komşuları, sonra daha uzaktakileri inceleyen bir arama yaklaşımıdır. Bu davranış kuyrukla ilişkilidir: daha önce keşfedilen düğümler önce işlenir.

Bu derste graf temsili ve BFS kodlaması zorunlu kapsamda değildir. Hatırlanması gereken bağlantı:

BFS → FIFO → kuyruk

14 Hangi yapı?

Problem	Daha doğal model
Undo geçmişi	yığın
Tarayıcıda geri gitme	yığın
Banka müşteri sırası	kuyruk
Yazdırma işleri	kuyruk
Son üç ölçümü saklama	`deque(maxlen=3)`
Parantez eşleştirme	yığın

15 Bölüm özeti

Kuyruk FIFO ilkesine göre çalışır.
Python’da genel amaçlı FIFO kuyruk için collections.deque uygundur.
popleft() ile baştan çıkarma yapılır.
Normal listede pop(0) doğru olsa da büyük veride daha pahalıdır.
Yığın ve kuyruk aynı öğeler üzerinde farklı çıkarma sırası uygular.
deque iki uçtan işlem yapabilir ve maxlen ile sınırlı geçmiş tutabilir.
BFS’nin temel davranışı kuyruk fikriyle ilişkilidir.

16 Kendinizi kontrol edin

FIFO ne demektir?
list.pop(0) yerine neden deque.popleft() tercih edilir?
Yığın ve kuyruk arasındaki temel sıra farkı nedir?
deque(maxlen=3) hangi tür problemlerde işinize yarar?
BFS ile kuyruk arasındaki ilişkiyi bir cümleyle açıklayın.

1 Bu hafta neleri yapabilmelisiniz?

2 FIFO: ilk giren ilk çıkar

3 Neden normal liste değil?

4 deque ile ilk kuyruk

5 Yığın ile kuyruk arasındaki fark

6 Hizmet kuyruğu simülasyonu

7 Alıştırma — yazdırma kuyruğu

8 Kuyrukta yeni işler gelebilir

9 deque iki uçlu bir yapıdır

10 Sınırlı uzunlukta deque

11 Mini simülasyon: tek gişe

12 Maliyet sezgisi

13 Kavram köşesi: BFS

14 Hangi yapı?

15 Bölüm özeti

16 Kendinizi kontrol edin

4 `deque` ile ilk kuyruk

9 `deque` iki uçlu bir yapıdır

10 Sınırlı uzunlukta `deque`