Bölüm 7: Kuyruklar

7.1Kuyruk nedir?

Yığın ve kuyruk, bir öğe topluluğuna erişimi bilerek kısıtlayan iki temel yapıdır. İkisinde de yalnız belirli bir uçtaki öğeye ulaşılır; ortadaki öğeler görünmez. Bu kısıtlama bir eksiklik değildir. Erişim kuralı ne kadar dar olursa yapı o kadar basit ve hızlı gerçeklenir, programın davranışı da o kadar kolay öngörülür. İki yapıyı ayıran tek şey, çıkarılacak öğenin hangisi olduğudur. Yığında en son eklenen öğe çıkar. Kuyrukta ise en uzun süredir bekleyen, yani en önce eklenen öğe çıkar.

7.1.1İlk giren ilk çıkar

Bir otobüs durağındaki sıra kuyruğun en sade örneğidir. Yeni gelen yolcu sıranın sonuna geçer. Otobüs gelince sıranın başındaki yolcu biner. Sıranın ortasına girmek ya da ortadan birini almak kurala aykırıdır. Bu düzende yolcular sıraya hangi sırayla girdiyse otobüse de o sırayla biner. Kuyruk veri yapısı bu davranışı birebir taşır.

Tanımdaki son cümle kuyruğun bütün davranışını belirler. Öğeler kuyruğa a₀, a₁, a₂ sırasıyla girdiyse kuyruktan da aynı sırayla çıkar. Yığında aynı ekleme sırası ters çıkış sırası verirdi: a₂, a₁, a₀. Yığın kuralına bu yüzden son giren ilk çıkar (LIFO) denir. Kısaca söylemek gerekirse yığın sırayı ters çevirir, kuyruk ise korur.

Şekil 7.1 boş bir kuyruğa sırasıyla A, B, C ve D'nin eklenmesini, ardından bir çıkarmayı gösterir. Boş kuyrukta ön ve arka aynı yerdedir; ortada öğe yoktur. Her eklemede arka bir hücre ilerler. Çıkarma işlemi önde duran A'yı verir, çünkü kuyruğa ilk giren odur. A çıktıktan sonra öndeki hücre boşalır ve kuyruğun yeni önü B olur. Şekilde dikkat çeken bir ayrıntı vardır: çıkarma, kalan öğeleri yerinden oynatmaz. Ön uç bir hücre sağa kayar, öğeler olduğu yerde kalır. Bu ayrıntı, dizi ile kurulan kuyruğun bütün sorunlarının ve çözümlerinin kaynağıdır.

7.1.2Kuyruk soyut veri tipi

Bir veri yapısını gerçeklemeye geçmeden önce onunla hangi işlemlerin yapılacağını ve her işlemin ne anlama geldiğini belirlemek gerekir. Bu belirleme, yapının iç düzeninden bağımsızdır. Kuyruğu kullanan bir program, öğelerin dizide mi bağlı listede mi durduğunu bilmek zorunda değildir; yalnız ekleme ve çıkarmanın ilk giren ilk çıkar kuralına uyduğunu bilmesi yeter. İşlemlerin bu biçimde, gerçeklemeden ayrı olarak verilmesine soyut veri tipi (abstract data type, ADT) denir. Tablo 7.1 kuyruk soyut veri tipinin altı işlemini verir.

Tablodaki iki hata durumunun adları yığından tanıdıktır. Dolu bir yapıya ekleme yapılmak istenirse taşma (overflow), boş bir yapıdan öğe alınmak istenirse alt taşma (underflow) olur. “Dolu” kavramı yalnız sabit boyutlu gerçeklemelerde anlam taşır. Bağlı listeyle kurulan bir kuyruk, bellek bitene kadar dolmaz. Yine de soyut veri tipi kuyruk_dolu işlemini içerir. Böylece aynı arayüz hem dizi hem bağlı liste gerçeklemesini kapsar.

Yığın ile kuyruğun farkı tabloda tek bir sözcüğe sığar: uç. Yığının tek bir etkin ucu vardır. Ekleme de çıkarma da üstte yapılır. Kuyruğun ise iki ucu vardır ve her işlem kendi ucunu kullanır: ekleme arkada, çıkarma önde yapılır. Bu fark gerçeklemeye de yansır. Yığını tek bir indisle (top) yönetmek yeter. Kuyruk ise iki indis ister: biri önü, öteki arkayı izler. Bu iki indisin birbirine göre konumu, notun geri kalanının asıl konusudur.

7.1.3Kuyruğun kullanıldığı yerler

Kuyruk, “sırası gelen hizmet alır” ilkesinin geçerli olduğu her yerde karşımıza çıkar. Bunların bir kısmı gerçek hayattaki sıraların bilgisayardaki karşılığıdır, bir kısmı ise algoritmaların iç işleyişinde kullanılır.

• İşletim sistemi. Çalışmaya hazır süreçler işlemciyi, yazıcıya gönderilen belgeler yazıcıyı, disk istekleri diski kuyrukta bekler. Bir isteğin sonradan gelip öndekileri geçmesi adaletsiz olurdu; kuyruk bu adaleti kendiliğinden sağlar.
• Tampon. Klavyeden gelen tuşlar, ağdan gelen paketler, ses kartına giden örnekler bir tampon (buffer) içinde bekler. Tampon, veriyi üreten taraf ile tüketen taraf arasında duran bir kuyruktur. İki tarafın hızı farklı olabilir: klavye bir anda birkaç tuş gönderebilir, program onları biraz sonra okur. Bu tamponlar neredeyse her zaman sabit boyutlu bir dairesel kuyruktur.
• Genişlik öncelikli arama. Bir çizgede ya da ağaçta düğümleri başlangıca uzaklık sırasıyla ziyaret eden genişlik öncelikli arama (breadth-first search, BFS) kuyruğa dayanır. İşlenen düğümün komşuları ya da çocukları kuyruğun arkasına eklenir, sıradaki düğüm önden alınır. Ağaçta aynı yöntem düğümleri düzey düzey, soldan sağa verir; buna düzey sırası (level-order) gezinme denir.
• Benzetim. Bir banka gişesinin, bir trafik ışığının ya da bir üretim hattının bilgisayarda canlandırılmasında gelen her müşteri ya da araç kuyruğa girer. Benzetim, ortalama bekleme süresi gibi soruları sistemi kurmadan cevaplamaya yarar.
• Mesaj kuyrukları. Büyük yazılım sistemlerinde sunucular birbirine işleri bir mesaj kuyruğu üzerinden iletir. İşler gönderiliş sırasıyla işlenir ve alıcı o an meşgul olsa bile kaybolmaz.

Bu listeye sık karıştırılan bir yapı da eklenmelidir. Öncelikli kuyruk (priority queue) adında “kuyruk” sözcüğü geçer, ama ilk giren ilk çıkar kuralına uymaz. Öncelikli kuyrukta her öğenin bir önceliği vardır ve her çıkarmada en yüksek öncelikli öğe alınır. Acil servisteki sıra buna iyi bir örnektir: ağır hasta, kendisinden önce gelmiş hafif hastaların önüne geçer. Öncelikli kuyruğun verimli gerçeklemesi heap adlı ağaç yapısıyla yapılır. Bu notta “kuyruk” sözcüğü, aksi söylenmedikçe, ilk giren ilk çıkar kuralına uyan sıradan kuyruğu anlatır.

Sunumda bir de etkileşimli kuyruk bulunur. Orada “ekle” düğmesi kuyruğun arkasına yeni bir öğe koyar, “al” düğmesi öndeki öğeyi çıkarır. Birkaç denemeden sonra aynı gözlem tekrar tekrar doğrulanır: çıkan öğelerin sırası, giren öğelerin sırasıyla aynıdır. Yığında bu sıra tam tersiydi.

7.2Dizi ile doğrusal kuyruk

Kuyruğu C'de kurmanın en kısa yolu, sabit boyutlu bir dizi ve iki tamsayı indis kullanmaktır. Bu kesim önce bu en basit gerçeklemeyi verir. Ardından kod izlemesiyle önemli bir kusurunu ortaya çıkarır ve kusuru gidermenin ilk, pahalı yolunu inceler.

7.2.1Gösterim ve C kodu

Yığında tek bir top indisi yeterliydi. Kuyrukta iki uç olduğu için iki indis tutulur: on ve arka. Öğeler dizinin içinde, on'dan sonraki hücreden arka'nın gösterdiği hücreye kadar yan yana durur. Aşağıdaki kod Horowitz, Sahni ve Anderson-Freed'in kitabındaki gerçeklemenin Türkçe adlandırılmış biçimidir:

#define MAX_QUEUE_SIZE 100
element kuyruk[MAX_QUEUE_SIZE];
int on = -1;        /* ilk öğenin bir öncesi */
int arka = -1;      /* son öğe */

void kuyruk_ekle(int *arka, element item) {
    if (*arka >= MAX_QUEUE_SIZE - 1)   /* yer var mı? */
        kuyruk_dolu();         /* uyar ve çık */
    kuyruk[++*arka] = item;    /* önce artır, sonra yaz */
}
element kuyruk_al(int *on, int arka) {
    if (*on == arka)
        kuyruk_bos();          /* boşsa uyar ve çık */
    return kuyruk[++*on];      /* artır ve öndekini döndür */
}

İlk satırlar kuyruğun belleğini kurar. MAX_QUEUE_SIZE dizinin hücre sayısıdır. element, kuyrukta saklanacak öğenin tipidir. Yığın gerçeklemesinde olduğu gibi bu tip programa göre bir struct olarak tanımlanır; örneğin tek bir int deger alanı taşıyabilir. kuyruk dizisi ve iki indis küresel değişkendir. Başlangıçta ikisi de −1'dir.

İki indisin anlamı dikkatle okunmalıdır, çünkü bütün kod bu anlamlara dayanır. arka, son öğenin bulunduğu hücreyi gösterir. on ise ilk öğeyi değil, ilk öğenin bir öncesini gösterir. Bu seçim ilk bakışta tuhaf görünür, ama iki işlemi de aynı biçime sokar: her iki işlem de önce kendi indisini bir artırır, sonra o hücreyi kullanır. Kuyruktaki öğeler bu yüzden kuyruk[on+1], …, kuyruk[arka] hücrelerindedir ve öğe sayısı arka − on'dur. İki indis eşitse aralık boştur: boş kuyruğun koşulu on == arka'dır. Başlangıçtaki −1 ve −1 değerleri de bu koşulu sağlar.

kuyruk_ekle önce yer olup olmadığına bakar. arka dizinin son hücresine (MAX_QUEUE_SIZE − 1) ulaştıysa arkasına yazılacak hücre kalmamıştır ve kuyruk_dolu çağrılır. Yer varsa ++*arka önce arka'yı bir artırır, ifadenin değeri de artırılmış indis olur; öğe o hücreye yazılır. kuyruk_al önce boşluğa bakar. Kuyruk boş değilse ++*on ile ön indisi, çıkarılacak öğenin hücresine ilerler ve o hücredeki öğe döndürülür.

Parametrelerin türleri bilinçli seçilmiştir. kuyruk_ekle arka'yı değiştirdiği için onu adresle, int *arka olarak alır; çağrı kuyruk_ekle(&arka, x) biçimindedir. kuyruk_al ise on'u değiştirir, arka'yı yalnız okur. Bu yüzden on'u adresle, arka'yı değerle alır. Parametre adları küresel değişkenlerin adlarıyla aynıdır. C'de bu geçerlidir: fonksiyonun içinde parametre adı küresel değişkeni gölgeler. Kodu okurken *arka'nın küresel arka'yı, çıplak arka'nın ise parametrenin kopyasını anlattığı akılda tutulmalıdır.

Kod, hata durumunda kuyruk_dolu ve kuyruk_bos fonksiyonlarını çağırır. Bu fonksiyonlar yığın gerçeklemesindeki karşılıkları gibi bir uyarı yazıp programı bitirir:

void kuyruk_dolu(void) {
    printf("Kuyruk Dolu!!!\n");  exit(-1);
}
void kuyruk_bos(void) {
    printf("Kuyruk Bos!!!\n");   exit(-2);
}

Programı bitirmek kaba bir hata yönetimidir, ama kodu kısa tutar ve öğrenmenin ilk aşamasında asıl düşünceyi öne çıkarır. Kuyruk dolu ya da boşken işleme devam edilmez; dolayısıyla kuyruk_ekle ve kuyruk_al içinde hata sonrası için ayrı bir dal gerekmez. Güvenli sürümler hata durumunda false döndürür ve kararı çağırana bırakır. Bu sürüm dairesel kuyrukta ele alınır.

Her iki işlem de bir karşılaştırma, bir artırma ve bir dizi erişimi yapar. Kuyrukta kaç öğe olduğundan bağımsız olarak sabit iş yapıldığı için iki işlemin de zaman maliyeti O(1)'dir. Kuyruk sabit boyutlu bir dizi kullanır; bellek maliyeti MAX_QUEUE_SIZE öğedir ve öğe sayısına bağlı değildir.

7.2.2Kod izleme: sahte doluluk

Doğrusal kuyruğun kusuru, kodu birkaç adım çalıştırınca görünür. İzlemede dizi küçük tutulur: MAX_QUEUE_SIZE = 4. Başlangıçta on = arka = −1'dir. İşlem sırası şöyledir: A, B ve C eklenir; iki kez öğe alınır; sonra D ve E eklenmek istenir. Öğeler tek harfli değerler olduğu için izlemede element, char olarak düşünülebilir.

İlk üç ekleme sorunsuzdur. Her birinde denetim yer olduğunu söyler, arka bir artar ve harf yeni hücreye yazılır. İki çıkarmada on önce 0'a, sonra 1'e ilerler ve sırasıyla A ile B döner. Burada önemli olan, çıkarmanın diziyi değiştirmemesidir. A ve B hâlâ 0 ve 1 numaralı hücrelerde yazılı durur, ama artık kuyruğun parçası değildir: kuyruk on+1'den başlar. Bu iki hücre fiilen boştur.

D eklendiğinde arka 3'e, yani dizinin son hücresine ulaşır. Kuyrukta yalnız iki öğe (C ve D) vardır; öğe sayısı arka − on = 3 − 1 = 2'dir. Buna karşın E eklenmek istendiğinde denetim 3 ≥ 3 sonucunu verir ve kod kuyruğu dolu sayar. Program “Kuyruk Dolu!!!” yazıp biter. Oysa dört hücreden ikisi boştur. Bu duruma sahte doluluk denir. Sorunun kaynağı, iki indisin de yalnız ileri gitmesidir. on ilerledikçe arkada bıraktığı hücreler bir daha hiç kullanılmaz. Doğrusal kuyruk, ömrü boyunca toplam MAX_QUEUE_SIZE ekleme yapabilir; aynı anda kaç öğe tuttuğu fark etmez. Örneğin 100 hücreli bir kuyruğa 60 öğe eklenip 60'ı da alınırsa kuyruk boştur. Yine de en çok 40 ekleme daha sığar; 41. ekleme “dolu” hatası verir.

7.2.3Kaydırma: pahalı çözüm

Sahte doluluğun ilk akla gelen çözümü, öğeleri dizinin başına kaydırmaktır. arka sona dayandığında önde boş hücre varsa bütün öğeler sola taşınır, on −1'e, arka da öğe sayısının bir eksiğine çekilir. Şekil 7.3 izlemedeki son durumdan başlar: on = 1, arka = 3, öğeler C ve D. Kaydırmadan sonra C 0 numaralı, D 1 numaralı hücreye geçer; on = −1, arka = 1 olur ve arkada iki hücre açılır.

Kaydırmayı kuyruk koduna eklemek kolaydır. Aşağıdaki iki fonksiyon önceki kesimdeki küresel kuyruk, on ve arka üzerinde çalışır:

void kaydir(void) {            /* öğeleri dizinin başına taşı */
    int n = arka - on;         /* öğe sayısı */
    for (int i = 0; i < n; i++)
        kuyruk[i] = kuyruk[on + 1 + i];
    on = -1;
    arka = n - 1;
}
void kuyruk_ekle_kaydir(element item) {
    if (arka == MAX_QUEUE_SIZE - 1) {
        if (on == -1) kuyruk_dolu();   /* gerçekten dolu */
        kaydir();                      /* önde yer var: O(n) */
    }
    kuyruk[++arka] = item;
}

kaydir önce öğe sayısını (n = arka − on) hesaplar. Döngü i'nci öğeyi, yani kuyruk[on+1+i] hücresindeki öğeyi, kuyruk[i]'ye taşır. Taşıma soldan sağa yapılır; hedef hücre her zaman kaynak hücrenin solunda olduğu için henüz okunmamış bir öğenin üzerine yazılmaz. Son iki atama indisleri yeni konuma çeker. kuyruk_ekle_kaydir yalnız arka sona dayandığında devreye girer. O anda on da −1 ise önde boş hücre yoktur ve kuyruk gerçekten doludur. Aksi hâlde önce kaydırma yapılır, sonra öğe her zamanki gibi eklenir. Bu sürüm sınandığında izlemedeki durum (C, D; on = 1, arka = 3) kaydırmayla on = −1, arka = 1'e geçer. Ardından E ve F sığar, G ise gerçek doluluk nedeniyle reddedilir.

Çözüm doğrudur, ama bedeli yüksektir. Kaydırma kuyruktaki n öğenin her birini bir kez taşır; maliyeti Θ(n)'dir. Kaydırma her eklemede yapılmaz, yalnız arka sona dayandığında yapılır. Ne var ki kuyruk sürekli neredeyse dolu çalışıyorsa (bir tampon için olağan bir durumdur) hemen her ekleme bir kaydırma tetikler. Kuyrukta M − 1 öğe varken bir ekleme ile bir çıkarma art arda yapılsın. Her çıkarma önde tek bir hücre açar. Bir sonraki eklemede arka yine sona dayanır ve M − 1 öğe taşınır. Böylece ekleme işlemi O(1)'den O(n)'ye çıkar.

Bu tahmin ölçümle de doğrulandı. Kuyrukta sürekli M − 1 öğe tutulurken 200 000 ekleme ve çıkarma çifti yapıldı. M = 1000 için toplam taşıma sayısı 199 799 001, M = 2000 için 399 798 001'dir; yani her eklemede yaklaşık M öğe taşınmıştır. Süreler Tablo 7.15'te verilmiştir: kaydırmalı kuyruğun süresi M ile doğru orantılı artar, dairesel kuyruğun süresi ise değişmez. Sunumda bu durum hocanın bir sözüyle anlatılır: kaydırma, bilgisayar bilimlerinde yüksek maliyetin adıdır. Kaydırmadan kurtulmanın yolu, öğeleri yerinde bırakıp indislerin dönüp dolaşmasına izin vermektir. Bu yapıya dairesel kuyruk denir.

7.3Dairesel kuyruk

Doğrusal kuyruğun sorunu, indislerin dizinin sonuna gelince durmasıdır. Dairesel kuyruk bu sınırı kaldırır: son hücreden sonra yeniden ilk hücreye geçilir. Böylece önde boşalan hücreler arkaya eklenen öğeler için kullanılır ve hiçbir öğe yerinden taşınmaz. Bu kesim fikri, onu mümkün kılan kalan işlemini, kodu ve dairesel kuyrukta dolu ile boşu ayırt etme sorununu sırasıyla ele alır.

7.3.1Dizinin sonunu başına bağlamak

Altı hücreli bir dizi düz bir şerit yerine bir halka olarak düşünülsün. 0'dan 5'e kadar numaralanmış hücreler halkanın dilimleridir ve 5 numaralı dilimin hemen ardından yeniden 0 gelir. Bellekte hiçbir şey değişmez; dizi yine düz bir bloktur. Değişen yalnız indislerin ilerleme kuralıdır. Şekil 7.4 bu halkayı gösterir: kuyrukta A, B ve C vardır, on 0'ı, arka 3'ü gösterir.

Tanımdaki dolu koşulu şunu söyler: arka bir ilerlediğinde on'un üzerine gelecekse yer yoktur. Bu koşulun bir sonucu, MAX hücreden birinin her zaman boş kalmasıdır. Kuyruk en çok MAX − 1 öğe tutar. Neden böyle olduğu, yani son hücrenin neden doldurulmadığı, dolu ile boşu ayırt etme sorununun konusudur. Şimdilik şu kadarı yeterlidir: son hücre de doldurulsaydı arka, on'a eşit olurdu. Bu da boş kuyruğun koşuluyla aynıdır ve kod dolu bir kuyruğu boş sanırdı.

7.3.2Modüler aritmetik ve sarma

İndisin halka üzerinde dönmesini sağlayan araç, C'deki kalan işleci %'dir. a % m ifadesi, a'nın m'ye bölümünden kalanı verir. Negatif olmayan a için sonuç her zaman 0 ile m − 1 arasındadır. Sayıların bu biçimde bir m değerine göre kalanlarıyla hesaplanmasına modüler aritmetik (modular arithmetic) denir. Saat bunun en tanıdık örneğidir: 11'den üç saat sonrası 14 değil, (11 + 3) mod 12 = 2'dir.

Dairesel kuyrukta arka'nın bir sonraki değeri (arka + 1) % MAX ile hesaplanır. arka son hücrede değilse bu ifade sıradan arka + 1'e eşittir. arka son hücredeyse arka + 1 = MAX olur ve kalan 0'dır: indis başa döner. Bu olaya sarma (wrap-around) denir. Tablo 7.3 MAX = 6 için dört ardışık adımı verir.

Kalan işleciyle ilgili C'ye özgü bir tuzak vardır. C standardı (C99'dan beri) tamsayı bölmesini sıfıra doğru keser. Bunun sonucu olarak negatif bir sayının kalanı da negatiftir: -1 % 6 ifadesinin değeri 5 değil, −1'dir; -2 % 6 ise −2'dir. Matematikteki mod işlemi her zaman negatif olmayan bir sonuç verir, C'nin % işleci vermez. İndisi bir geri almak gerektiğinde bu fark önem kazanır. (i − 1) % MAX ifadesi i = 0 için −1 verir ve dizinin dışına, kuyruk[-1]'e erişilir. Doğru yazım (i − 1 + MAX) % MAX'tır. MAX eklemek değeri negatif olmaktan kurtarır, kalan işlemi de sonucu yine 0 ile MAX − 1 arasına indirir: (0 − 1 + 6) % 6 = 5. Kuyrukta indis yalnız ileri gider; geri adım, iki uçtan da çalışan çift uçlu kuyrukta gerekir.

Modüler aritmetiğin ikinci kullanımı öğe sayısını bulmaktır. Doğrusal kuyrukta öğe sayısı arka − on idi. Dairesel kuyrukta arka sarıp on'un gerisine düşebilir; o zaman fark negatif olur. Aynı düzeltme burada da işe yarar:

7.3.3A…F ile sarma

Sarmanın kuyrukta nasıl işlediğini adım adım görmek için altı hücreli bir dairesel kuyruk ele alınsın. Başlangıçta on = arka = 0'dır. A, B, C, D ve E sırasıyla eklenir. Her eklemede arka önce ilerler, sonra öğe yeni hücreye yazılır. Bu yüzden A 0 numaralı hücreye değil, 1 numaralı hücreye girer. E eklendikten sonra arka = 5'tir ve 0 numaralı hücre boştur.

Bu noktada bir ekleme daha denenseydi (5 + 1) % 6 = 0 değeri on'a eşit çıkardı ve kuyruk dolu sayılırdı. Altı hücrede beş öğe vardır; bir hücre bilerek boş bırakılmıştır. Sonra A alınır: on = (0 + 1) % 6 = 1 olur ve A döner. Artık 0 ve 1 numaralı hücrelerin ikisi de boştur. Ardından F eklenir. arka = (5 + 1) % 6 = 0 olur; F, önde boşalan 0 numaralı hücreye yazılır. Doğrusal kuyruğun kullanamadığı hücre burada arkadaymış gibi kullanılmıştır. Kuyruk şimdi yine doludur: (0 + 1) % 6 = 1 = on. Kuyrukta B, C, D, E, F vardır ve sıraları korunmuştur. Bir sonraki çıkarma B'yi verir, çünkü on 1'den 2'ye ilerler.

7.3.4C kodu ve ince bir nokta

Dairesel kuyruğun kodu, doğrusal kuyruğun kodundan yalnız iki noktada ayrılır: indisler % MAX_QUEUE_SIZE ile ilerler ve dolu koşulu değişir. Aşağıdaki sürüm yine Horowitz, Sahni ve Anderson-Freed'in kitabındaki gerçeklemeye dayanır:

void kuyruk_ekle(int on, int *arka, element item) {
    *arka = (*arka + 1) % MAX_QUEUE_SIZE; /* ilerlet */
    if (on == *arka) kuyruk_dolu();       /* dolu mu? */
    kuyruk[*arka] = item;                 /* yerleştir */
}
element kuyruk_al(int *on, int arka) {
    if (*on == arka) kuyruk_bos();        /* boş mu? */
    *on = (*on + 1) % MAX_QUEUE_SIZE;     /* ilerlet */
    return kuyruk[*on];                   /* döndür */
}

kuyruk_ekle artık on'u da parametre olarak alır, çünkü dolu koşulu on'a bağlıdır. Fonksiyon önce *arka'yı sarmalı biçimde bir ilerletir. İlerlemiş arka on'a eşitse kuyruk doludur ve kuyruk_dolu çağrılır. Değilse öğe yeni hücreye yazılır. kuyruk_al doğrusal sürümdeki gibi önce boşluğa bakar, sonra *on'u sarmalı biçimde ilerletip o hücredeki öğeyi döndürür. Her iki fonksiyon da sabit sayıda işlem yapar ve hiçbir öğeyi taşımaz; ikisinin de maliyeti O(1)'dir.

Bu koddaki ince nokta, kuyruk_ekle'nin önce *arka'yı ilerletmesi, doluluğa sonra bakmasıdır. Kuyruk doluysa *arka çoktan on'a eşitlenmiştir. Sunumdaki sürümde bunun zararı yoktur, çünkü kuyruk_dolu programı bitirir ve bozulan değer bir daha kullanılmaz. Hata durumunda programı bitirmeyen, yalnız uyarı verip dönen bir sürüm yazıldığında ise sorun ortaya çıkar. Kuyruk dolu iken yapılan bir ekleme denemesinden sonra on == arka olur ve kuyruk boş görünür. İçindeki bütün öğeler bir anda kaybolmuştur. Bu davranış küçük bir deneyle doğrulandı: altı hücreli kuyruğa A…E eklendikten sonra (on = 0, arka = 5) F eklenmek istendi. Uyarı yazılıp dönüldükten sonra arka = 0 ve on == arka oldu; kuyruk boş göründü.

Kitaptaki gerçekleme bu yüzden dolu durumunda arka'yı eski değerine geri alır. Daha temiz bir yol, yeni konumu önce geçici bir değişkende hesaplamak ve arka'yı ancak yer olduğu kesinleşince değiştirmektir. Bu yaklaşım bir genel ilkenin örneğidir: başarısız olabilen bir işlem, başarısız olduğunda veri yapısını değiştirmemelidir.

Sunumda bu slaytın yanında hocanın bir sözü de yer alır. Söz, iyi bir üniversitede okumanın güvence değil sorumluluk olduğunu anlatır: öğrenci, başaramazsa okuldan atılacağını bilerek çalışmalıdır. Aynı tutum kod yazarken de geçerlidir. Bir kodun “genellikle çalışması” yetmez; dolu kuyruğa ekleme gibi kenar durumlar da bilerek düşünülmelidir.

7.3.5Güvenli sürüm ve kod izleme

Aşağıdaki sürüm programı bitirmez. Hata durumunda false, başarıda true döndürür ve kararı çağırana bırakır. kuyruk_al çıkan öğeyi dönüş değeriyle değil, bir çıkış parametresiyle (element *x) verir; çünkü dönüş değeri başarı bilgisine ayrılmıştır. bool tipi için <stdbool.h> eklenmelidir.

bool kuyruk_ekle(int on, int *arka, element x) {
  int yeni = (*arka + 1) % MAX_QUEUE_SIZE;
  if (yeni == on) return false;       /* dolu */
  *arka = yeni;  kuyruk[yeni] = x;
  return true;
}
bool kuyruk_al(int *on, int arka, element *x) {
  if (*on == arka) return false;      /* boş */
  *on = (*on + 1) % MAX_QUEUE_SIZE;
  *x = kuyruk[*on];  return true;
}

kuyruk_ekle yeni konumu yeni adlı yerel değişkende hesaplar. yeni == on ise kuyruk doludur ve fonksiyon arka'ya hiç dokunmadan false döner. Yer varsa önce *arka = yeni yapılır, sonra öğe yazılır. kuyruk_al boş kuyrukta false döner. Aksi hâlde on'u ilerletir, öğeyi *x üzerinden çağırana iletir ve true döner. Çağıran taraf if (!kuyruk_ekle(on, &arka, x)) gibi bir denetimle hatayı yakalayabilir.

Tablonun iki satırı özellikle önemlidir. İlk E denemesinde kuyrukta dört öğe vardır ve beş hücreden biri (0 numaralı) boştur. Yine de yeni 0 olur ve on'a eşittir; kuyruk dolu sayılır. Güvenli sürüm burada arka'yı 4'te bırakır. Kuyruk bozulmamıştır ve iki çıkarma A ile B'yi doğru sırayla verir. İkinci E denemesinde arka 4'ten 0'a sarar ve E, doğrusal kuyruğun asla kullanamayacağı 0 numaralı hücreye yazılır. G denemesinde yine dört öğe vardır (C, D, E, F) ve boş kalan 2 numaralı hücre, on'un gösterdiği hücredir. Bu durumdaki kuyruğu boşaltan çıkarmalar C, D, E, F sırasını verir; bu da ilk giren ilk çıkar kuralıyla tutarlıdır.

7.3.6Dolu mu, boş mu? Üç yöntem

Önceki iki izlemede kuyruk bir hücresi boşken dolu sayıldı. Bu bir dikkatsizlik değil, zorunluluktur. Yalnız on ve arka ile dolu ve boş kuyruklar birbirinden ayırt edilemez. Durumu kesin biçimde ifade etmek için sayma yeter.

Kanıt. Kuyruktaki öğe sayısı yalnız iki indisin farkına bağlıdır: öğeler on'un bir sonrasından başlayıp arka'ya kadar uzanır. Fark (arka − on + MAX) % MAX biçiminde ölçülür ve bu ifade yalnız 0, 1, …, MAX − 1 değerlerini alabilir; yani MAX farklı değer vardır. Öğe sayısı ise 0'dan MAX'a kadar MAX + 1 farklı değer alabilir. MAX + 1 durumu MAX kutuya dağıtmak gerekir. Güvercin yuvası ilkesine göre en az bir kutuya iki durum düşer. Somut olarak, boş kuyruk ile MAX öğeli dolu kuyruk aynı farkı (0) verir: her ikisinde de on == arka'dır. ∎

Teorem iki çıkış yolu bırakır. Ya ayırt edilemeyen durumlardan biri kullanılmaz ya da indislerin yanında ek bilgi tutulur. Tablo 7.5 bu iki yolun üç uygulamasını karşılaştırır.

Birinci yöntem buraya kadarki kodların kullandığı yöntemdir. MAX öğeli durumdan vazgeçilir, böylece on == arka yalnız boş kuyruğu anlatır. Bedeli tek bir hücredir. Öğeler büyük yapılar ise bu hücre kayda değer bir bellek demektir, ama çoğu uygulamada önemsizdir. Kodun sadeliği bu bedeli karşılar.

İkinci yöntem öğe sayısını ayrı bir sayac değişkeninde tutar. Boş ve dolu doğrudan bu sayaçtan okunur ve MAX hücrenin hepsi kullanılır. Sayacın bir yan yararı daha vardır: öğe sayısı her an hazırdır ve O(1)'de okunur. Üstelik sayaç varken arka'yı tutmaya gerek kalmaz. Son öğenin yeri (on + sayac − 1) % KAP ile, bir sonraki boş hücre ise (on + sayac) % KAP ile hesaplanır.

Üçüncü yöntem yalnız bir bitlik bilgi ekler: son yapılan işlemin ekleme mi alma mı olduğu. on == arka durumu ancak iki biçimde ortaya çıkar. Ya bir alma işlemi kuyruğun son öğesini çıkarmıştır ya da bir ekleme işlemi son boş hücreyi doldurmuştur. Bayrak bu iki olasılığı birbirinden ayırır. Bayrak yönteminin kodu alıştırmalar kesiminde verilir.

7.3.7Sayaçlı dairesel kuyruk

Sayaçlı sürüm kuyruğun bütün durumunu bir struct içinde toplar. Böylece birden çok kuyruk aynı programda kullanılabilir ve küresel değişkene gerek kalmaz. Yapının tanımı typedef struct { int veri[KAP]; int on, sayac; } Kuyruk; biçimindedir. Bu sürümde on, bir öncesini değil, ilk öğenin kendisini gösterir; boş bir kuyruk on = 0, sayac = 0 ile başlar. İşlemler şöyledir:

bool ekle(Kuyruk *k, int x) {
  if (k->sayac == KAP) return false;       /* dolu */
  k->veri[(k->on + k->sayac) % KAP] = x;
  k->sayac++;
  return true;
}
bool al(Kuyruk *k, int *x) {
  if (k->sayac == 0) return false;         /* boş */
  *x = k->veri[k->on];
  k->on = (k->on + 1) % KAP;
  k->sayac--;
  return true;
}

ekle önce doluluğa bakar: sayac == KAP ise yer yoktur. Yer varsa yeni öğe, son öğenin bir sonrasına, yani (on + sayac) % KAP hücresine yazılır ve sayaç bir artar. al boş kuyrukta false döner. Boş değilse öndeki öğeyi *x'e kopyalar, on'u sarmalı biçimde bir ilerletir ve sayacı bir azaltır. İki işlem de sabit iş yapar; maliyetleri O(1)'dir. Fonksiyonlar kuyruğu Kuyruk *k işaretçisiyle alır. Yapı değere göre aktarılsaydı fonksiyon yapının bir kopyası üzerinde çalışır ve çağıranın kuyruğu değişmezdi. k->sayac yazımı, (*k).sayac'ın kısaltmasıdır.

Bu kez üç hücrenin üçü de dolar ve hiçbir hücre israf edilmez. Dördüncü ekleme ancak sayaç KAP'a ulaştığı için reddedilir. Bir çıkarmadan sonra eklenen 4, sarmayla 0 numaralı hücreye yazılır. Son durumda kuyruğun mantıksal sırası on'dan başlayarak 3, 4'tür: 3 ikinci hücrede, 4 sıfırıncı hücrededir. Dizideki fiziksel sıra (4, ·, 3) ile kuyruğun sırası farklıdır. Dairesel kuyrukta sıra hiçbir zaman dizinin düz okunuşundan çıkarılmaz; her zaman on'dan başlayıp sarılarak okunur.

7.4Bağlı kuyruk

Dizi tabanlı her kuyruğun bir kapasitesi vardır. Kapasite programı yazarken seçilir ve sonradan değişmez. Kuyruğa en çok kaç öğe gireceği önceden bilinmiyorsa iki kötü seçenek kalır: büyük bir dizi ayırıp belleği boşa harcamak ya da küçük bir dizi ayırıp taşma riskini almak. Bağlı liste bu ikilemi ortadan kaldırır. Her öğe kendi düğümünde durur, düğüm gerektiğinde malloc ile ayrılır, işi bitince free ile iade edilir.

7.4.1Bağlı liste ile kuyruk

Bağlı listenin her düğümü bir değer ve bir sonraki düğümün adresini (bağ) taşır. Düğüm tipi bu notta typedef struct dugum { int deger; struct dugum *bag; } dugum; biçiminde tanımlanır. Yapının içinde kendi tipinden bir işaretçi bulunur; bu yüzden struct dugum adı typedef bitmeden kullanılır. Son düğümün bağı NULL'dır.

Tek yönlü bağlı listenin başına eklemek ve başından silmek kolaydır, çünkü ilk düğüm elde tutulur. Sona eklemek için ise son düğüme ulaşmak gerekir. Yalnız ilk düğümün adresi tutulursa son düğüm ancak bütün liste baştan sona yürünerek bulunur ve bu O(n) sürer. Kuyrukta ekleme bir uçtan, çıkarma öbür uçtan yapıldığı için iki ucun da elde olması gerekir. Bu yüzden bağlı kuyruk iki işaretçiyle temsil edilir: on ilk düğümü, arka son düğümü gösterir. Boş kuyrukta ikisi de NULL'dır.

Hangi ucun ön, hangisinin arka olacağı rastgele seçilmez. Ekleme listenin sonuna yapılır: arka->bag = yeni; arka = yeni; ve iş biter. Çıkarma listenin başından yapılır: on = on->bag; ile ilk düğüm atlanır. İki işlem de sabit sayıda atama yapar ve O(1)'dir. Tersi seçilseydi, yani başa ekleyip sondan silinseydi, ekleme yine kolay olurdu ama silme zorlaşırdı. Son düğümü silmek için sondan bir önceki düğümün bağını NULL yapmak gerekir. Tek yönlü listede bir düğümden öncekine geri dönülemez; sondan bir önceki düğüm de ancak baştan yürünerek, O(n) sürede bulunur. Kural kısaca şöyledir: tek yönlü bağlı kuyrukta sona eklenir, baştan silinir.

Bu kesim işaretçi bilgisine dayanır. Sunumda hocanın bir anısı, öğrencinin bu konudaki duygusunu iyi anlatır. Hoca iki dersi işaretçilere ayırmıştır. Bir öğrenci işaretçileri iyi bildiğini, ama anlatılanı yine de anlamadığını söyler. Hoca da bunun olabileceğini kabul eder. İşaretçili kodu kavramanın en güvenli yolu, her atamadan sonra kutu ve okları kâğıda çizmektir. Aşağıdaki iki izleme bu çizimi adım adım yapar.

7.4.2Kod izleme: kuyruk_ekle

Ekleme fonksiyonu kuyruğun iki işaretçisini de değiştirebilir. Boş kuyruğa yapılan ilk eklemede hem on hem arka yeni düğümü göstermelidir. Bu yüzden iki işaretçi de adresle, yani işaretçinin işaretçisi olarak (dugum **) aktarılır. Çağrı kuyruk_ekle(&on, &arka, 10) biçimindedir.

bool kuyruk_ekle(dugum **on, dugum **arka, int x) {
  dugum *yeni = malloc(sizeof *yeni);
  if (yeni == NULL) return false;
  yeni->deger = x;  yeni->bag = NULL;
  if (*arka == NULL) *on = yeni;   /* boş kuyruk */
  else (*arka)->bag = yeni;        /* sona bağla */
  *arka = yeni;
  return true;
}

İlk satır yeni düğüm için bellek ayırır. sizeof *yeni, yeni'nin gösterdiği tipin, yani dugum'un boyutudur. Tip adını tekrar yazmamak, sonradan tip değişirse kodu güncel tutar. malloc bellek bulamazsa NULL döner. Bu durumda fonksiyon kuyruğa dokunmadan false döndürür. Ardından düğümün alanları doldurulur. Yeni düğüm kuyruğun son düğümü olacağı için bağı NULL yapılır.

Sonraki if iki durumu ayırır. *arka == NULL ise kuyruk boştur; yeni düğüm aynı zamanda ilk düğümdür ve *on = yeni yapılır. Kuyruk boş değilse yeni düğüm eski son düğümün arkasına bağlanır: (*arka)->bag = yeni. Buradaki parantez gereklidir. -> işleci *'dan önce uygulanır; *arka->bag yazılsaydı *(arka->bag) olarak okunur ve derlenmezdi, çünkü arka bir yapıyı değil, bir işaretçiyi gösterir. Her iki durumda da son satır *arka = yeni ile arkayı yeni düğüme taşır.

İzleme, on'un yalnız ilk eklemede değiştiğini gösterir. Sonraki eklemelerde on hep 10'u gösterir; değişen, eski son düğümün bağı ve arka'dır. Her ekleme bir malloc, birkaç atama ve bir karşılaştırma yapar. Kuyruğun uzunluğu hiçbir adımı etkilemez; ekleme O(1)'dir. arka işaretçisi tutulmasaydı son düğüm her eklemede baştan yürünerek bulunur ve n eklemenin toplam maliyeti 1 + 2 + … + n = Θ(n²) olurdu.

7.4.3Kod izleme: kuyruk_al

Çıkarma işlemi öndeki düğümü listeden ayırır, değerini çağırana verir ve düğümün belleğini iade eder:

bool kuyruk_al(dugum **on, dugum **arka, int *x) {
  dugum *eski = *on;
  if (eski == NULL) return false;      /* boş */
  *x = eski->deger;
  *on = eski->bag;
  if (*on == NULL) *arka = NULL;  /* son öğe gitti */
  free(eski);
  return true;
}

Fonksiyon önce öndeki düğümün adresini eski adlı yerel değişkende saklar. Bu saklama zorunludur. *on bir sonraki düğüme ilerletildikten sonra eski düğüme ulaşmanın başka yolu kalmaz; adresi saklanmadan ilerlenirse düğüm free edilemez ve sızar. eski NULL ise kuyruk boştur ve false döner. Değilse değer *x'e kopyalanır ve *on = eski->bag ile ön, ikinci düğüme geçer.

Sonraki satır bağlı kuyruğun en kolay unutulan ayrıntısıdır. Kuyruktaki son öğe çıkarıldıysa *on artık NULL'dır. Bu anda *arka hâlâ az sonra serbest bırakılacak düğümü gösterir. *arka = NULL yapılmazsa arka bir sarkan işaretçi (dangling pointer), yani artık geçerli olmayan bir bellek bölgesini gösteren işaretçi olur. Bir sonraki kuyruk_ekle çağrısı *arka'yı NULL görmez, kuyruğu boş saymaz ve serbest bırakılmış düğümün bağ alanına yazar. Bu tanımsız davranıştır. Üstelik on NULL kaldığı için yeni öğe de kuyrukta görünmez. Son olarak free(eski) ile düğüm iade edilir. free, değer okunduktan ve bağ izlendikten sonra çağrılmalıdır; serbest bırakılmış bir düğümün alanlarını okumak da tanımsız davranıştır.

İki fonksiyon birlikte sınandı. Boş kuyruğa 10, 20, 30 eklenip hepsi alındığında değerler 10, 20, 30 sırasıyla çıktı ve son çıkarmadan sonra on ile arka'nın ikisi de NULL oldu. Boşalan kuyruğa yeni bir ekleme (99) her iki işaretçiyi de doğru biçimde yeni düğüme yöneltti. 100 000 öğelik bir deneme de öğelerin ekleme sırasıyla çıktığını doğruladı. Programdaki malloc ve free çağrıları sayıldı: 100 006 ayırmanın her biri için bir iade yapıldı, sızıntı yoktur. Bu derleyici ve platformda bir düğüm 16 bayttır: 4 baytlık int, 4 baytlık hizalama boşluğu ve 8 baytlık işaretçi.

7.4.4Dizi mi, bağlı liste mi?

Kuyruğun üç gerçeklemesi aynı soyut işlemleri sunar, ama maliyetleri ve kısıtları farklıdır. Tablo 7.9 bunları yan yana koyar.

Doğrusal kuyruk yalnız öğretim amacı taşır; gerçek programlarda kullanılmaz. Dairesel dizi ile bağlı liste arasındaki seçim ise uygulamaya bağlıdır. Dairesel dizi belleği tek blok olarak kullanır. Öğeler bellekte yan yana durduğu için işlemci önbelleğinden iyi yararlanır ve her işlemde malloc çağırmaz. Bağlı kuyruk ise üst sınır gerektirmez, ama her öğe için bir işaretçi taşır ve her ekleme bir bellek ayırma çağrısıdır. int tutan bir kuyrukta bu, öğe başına 16 bayt demektir; dizide 4 bayt yeter.

Pratikte en çok iki yapı kullanılır: sabit kapasiteli tamponlar için dairesel dizi ve üst sınırı bilinmeyen kuyruklar için büyüyen dairesel dizi. Büyüyen sürümde dizi dolunca iki katı büyüklükte yeni bir dizi ayrılır ve öğeler oraya taşınır. Taşıma realloc ile yapılamaz. realloc eski bloğu olduğu gibi kopyalar; kuyruk sarmış durumdaysa öğelerin bir kısmı dizinin sonunda, bir kısmı başındadır ve büyüyen dizide arada boş hücreler kalır. Öğeler bu yüzden on'dan başlayarak, mantıksal sırayla tek tek kopyalanır.

typedef struct {
  int *veri;
  int kap, on, sayac;
} DKuyruk;

bool buyut(DKuyruk *k) {
  int yeni_kap = 2 * k->kap;
  int *yeni = malloc(yeni_kap * sizeof *yeni);
  if (yeni == NULL) return false;
  for (int i = 0; i < k->sayac; i++)              /* sırayı düzelterek kopyala */
    yeni[i] = k->veri[(k->on + i) % k->kap];
  free(k->veri);
  k->veri = yeni;  k->kap = yeni_kap;  k->on = 0;
  return true;
}
bool d_ekle(DKuyruk *k, int x) {
  if (k->sayac == k->kap && !buyut(k)) return false;
  k->veri[(k->on + k->sayac) % k->kap] = x;
  k->sayac++;
  return true;
}

buyut yeni diziyi ayırır, i'nci öğeyi veri[(on + i) % kap] hücresinden alıp yeni dizinin i'nci hücresine yazar, eski diziyi iade eder ve on'u 0'a çeker. d_ekle yalnız kuyruk doluyken büyütür; büyütme başarısız olursa kuyruğa dokunmadan false döner. Örneğin dört hücreli kuyruğa 1…4 eklenip iki öğe alındıktan sonra 5 ve 6 eklensin. Dizi fiziksel olarak 5, 6, 3, 4 içerir; on = 2'dir. 7 eklenince dizi sekiz hücreye büyür ve öğeler 3, 4, 5, 6 sırasıyla başa dizilir; 7 de beşinci hücreye girer. Sırayı bozan bir kopyalama, kuyruktan 3, 4, 5, 6, 7 yerine başka bir sıra çıkarırdı.

Büyütme tek başına Θ(n) sürer, ama seyrek yapılır. Kapasite her seferinde iki katına çıktığı için n eklemede kopyalanan toplam öğe sayısı 1 + 2 + 4 + … < 2n'dir. Böylece ekleme başına ortalama maliyet sabit kalır; ekleme amortize O(1)'dir. Deneyde kapasitesi 1'den başlayan kuyruğa bir milyon öğe eklendi: 20 büyütme yapıldı, toplam 1 048 575 öğe kopyalandı ve bu sayı 2n'nin altında kaldı. Bütün öğeler ekleme sırasıyla çıktı; 23 malloc çağrısının hepsi free ile iade edildi.

Bağlı kuyruk, öğeler zaten düğüm olarak yaşıyorsa doğal seçimdir. Örneğin bir işletim sistemi, süreç tanımlayıcı yapılarını kendi bağ alanlarıyla kuyruğa dizer. Bu durumda kuyruk ayrı bir bellek ayırmaz; yalnız var olan bağları düzenler.

7.5Deque ve uygulamalar

Kuyruk ve yığın, erişimi bir ya da iki uçla sınırlar. Bu kesim önce iki ucun da hem ekleme hem çıkarma için açık olduğu genel yapıyı, çift uçlu kuyruğu tanıtır. Ardından kuyruğun üç uygulamasına geçer: tek dizide birden çok kuyruk tutmak, işletim sistemlerindeki zaman dilimli zamanlama ve yalnız iki yığınla kuyruk kurmak.

7.5.1Çift uçlu kuyruk

Deque, yığın ile kuyruğu kapsayan genel bir yapıdır. Yalnız bir uç kullanılırsa, örneğin hep sona eklenip hep sondan alınırsa, deque bir yığın gibi davranır: 1, 2, 3 eklenince 3, 2, 1 çıkar. Bir uçtan eklenip öbür uçtan alınırsa kuyruk olur: aynı ekleme sırası 1, 2, 3 çıkışını verir. Bu iki davranış, aşağıdaki gerçeklemeyle sınanarak doğrulandı. İki kısıtlı türü de vardır. Girdisi kısıtlı deque'de ekleme yalnız bir uçta, silme iki uçta yapılır. Çıktısı kısıtlı deque'de ise ekleme iki uçta, silme yalnız bir uçta yapılır.

Deque birçok algoritmada iş görür. Kayan pencere sorusunda bir dizi üzerinde sabit genişlikte bir pencere kaydırılır ve her konumda penceredeki en büyük değer istenir. Deque, aday değerlerin indislerini tutar. Pencereden çıkan indis baştan, yeni gelenden küçük kalan adaylar sondan atılır. Böylece bütün dizi O(n) sürede işlenir. Çok çekirdekli zamanlayıcılarda kullanılan iş çalma (work stealing) yönteminde her çekirdek kendi işlerini bir deque'de tutar. Çekirdek kendi işlerini bir uçtan alır, boşta kalan başka bir çekirdek ise öbür uçtan iş “çalar”. Metin düzenleyicilerdeki geri alma geçmişi de deque ile tutulabilir. Yeni işlemler sona eklenir ve geri alma sondan yapılır. Geçmiş belirli bir uzunluğu aşınca en eski kayıt baştan atılır.

7.5.2Dairesel dizide deque

Deque, sayaçlı dairesel kuyruğa küçük bir eklemeyle kurulur. Yapı aynıdır: typedef struct { int veri[KAP]; int on, sayac; } Deque;. on ilk öğeyi gösterir, sayac öğe sayısıdır. Sona ekleme ve baştan alma, sayaçlı kuyruğun ekle ve al fonksiyonlarıyla aynıdır. Yeni olan iki işlem başa ekleme ve sondan almadır:

bool basa_ekle(Deque *d, int x) {
  if (d->sayac == KAP) return false;
  d->on = (d->on - 1 + KAP) % KAP;    /* bir geri */
  d->veri[d->on] = x;  d->sayac++;
  return true;
}
bool sondan_al(Deque *d, int *x) {
  if (d->sayac == 0) return false;
  *x = d->veri[(d->on + d->sayac - 1) % KAP];
  d->sayac--;  return true;
}

basa_ekle yeni öğeyi mevcut ilk öğenin bir gerisine koyar. Bunun için on bir geri alınır. Geri adım, modüler aritmetiğin negatif kalan tuzağına düşmemek için (on − 1 + KAP) % KAP ile hesaplanır. on = 0 iken bu ifade KAP − 1 verir: 0'ın bir gerisi dizinin son hücresidir. sondan_al son öğenin konumunu (on + sayac − 1) % KAP ile bulur, o hücredeki değeri okur ve yalnız sayacı azaltır. Son öğe çıkarıldığında on değişmez, çünkü ilk öğe yerinde kalmıştır. Tamamlık için öteki iki işlem de aşağıda verilmiştir:

bool sona_ekle(Deque *d, int x) {
  if (d->sayac == KAP) return false;
  d->veri[(d->on + d->sayac) % KAP] = x;   /* son öğenin bir sonrası */
  d->sayac++;
  return true;
}
bool bastan_al(Deque *d, int *x) {
  if (d->sayac == 0) return false;
  *x = d->veri[d->on];
  d->on = (d->on + 1) % KAP;            /* bir ileri */
  d->sayac--;
  return true;
}

Dört fonksiyonun hiçbiri döngü içermez; her biri birkaç aritmetik işlem ve bir dizi erişimi yapar. Hepsinin maliyeti O(1)'dir. Bellek maliyeti KAP öğedir.

İlk basa_ekle, sarmanın geri yönde de işlediğini gösterir. on 0'dan 4'e geçer ve 5, dizinin son hücresine yazılır. Mantıksal sırada ise 5, 10'un önündedir. Dizi düz okunduğunda 10, 20, ·, ·, 5 görünür; deque'nin sırası ise on'dan başlayıp sarılarak okunur: 5, 10, 20. İki sondan_al çağrısı en son giren öğeleri değil, deque'nin sonundaki öğeleri verir: önce 20, sonra 10. Bu noktada bir bastan_al çağrılsaydı 3 dönerdi ve on 4'e ilerlerdi.

7.5.3Tek dizide birden çok kuyruk

Bazı programlar aynı anda çok sayıda kuyruk kullanır. Örneğin bir işletim sistemi her öncelik düzeyi için ayrı bir hazır süreç kuyruğu tutabilir. Her kuyruğa ayrı ve büyük bir dizi ayırmak belleği boşa harcar, çünkü kuyrukların hepsi aynı anda dolmaz. Yığınlarda kullanılan bir yöntem burada da denenebilir: tek boyutlu bir memory[] dizisi n kesime bölünür ve her kuyruğa bir kesim verilir. i'nci kuyruk için üç değer tutulur: on[i], arka[i] ve kesimin bittiği yeri gösteren sinir[i].

İki yığın tek diziye çok verimli yerleşir: biri dizinin başından sağa, öbürü sonundan sola doğru büyür ve ikisi ancak bütün dizi dolunca karşılaşır. Bu “uçlardan büyütme” hilesi kuyrukta işe yaramaz. Yığının alt ucu sabittir, kuyruğun ise iki ucu da hareket eder. Kuyruk ekleme ve çıkarmalarla kesim içinde sürekli kayar. Her kesim kendi içinde dairesel kuyruk gibi yönetilirse kaydırma gerekmez. Ama bir kesim dolduğunda, başka kesimlerde boş yer olsa bile, kuyruklardan birini taşıyıp yer açmak gerekir. Bu da m dizinin boyu olmak üzere O(m) sürer. Bu karmaşıklık yüzünden günümüzde birden çok kuyruk için genellikle her kuyruğa ayrı bir büyüyen dizi ya da bağlı liste kullanılır.

7.5.4Round robin iş zamanlama

Tek işlemcili bir bilgisayarda aynı anda birçok süreç çalışmak ister. İşletim sistemi işlemciyi süreçler arasında paylaştırır. En bilinen paylaştırma yöntemi zaman dilimli zamanlamadır; İngilizce adıyla round robin (round robin) de denir. Hazır süreçler bir kuyrukta bekler. Zamanlayıcı öndeki süreci alır ve onu en çok Q birim, yani bir zaman dilimi kadar çalıştırır. Süreç bu sürede işini bitirirse sistemden ayrılır. Bitiremezse kalan işiyle birlikte kuyruğun sonuna geri döner. Böylece hiçbir süreç işlemciyi tekeline alamaz ve her süreç düzenli aralıklarla sıra bulur.

Benzetimde süreçler 0, 1, 2 numaralarıyla, kalan iş miktarları kalan[] dizisiyle temsil edilir. Kuyruk olarak sayaçlı dairesel kuyruk kullanılır; fonksiyon adları bu kez kuyruk_ekle ve kuyruk_al'dır:

#define KAP 16
typedef struct { int veri[KAP]; int on, sayac; } Kuyruk;

bool kuyruk_ekle(Kuyruk *k, int x) {
  if (k->sayac == KAP) return false;
  k->veri[(k->on + k->sayac) % KAP] = x;
  k->sayac++;
  return true;
}
bool kuyruk_al(Kuyruk *k, int *x) {
  if (k->sayac == 0) return false;
  *x = k->veri[k->on];
  k->on = (k->on + 1) % KAP;
  k->sayac--;
  return true;
}

Başlangıçta üç süreç de kuyruktadır. P0'ın 5, P1'in 2, P2'nin 4 birim işi vardır ve zaman dilimi Q = 2'dir:

int kalan[] = {5, 2, 4};      /* P0, P1, P2 iş miktarları */
int Q = 2, zaman = 0, p;
Kuyruk k = { {0}, 0, 0 };     /* boş sayaçlı kuyruk */
for (int i = 0; i < 3; i++)
  kuyruk_ekle(&k, i);         /* başta hepsi kuyrukta */

Zamanlayıcının kendisi tek bir döngüdür:

/* k: süreç numaraları kuyruğu; Q: zaman dilimi */
while (kuyruk_al(&k, &p)) {
  int dilim = kalan[p] < Q ? kalan[p] : Q;
  zaman += dilim;
  kalan[p] -= dilim;
  if (kalan[p] > 0)
    kuyruk_ekle(&k, p);           /* sona geri */
  else
    printf("P%d biter: t=%d\n", p, zaman);
}

Döngü kuyruk boşalana kadar sürer; kuyruk_al boş kuyrukta false döndürdüğü için koşul aynı zamanda bitiş denetimidir. Her turda öndeki süreç p'ye alınır. Sürecin bu turda çalışacağı süre, kalan işi ile zaman diliminden küçük olanıdır; koşullu ifade (? :) bunu tek satırda hesaplar. Saat (zaman) bu kadar ilerler, sürecin kalan işi de bu kadar azalır. İş kaldıysa süreç kuyruğun sonuna eklenir, kalmadıysa bitiş anı yazdırılır.

Program sırasıyla P1 biter: t=4, P2 biter: t=10 ve P0 biter: t=11 yazar. Son turda P0'ın yalnız 1 birim işi kaldığı için dilim 2 değil 1'dir. Toplam süre işlerin toplamına (5 + 2 + 4 = 11) eşittir, çünkü işlemci hiç boş kalmaz. Zamanlamanın sonucu bitiş sırasıdır. En kısa iş (P1) önce, en uzun iş (P0) en son biter. Oysa süreçler önce gelen önce hizmet alır kuralıyla, araya girmeden çalıştırılsaydı bitiş anları P0 için 5, P1 için 7, P2 için 11 olurdu. Kısa iş, uzun bir işin arkasında beklemek zorunda kalırdı.

Maliyet bakımından her tur bir kuyruk_al ve en çok bir kuyruk_ekle yapar; ikisi de O(1)'dir. Bir sürecin toplam işi w birimse süreç ⌈w/Q⌉ kez kuyruktan alınır. Benzetimin toplam maliyeti bu sayıların toplamıyla orantılıdır. Örnekte bu toplam 3 + 1 + 2 = 6 turdur. Zaman dilimi küçüldükçe süreçler daha sık sıra bulur, ama tur sayısı artar. Q = 1 ile aynı örnek 11 tur sürer. Gerçek sistemlerde her tur bir bağlam değiştirme bedeli taşıdığı için dilim çok küçük seçilmez.

7.5.5İki yığınla kuyruk

Yalnız yığın işlemleri sunan bir ortamda kuyruk gerekirse iki yığın yeter. Fikir, yığının sırayı ters çevirmesine dayanır. Bir dizi öğe bir yığına konup oradan başka bir yığına aktarılırsa iki kez ters çevrilmiş olur, yani ilk sırasına döner. Kuyruk iki yığından oluşur: giris ve cikis. Yığın tipi Yigit, veri dizisi ve boşken −1 olan ust indisiyle tanımlıdır. push, pop ve yigit_bos bilinen yığın işlemleridir; pop, yığın boşsa false döndürür. Kuyruk tipi typedef struct { Yigit giris, cikis; } Kuyruk2; biçimindedir.

void ekle(Kuyruk2 *q, int x) {
  push(&q->giris, x);
}
bool al(Kuyruk2 *q, int *x) {
  int t;
  if (yigit_bos(&q->cikis))       /* çıkış boşsa */
    while (pop(&q->giris, &t))    /* hepsini aktar */
      push(&q->cikis, t);
  return pop(&q->cikis, x);
}

ekle öğeyi her zaman giriş yığınına koyar; bunun maliyeti tek bir push'tur. al, çıkış yığını boşsa önce girişteki bütün öğeleri tek tek çıkış yığınına aktarır. Aktarma sırayı ters çevirir: girişin en altındaki, yani en eski öğe çıkışın en üstüne gelir. Sonra çıkış yığınından bir pop yapılır. Çıkış yığını boş değilse aktarma yapılmaz, çünkü çıkıştaki her öğe girişteki her öğeden daha eskidir. Çıkış boşalmadan aktarma yapılsaydı yeni öğeler eskilerin üstüne biner ve sıra bozulurdu. İki yığın da boşsa son pop false döndürür ve al da false döner. ekle ise push'un dönüş değerini yok sayar. Giriş yığını dolu olursa öğe sessizce kaybolur; güvenli bir sürüm bu değeri çağırana iletmelidir.

Çıkış sırası 1, 2, 3, 4'tür; ekleme sırasıyla aynıdır. 4, 2 ve 3'ten sonra eklendiği hâlde onlardan önce çıkmaz. Çünkü 4 eklendiğinde 2 ve 3 zaten çıkış yığınındadır ve 4 ancak çıkış boşaldıktan sonra aktarılır.

Tek bir al çağrısı pahalı olabilir: çıkış boşken girişte n öğe varsa n aktarma yapılır ve çağrı Θ(n) sürer. Ama böyle pahalı çağrılar seyrektir. Bir dizi işlemin toplam maliyetine bakıldığında işlem başına maliyet sabittir.

Kanıt. Tek bir öğenin kuyruktaki ömrü izlensin. Öğe ekle ile giriş yığınına bir kez konur (bir push). Bir aktarma sırasında girişten bir kez çıkar ve çıkışa bir kez konur (bir pop, bir push). Çıkış yığınından giriş yığınına hiçbir zaman geri dönmez; bu yüzden ikinci kez aktarılmaz. Son olarak al ile çıkış yığınından bir kez çıkar (bir pop). Her öğe böylece en çok dört yığın işlemine katılır. Bunlara ek olarak her al çağrısı, yığınlar boşken başarısız olan en çok bir pop ve bir yigit_bos denetimi yapar. Dizide en çok m öğe eklenebildiği için öğelere ait işlemler en çok 4m'dir; başarısız işlemler de sabit bir çarpanla sınırlıdır. Toplam iş O(m), işlem başına ortalama iş O(1)'dir. ∎

Bu kanıttaki yöntem, amortize analizin (amortized analysis) en sade biçimidir. Pahalı bir işlemin maliyeti, onu mümkün kılan ucuz işlemlere paylaştırılır. Burada her ekle, öğesinin sonradan aktarılma bedelini de önceden “öder”. Teorem bir deneyle de sınandı. Rastgele seçilmiş 60 işlemlik bir dizide 37 ekleme ve buna denk çıkarma yapıldı. Toplam 74 push ve 74 pop sayıldı; bu, öğe başına tam iki push ve iki pop demektir. Bütün öğeler ekleme sırasıyla çıktı. Burada dikkat edilmesi gereken bir nokta vardır: amortize O(1), her çağrının hızlı olduğunu söylemez. Bir uygulama her işlemin belirli bir süreyi aşmamasını istiyorsa (örneğin gerçek zamanlı bir ses tamponu) dairesel kuyruk daha uygundur.

7.5.6Yığın mı, kuyruk mu?

Bir problemde yığın mı kuyruk mu kullanılacağını belirlemek için tek bir soru sorulur: işlenmeyi bekleyen öğelerden hangisi önce ele alınmalıdır, en yenisi mi en eskisi mi? En yenisiyse yığın, en eskisiyse kuyruk uygundur. Ne en yeni ne en eski, başka bir ölçüte göre en önemli öğe önce alınacaksa öncelikli kuyruk gerekir. Tablo 7.13 sunumdaki örnekleri bu soruya göre sınıflandırır.

Son satır, adındaki “kuyruk” sözcüğüne bakılarak yanlış sınıflandırılabilir. Sunumdaki hocanın notu da bu karışıklığa dikkat çeker. Günlük dildeki kuyrukta sondan eklenir, baştan alınır. Öncelikli kuyruk ise bu kurala uymaz; adındaki sözcük yalnız “bekleme yeri” anlamını taşır.

7.6Karmaşıklık özeti ve ölçüm

Tablo 7.14 notta incelenen dört gerçeklemenin işlem maliyetlerini bir araya getirir. Tablodaki her değerin gerekçesi ilgili kesimde verilmiştir. Burada yalnız ortak noktalar özetlenir.

Yıldızlı değer bir uyarı taşır. Doğrusal kuyrukta ekleme kendi başına O(1)'dir, ama sahte doluluk kaydırmayla giderilirse ekleme O(n)'ye çıkar. Bağlı kuyrukta öğe sayısı ayrı bir sayaç tutulmazsa ancak liste baştan sona yürünerek bulunur. Bir sayaç değişkeni eklemek, bu işlemi de O(1)'e indirir. Bütün gerçeklemelerde ekleme ve alma sabit sürdüğü için kuyruğu kullanan algoritmaların maliyeti, yaptıkları kuyruk işlemi sayısıyla belirlenir. Round robin benzetimi ve düzey sırası gezinme, n öğe için O(n) kuyruk işlemi yapar.

Kaydırmalı doğrusal kuyruk ile dairesel kuyruk arasındaki fark ölçümle de gösterildi. İki kuyruk da M hücrelik bir dizi kullandı. Kaydırmalı kuyrukta sürekli M − 1, dairesel kuyrukta bir hücre boş kalacağı için M − 2 öğe tutuldu. Bu durumda 200 000 kez bir ekleme ve bir alma yapıldı. Program -O2 ile derlendi ve süreler timespec_get ile ölçüldü. Sonuçlar Tablo 7.15'te verilmiştir. Mutlak süreler makineye göre değişir; önemli olan, sütunların M ile nasıl değiştiğidir.

Taşınan öğe sayısı M her iki katına çıktığında iki katına çıkar; her ekleme yaklaşık M − 1 öğe taşır. Süreler de aynı oranda artar. Dairesel kuyruğun süresi ise M'den bağımsızdır. Kaydırmalı sürümün süreleri, taşınan öğe sayısına göre şaşırtıcı biçimde kısadır. Bunun nedeni, derleyicinin kaydırma döngüsünü bellek bloklarını toplu kopyalayan hızlı bir işleme çevirmesidir. Yine de büyüme doğrusaldır ve kuyruk büyüdükçe fark açılır.

7.7Sık yapılan hatalar

Kuyruk kodlarında en sık görülen altı hata aşağıda toplanmıştır. Her biri önceki kesimlerde ayrıntısıyla ele alındı; burada belirtisi ve çaresi birlikte verilir.

1. Doğrusal kuyrukta arka == MAX − 1'i gerçek doluluk sanmak. Koşul yalnız arkada yer kalmadığını söyler; öğe sayısı arka − on'dur ve çok küçük olabilir. Çaresi dairesel kuyruktur.
2. Dairesel kuyrukta % MAX'ı unutmak. İndis ilk sarmada dizinin dışına çıkar. Program uzun süre doğru çalışıp sonra beklenmedik bir yerde bozulabilir. İndisi değiştiren her satırda kalan işlemi aranmalıdır.
3. Önce arka'yı ilerletip kuyruk doluysa geri almamak. Hata döndüren bir sürümde dolu kuyruğa yapılan ekleme denemesi arka'yı on'a eşitler ve kuyruk boş görünür. Yeni konum önce geçici bir değişkende denenmelidir.
4. Geri adımda (i − 1) % MAX yazmak. C'de negatif sayının kalanı negatiftir; i = 0 için sonuç −1 olur. Doğrusu (i − 1 + MAX) % MAX'tır.
5. Bağlı kuyruktan son öğe alınınca arka = NULL yapmamak. arka serbest bırakılmış düğümü gösterir; sonraki ekleme bu belleğe yazar ve yeni öğe kuyrukta görünmez.
6. Boş bağlı kuyruğa ilk eklemede on'u güncellemeyi unutmak. Ya NULL işaretçi üzerinden yazılır ve program çöker ya da on NULL kalır ve eklenen öğeler hiçbir zaman alınamaz.

Bu hataların ortak kökü, kenar durumlardır: boş kuyruk, dolu kuyruk, tek öğeli kuyruk ve dizinin son hücresi. Bir kuyruk gerçeklemesi sınanırken en az şu senaryolar denenmelidir: boş kuyruktan alma, kuyruğu tam doldurup bir ekleme daha deneme, en az bir sarma, kuyruğu tümüyle boşaltıp yeniden kullanma.

7.8Alıştırmalar ve çözümleri

Bu kesim sunumdaki beş alıştırmayı ayrıntılı çözümleriyle verir. Kod içeren çözümler derlenip sınanmıştır.

7.8.1Öğe sayısı ve konumları

Soru. MAX = 6, on = 4, arka = 1 olan dairesel kuyrukta kaç öğe vardır ve öğeler hangi indislerdedir?

Çözüm. Öğe sayısı (arka − on + MAX) % MAX = (1 − 4 + 6) % 6 = 3'tür. on ilk öğenin bir öncesini gösterdiği için öğeler on'un bir sonrasından başlar: (4 + 1) % 6 = 5. Ardından sarmayla 0 ve 1 gelir. Öğeler 5, 0 ve 1 numaralı hücrelerdedir ve kuyruğun önündeki öğe 5 numaralı hücrededir. 2, 3 ve 4 numaralı hücreler boştur; 4 numaralı hücre, birinci yöntemin boş bıraktığı hücredir.

7.8.2Bayrak yöntemiyle dairesel kuyruk

Soru. Dolu ile boşu bir bayrakla ayırt eden dairesel kuyruğun ekleme ve alma yordamlarını yazın.

Çözüm. son_ekleme adlı mantıksal değişken, son yapılan işlemin ekleme olup olmadığını tutar. on == arka durumunda bu değişken doğruysa kuyruk dolu, yanlışsa boştur. Başlangıçta kuyruk boş olduğu için değeri false'tur.

#define MAX 4
int kuyruk[MAX];
int on = 0, arka = 0;
bool son_ekleme = false;      /* son işlem ekleme miydi? */

bool ekle(int x) {
    if (on == arka && son_ekleme) return false;   /* dolu */
    arka = (arka + 1) % MAX;
    kuyruk[arka] = x;
    son_ekleme = true;
    return true;
}
bool al(int *x) {
    if (on == arka && !son_ekleme) return false;  /* boş */
    on = (on + 1) % MAX;
    *x = kuyruk[on];
    son_ekleme = false;
    return true;
}

Ekleme, dolu denetiminden sonra sunumdaki kodla aynı biçimde çalışır, ama son olarak bayrağı kaldırır. Alma ise bayrağı indirir. Bayrak yalnız on == arka iken okunur. Kuyrukta 1 ile MAX − 1 arasında öğe varken iki indis zaten farklıdır ve bayrağın değeri önemsizdir. Bu sürüm sınandığında dört hücreli boş kuyruğa dört ekleme sığdı (on = arka = 0, bayrak doğru), beşinci ekleme reddedildi. Bir alma (10) ve bir ekleme (99) sonrasında kuyruk yine doldu ve öğeler 11, 12, 13, 99 sırasıyla çıktı. Hiçbir hücre israf edilmez; bedeli, her işlemde bir atama ve dolu ya da boş denetiminde bir mantıksal karşılaştırmadır.

7.8.3İki yığınla kuyruğun maliyeti

Soru. İki yığınla bir kuyruk yazın. al işleminin amortize maliyeti nedir?

Çözüm. Kod, sunumdaki ekle ve al fonksiyonlarıdır: ekleme giriş yığınına push yapar; alma, çıkış yığını boşsa girişi tümüyle aktarır, sonra çıkıştan pop yapar. Teorem 7.2'nin kanıtında gösterildiği gibi her öğe en çok iki kez yığına konur ve iki kez yığından çıkar. m işlemlik bir dizinin toplam maliyeti O(m)'dir. al'ın amortize maliyeti bu yüzden O(1)'dir. En kötü durumdaki tek çağrı ise Θ(n) sürer. Örneğin 1, 2, 3, 4 eklenip bir öğe alınsın, 5 eklensin ve dört öğe daha alınsın. Çıkış 1, 2, 3, 4, 5'tir. İlk alma dört öğeyi, son alma yalnız 5'i aktarır; toplam push sayısı 5 ekleme ve 5 aktarma olmak üzere 10'dur.

7.8.4Yalnız arka işaretçili dairesel bağlı kuyruk

Soru. Kuyruğu, yalnız arka işaretçisi tutulan dairesel bir bağlı listeyle yazın.

Çözüm. Dairesel bağlı listede son düğümün bağı NULL değil, ilk düğümdür. Bu yüzden ayrı bir on işaretçisine gerek kalmaz: ön düğüm her zaman arka->bag'dir. Tek düğümlü kuyrukta düğüm kendini gösterir. Boş kuyrukta arka NULL'dır.

bool ekle(dugum **arka, int x) {
  dugum *yeni = malloc(sizeof *yeni);
  if (yeni == NULL) return false;
  yeni->deger = x;
  if (*arka == NULL) yeni->bag = yeni;      /* tek düğüm kendini gösterir */
  else {
    yeni->bag = (*arka)->bag;               /* yeni, önü gösterir */
    (*arka)->bag = yeni;                    /* eski son, yeniyi gösterir */
  }
  *arka = yeni;
  return true;
}
bool al(dugum **arka, int *x) {
  if (*arka == NULL) return false;          /* boş */
  dugum *on = (*arka)->bag;                 /* ön, arkanın bir sonrası */
  *x = on->deger;
  if (on == *arka) *arka = NULL;            /* son düğüm de gitti */
  else (*arka)->bag = on->bag;
  free(on);
  return true;
}

Ekleme, yeni düğümü son düğüm ile ön düğüm arasına yerleştirir. Önce yeni düğüm ön düğümü gösterir (yeni->bag = arka->bag), sonra eski son düğüm yeni düğümü gösterir, en son arka yeni düğüme taşınır. Bağların bu sırası önemlidir: ikinci atama önce yapılsaydı ön düğümün adresi kaybolurdu. Alma, ön düğümü (arka->bag) çıkarır. Kuyrukta tek düğüm varsa ön ile arka aynı düğümdür ve kuyruk boşalır. Aksi hâlde son düğümün bağı ikinci düğüme çevrilir. İki işlem de O(1)'dir ve tek işaretçi tutulur. Sınamada 10, 20, 30 eklenip alındığında sıra korundu; 1003 malloc çağrısının hepsi free ile iade edildi.

7.8.5Round robin, Q = 3

Soru. Round robin örneğini (P0 = 5, P1 = 2, P2 = 4) Q = 3 ile çalıştırın. Süreçler ne zaman biter?

Çözüm. P0 0–3 arasında çalışır ve 2 birimi kalır; sona döner. P1 3–5 arasında çalışır ve t = 5'te biter. P2 5–8 arasında çalışır ve 1 birimi kalır; sona döner. P0 8–10 arasında kalan 2 birimi çalışır ve t = 10'da biter. P2 10–11 arasında son birimini çalışır ve t = 11'de biter. Program P1 biter: t=5, P0 biter: t=10, P2 biter: t=11 yazar. Q = 2'ye göre bitiş sırası değişmiştir: P0 artık P2'den önce biter. Tur sayısı da 6'dan 5'e iner. Dilim büyüdükçe zamanlama, önce gelen önce hizmet alır düzenine yaklaşır; Q ≥ 5 için bitiş anları 5, 7 ve 11 olur.

7.9Özet

• Kuyruk, eklemenin arkadan, çıkarmanın önden yapıldığı sıralı listedir; kuralı ilk giren ilk çıkar'dır (FIFO). Yığın sırayı ters çevirir, kuyruk korur. Temel işlemler kuyruk_ekle (taşma), kuyruk_al (alt taşma), kuyruk_on, kuyruk_bos ve kuyruk_dolu'dur.
• Doğrusal kuyruk iki indis kullanır: on ilk öğenin bir öncesini, arka son öğeyi gösterir; boş koşulu on == arka'dır. İndisler yalnız ileri gittiği için önde boşalan hücreler kullanılamaz (sahte doluluk). Kaydırma bu sorunu çözer ama eklemeyi O(n) yapar.
• Dairesel kuyruk indisleri % MAX ile sarar. Boş: on == arka; dolu: (arka + 1) % MAX == on. Öğe sayısı (arka − on + MAX) % MAX, geri adım (i − 1 + MAX) % MAX'tır; C'de negatif sayının kalanı negatiftir.
• İki indis MAX + 1 doluluk durumunu ayırt edemez. Çare ya bir hücreyi boş bırakmak (kapasite MAX − 1) ya da bir sayaç veya bayrak tutmaktır. Sayaçlı sürüm öğe sayısını O(1)'de verir ve arka'yı hesaplar.
• Başarısız olabilen bir işlem, başarısız olduğunda yapıyı değiştirmemelidir: yeni konum önce geçici bir değişkende denenir.
• Bağlı kuyruk on ve arka işaretçileriyle sona ekler, baştan siler; iki işlem de O(1)'dir. Boş kuyruğa ilk eklemede on, son öğe çıkınca arka = NULL güncellenir; aksi hâlde sızıntı ya da sarkan işaretçi oluşur.
• Pratikte sabit kapasiteli tamponlar için dairesel dizi, üst sınırı bilinmeyen kuyruklar için iki katına büyüyen dairesel dizi (amortize O(1)) kullanılır; büyütmede öğeler on'dan başlayarak sırayla kopyalanır.
• Deque iki uçta da ekleme ve çıkarma yapar; dairesel dizide dört işlemin hepsi O(1)'dir. Yığını da kuyruğu da kapsar.
• Round robin zamanlamada süreçler kuyrukta bekler, en çok bir zaman dilimi çalışır ve işi kalırsa sona döner. İki yığınla kuyrukta her öğe en çok bir kez aktarılır; işlemler amortize O(1)'dir.

7.10Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• kuyruk queue
• ilk giren ilk çıkar FIFO (first in, first out)
• son giren ilk çıkar LIFO (last in, first out)
• ön front
• arka rear
• enqueue (arkaya ekleme) enqueue
• dequeue (önden çıkarma) dequeue
• soyut veri tipi abstract data type
• taşma overflow
• alt taşma underflow
• dairesel kuyruk circular queue
• modüler aritmetik modular arithmetic
• tampon buffer
• genişlik öncelikli arama breadth-first search (BFS)
• düzey sırası level-order
• öncelikli kuyruk priority queue
• sarkan işaretçi dangling pointer
• bellek sızıntısı memory leak
• çift uçlu kuyruk deque (double-ended queue)
• amortize analiz amortized analysis
• ikiye katlama doubling
• yığın stack

7.11Kendini Dene

1. Güvenli dairesel kuyrukta MAX_QUEUE_SIZE = 4 ve başlangıçta on = arka = 0'dır. Sırasıyla 1, 2, 3, 4 eklenmek istenir, bir öğe alınır ve 4 yeniden eklenir. Hangi ekleme reddedilir? Sonunda on, arka ve öğe sayısı nedir? Sonraki kuyruk_al hangi değeri verir?

   Cevap

   1, 2, 3 sırasıyla 1, 2, 3 numaralı hücrelere girer. 4 için yeni = (3 + 1) % 4 = 0 = on olur ve ekleme reddedilir. Alma on'u 1'e ilerletir ve 1'i verir. Yeniden eklenen 4, arka = 0 hücresine yazılır. Sonunda on = 1, arka = 0, öğe sayısı (0 − 1 + 4) % 4 = 3'tür. Sonraki alma 2'yi verir.

2. MAX_QUEUE_SIZE = 5 olan doğrusal kuyruğa üç öğe eklenip üçü de alınıyor. Kuyruk boş olduğu hâlde en çok kaç ekleme daha yapılabilir? Neden?

   Cevap

   Üç ekleme ve üç almadan sonra on = arka = 2'dir. Ekleme arka 4 olana kadar yapılabilir: iki ekleme. Üçüncü denemede arka ≥ 4 olur ve kuyruk dolu sayılır. Nedeni sahte doluluktur: 0, 1 ve 2 numaralı hücreler boştur ama indisler yalnız ileri gittiği için bir daha kullanılmaz.

3. Bir programcı deque'de geri adımı d->on = (d->on - 1) % KAP; diye yazmıştır. KAP = 8 ve on = 0 iken basa_ekle çağrılırsa ne olur?

   Cevap

   C'de (0 − 1) % 8 ifadesinin değeri −1'dir. on −1 olur ve öğe veri[-1]'e, yani dizinin dışına yazılır. Bu tanımsız davranıştır; yapının başka bir alanı ya da komşu bir değişken bozulabilir. Doğru ifade (on − 1 + KAP) % KAP'tır ve 7 verir.

4. Bağlı kuyruğun kuyruk_al fonksiyonundan if (*on == NULL) *arka = NULL; satırı silinmiştir. Boş kuyruğa 5 ve 7 eklenir, iki öğe alınır, sonra 9 eklenir. Ne olur?

   Cevap

   İkinci almadan sonra on NULL'dır, ama arka serbest bırakılmış 7 düğümünü göstermeye devam eder. 9 eklenirken *arka != NULL olduğu için kod kuyruğu boş saymaz ve (*arka)->bag = yeni ile serbest bırakılmış belleğe yazar; bu tanımsız davranıştır. on güncellenmediği için NULL kalır. Sonraki kuyruk_al kuyruğu boş bulur; 9 hiçbir zaman alınamaz ve düğümü sızar.

5. Sayaçlı dairesel kuyrukta KAP = 4, on = 3, sayac = 3'tür. Öğeler hangi hücrelerdedir? Bir sonraki ekle öğeyi hangi hücreye yazar?

   Cevap

   Öğeler on'dan başlayarak 3, 0 ve 1 numaralı hücrelerdedir. Son öğenin yeri (3 + 3 − 1) % 4 = 1'dir. Bir sonraki ekleme (3 + 3) % 4 = 2 numaralı hücreye yazar ve sayaç 4 olur; kuyruk dolar.

6. KAP = 6 olan boş bir deque'ye (on = 0, sayac = 0) sırasıyla basa_ekle 1, basa_ekle 2, sona_ekle 3 uygulanır. Hangi değer hangi hücrededir? bastan_al ne verir?

   Cevap

   İlk basa_ekle on'u (0 − 1 + 6) % 6 = 5'e alır ve 1'i 5 numaralı hücreye yazar. İkincisi on'u 4'e alır ve 2'yi 4 numaralı hücreye yazar. sona_ekle 3, (4 + 2) % 6 = 0 numaralı hücreye yazar. Deque'nin sırası 2, 1, 3'tür; bastan_al 2'yi verir.

7. Round robin benzetiminde üç sürecin her birinin 3 birim işi vardır ve Q = 2'dir. Süreçler hangi anlarda biter?

   Cevap

   İlk turda P0 0–2, P1 2–4, P2 4–6 arasında çalışır; her birinin 1 birimi kalır ve sona döner. İkinci turda P0 6–7, P1 7–8, P2 8–9 arasında çalışır. Bitiş anları P0 için 7, P1 için 8, P2 için 9'dur.

8. İki yığınla kurulan kuyruğa 1, 2, 3, 4 eklenir; bir öğe alınır; 5 eklenir; dört öğe daha alınır. Çıkış sırası nedir? Toplam kaç push yapılır?

   Cevap

   İlk almada çıkış yığını boştur; 4, 3, 2, 1 aktarılır ve 1 alınır. 5 giriş yığınına konur. Sonraki üç alma çıkış yığınından 2, 3, 4'ü verir. Son almada çıkış boştur; 5 aktarılır ve alınır. Çıkış sırası 1, 2, 3, 4, 5'tir. push sayısı 5 ekleme ve 5 aktarma olmak üzere 10'dur.

9. Birinci yöntemde (bir hücreyi boş bırakmak) MAX hücreli kuyruk neden en çok MAX − 1 öğe tutar? Kuyruğun MAX öğe tutmasına izin verilseydi ne olurdu?

   Cevap

   MAX'ıncı öğe eklenseydi arka ilerleyip on'a eşit olurdu. on == arka ise boş kuyruğun koşuludur. Kod dolu kuyruğu boş sanır: kuyruk_al alt taşma bildirir, kuyruk_ekle ise öğelerin üzerine yazar. İki indisin farkı yalnız MAX değer alır, oysa öğe sayısı MAX + 1 değer alabilir; bir durumdan vazgeçmek gerekir.

7.12İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Kesim 3.3 ve 4.3: bu notun izlediği dizi tabanlı ve bağlı kuyruk gerçeklemelerinin, dairesel kuyruğun ve tek dizide birden çok kuyruğun kaynağıdır.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Kesim 10.1: kuyruğu sözde kodla, dairesel dizi üzerinde kısa ve kesin biçimde verir; deque ve iki yığınla kuyruk alıştırma olarak yer alır.
• R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 4: soyut veri tiplerini, yığın ve kuyruk arayüzlerini ve bunların dizi ve bağlı liste gerçeklemelerini karşılaştırmalı olarak işler.

7.13Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Bölüm 3.3 ve 4.3.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, Bölüm 10.1 (kuyruklar, deque alıştırmaları).
3. R. Sedgewick, Algorithms in C, Kısım 1–4, Bölüm 4.

İlgili sayfalar: Bölüm 7 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.