Veri Yapıları #07 | Kuyruk: İlk Giren İlk Çıkar — Dairesel Dizi, Bağlı Liste ve Josephus

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin yedinci videosu. Beş yerlik bir dizide kuyrukta yalnızca 2 eleman varken 60 eklenemiyor: dizide boş yerler var ama kuyruk dolu görünüyor. Nedenini bulup kuyruğu doğru kuruyoruz. Kuyruk, elemanların arkadan girip önden çıktığı bir listedir: ilk giren ilk çıkar (FIFO). Ekleme (enqueue), çıkarma (dequeue) ve öne bakma işlemlerini kuyruk.h arayüzüne yazıyoruz. Düz dizide çıkarmanın iki yolu var: her çıkarmada herkesi sola kaydırmak (on bin eleman için 49 995 000 kayma, yani N·(N−1)/2) ya da yalnızca önü ilerletmek (bu kez baştaki yerler bir daha kullanılmıyor). Çözüm dairesel dizi: arka ve ön, mod ile başa döner; dolu ve boş kuyrukta ön ile arka aynı yerlerde durduğu için eleman sayısı (boy) ayrıca tutulur. Dairenin içini gerçek bir izle adım adım takip ediyoruz: düz dizide eklenemeyen 60, burada boşalan ilk yere giriyor. Ardından kuyruğu bağlı listeyle kuruyoruz: ön listenin başı, arka sonu; son eleman çıkınca arka da NULL yapılmalı. Aynı deneme programı iki gerçekleştirmede de aynı çıktıyı veriyor. 4. dersteki Josephus (sıcak patates) problemini bu kez kuyrukla çözüyor ve aynı sonucu buluyoruz: kazanan 4. Son olarak kuyruğun kullanıldığı yerleri görüyoruz: yazıcı kuyruğu, klavye arabelleği ve işletim sisteminin hazır kuyruğu (round robin). Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Kuyruk soyut veri tipi: ekleme (enqueue), çıkarma (dequeue), ön; FIFO 2. Düz dizinin sorunu: kaydırmanın bedeli ve kaybolan yerler 3. Dairesel dizi: mod ile başa dönme, boy alanı 4. Bağlı listeyle kuyruk: ön ve arka işaretçileri 5. Josephus problemi ve kuyruğun kullanım alanları Bölümler: 0:00 Kuyruk: ilk giren ilk çıkar 0:15 Boş yer var, kuyruk dolu görünüyor 0:45 Ekleme, çıkarma, ön: FIFO 1:13 Düz dizide çıkarmanın iki yolu 2:03 Dairesel dizi 2:43 Dairenin içini izlemek 3:09 Bağlı listeyle kuyruk 3:39 Josephus, bu kez kuyrukla 4:12 Kuyruğun kullanım alanları 4:42 Bugünün dört kuralı 5:04 Sonraki ders: ağaçlar Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.7 (kuyruk modeli, dizi ile dairesel gerçekleştirme, uygulamalar). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar ve örnekler C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C ve bu serinin 3.–6. dersleri (bağlı liste, dairesel liste, yığın).