Kuyruk ve deque

Bazı problemlerde en son gelenin değil, ilk gelenin önce işlenmesi gerekir. Banka sırası, yazıcıya gönderilen belgeler, müşteri talepleri ve sırayla çalıştırılacak görevler 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,
  • Kuyruğa ekleme (enqueue) ve kuyruktan çıkarma (dequeue) işlemlerini açıklayabilmeli,
  • collections.deque ile kuyruk oluşturabilmeli,
  • list.pop(0) yerine neden deque.popleft() tercih edildiğini maliyet açısından açıklayabilmeli,
  • Basit bir hizmet ya da görev kuyruğunun simülasyonunu yazabilmeli,
  • Kuyruktan eleman çıkarmadan önce kuyruğun boş olup olmadığını kontrol edebilmeli,
  • BFS’nin kuyrukla ilişkisini ana hatlarıyla 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ğru çalışır. Ama listenin başından eleman çıkarınca kalan bütün elemanlar birer konum kayar. Liste uzadıkça bu işlem pahalılaşır.

Python’ın standart kütüphanesindeki deque (çift uçlu kuyruk), iki uçtan da ekleme ve çıkarma için yazılmıştır.

4 deque ile ilk kuyruk

Bazı örneklerde çıktı sade görünsün diye list(queue) yazıyoruz. Bu yalnızca yazdırmak için bir liste oluşturur; queue yine deque olarak kalır.

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

Aynı üç öğeyi hem yığına hem kuyruğa ekleyelim:

Ekleme sırası aynı olduğu hâlde yığından C, kuyruktan A çıkar. Hangi öğenin önce çıkacağını veri yapısı belirler.

6 Hizmet kuyruğu simülasyonu

Bu örnekte while customers: döngüsü kuyruk boşalana kadar sürer.

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

Aşağıdaki fonksiyon, yazdırma işlerini geldikleri sırayla işlemeli ve işlediklerini processed listesinde döndürmeli.

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

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şler sürerken yeni işler de gelebilir:

Kuyruk, sırayı bozmadan program çalışırken büyüyüp küçülebilir.

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

deque adı double-ended queue (çift uçlu kuyruk) sözünden gelir: iki uçtan da ekleme ve çıkarma yapılabilir.

Bu yüzden deque’i kuyruk gibi de, yığın gibi de kullanabiliriz.

10 Sınırlı uzunlukta deque

maxlen parametresiyle yalnızca son n öğeyi tutan bir deque oluşturabiliriz. Yer dolunca her yeni öğe eklendiğinde en eski öğe öbür uçtan düşer:

Bu, “son üç ölçüm” ya da “son beş olay” gibi problemlerde işe yarar.

11 Mini simülasyon: tek gişe

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

Bu simülasyondaki kuyruk, gişe önündeki gerçek sıranın aynısıdır: önce gelen önce işlenir.

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).

deque ise iki uçtan ekleme ve çıkarma için yazılmıştır; append(), appendleft(), pop() ve popleft() iki uçta da ucuzdur.

Important

Liste de deque de kuyruk olarak çalışır, ama ikisi bu iş için aynı ölçüde uygun değildir. Veri yapısı seçerken kodun doğru çalışmasına olduğu kadar işlem maliyetine de bakarız.

13 Kavram köşesi: BFS

Genişlik öncelikli arama (breadth-first search, BFS), bir ağaçta ya da grafta önce yakın komşulara, sonra daha uzaktakilere bakan bir arama yöntemidir. Kuyrukla ilişkisi şurada: önce bulunan düğümler önce işlenir.

Bu derste graf ya da BFS kodu yazmanız beklenmiyor. Aklınızda kalması gereken bağlantı şu:

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.
  • Listede pop(0) doğru çalışır, ama büyük veride pahalıdır.
  • Aynı öğeler eklendiğinde yığın ve kuyruk onları farklı sırayla çıkarır.
  • deque’e iki uçtan da ekleyip çıkarabiliriz; maxlen ile yalnızca son birkaç öğeyi tutabiliriz.
  • BFS önce bulduğunu önce işlediği için kuyrukla çalışır.

16 Kendinizi kontrol edin

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