Bölüm 8: Kuyruklar ve Deque

8.1Kuyruk ADT'si

Bir veri yapısı iki düzeyde anlatılabilir. Birinci düzey yapının ne yaptığını söyler: hangi işlemler vardır, her işlem neyi değiştirir ve ne döndürür. İkinci düzey bunun nasıl yapıldığını söyler: veriler bellekte hangi biçimde durur, her işlem hangi adımlarla yürür. Birinci düzeydeki tarife soyut veri tipi (abstract data type, kısaca ADT) denir. Bu kesim kuyruğu soyut düzeyde, yani gerçeklemeden bağımsız olarak tanıtır.

8.1.1Kuyruk nedir?

Market kasasındaki sırayı düşünelim. Kasaya yeni gelen müşteri sıranın sonuna geçer. Kasiyer her seferinde sıranın en önündeki müşteriye hizmet verir. Hizmeti biten müşteri sıradan ayrılır, arkasındaki öne geçer. Sıranın ortasına girmek ya da ortadan birini öne almak kurala aykırıdır. Bilet gişesi, banka veznesi ve otoyol gişesi de aynı kuralla işler: önce gelen önce hizmet alır.

Bilgisayar bilimindeki kuyruk (queue) bu düzeni taklit eder. Öğeler bir sıra hâlinde tutulur ve sıranın iki ucu ayrı işlere ayrılır. Yeni öğe her zaman arka (rear) uca eklenir. Çıkarma ise her zaman ön (front) uçtan yapılır. Böylece kuyruktan çıkan öğe, o anda kuyrukta bekleyenler arasında en uzun süredir bekleyen, yani en eski öğedir.

Kuyruğu bir önceki konudaki yığınla karşılaştırmak öğreticidir. Yığında ekleme ve çıkarma aynı uçta, üstte yapılır; en son giren ilk çıkar (LIFO). Kuyrukta ise ekleme ve çıkarma ayrı uçlardadır; en önce giren ilk çıkar. Bir yapıya 1, 2, 3 sırasıyla öğe eklenip üç kez çıkarma yapılsın. Yığından 3, 2, 1 çıkar; giriş sırası tersine döner. Kuyruktan 1, 2, 3 çıkar; giriş sırası aynen korunur. Kuyruğun asıl işi budur: gelen işleri geliş sırasıyla saklamak ve aynı sırayla teslim etmek.

Kuyruğun her iki ucu da açıktır, ama her uç tek yönde kullanılır. Bu yüzden kuyruk doğrusal bir yapıdır: her öğenin (ilk öğe dışında) tek bir öncülü, (son öğe dışında) tek bir ardılı vardır. Öğeler arasında dallanma yoktur.

8.1.2Temel işlemler

Kuyruğun iki temel işlemi vardır. Adları İngilizcede kalıplaşmıştır ve ders boyunca aynen kullanılır.

• Ekleme (enqueue): Kuyruğun sonuna, yani arkasına yeni bir öğe ekler. “Sıraya girmek” olarak düşünülebilir.
• Çıkarma (dequeue): Kuyruğun başındaki, yani önündeki öğeyi çıkarır ve döndürür. İlk giren öğe ilk çıkar.

İki işlem de iyi bir gerçeklemede O(1) zamanlıdır: kuyrukta kaç öğe olursa olsun sabit sayıda adımda biter. Bunun için gerçeklemenin iki ucu da doğrudan, aramaya gerek kalmadan bulabilmesi gerekir. Dizi ve bağlı liste gerçeklemelerinin bütün tasarımı bu tek amaca hizmet eder.

Kuyrukta ortadaki bir öğeye doğrudan erişilmez; yalnız ön ve arka uçlar kullanılır. Bu bir eksiklik değil, bilinçli bir kısıtlamadır. Kuyruğu kullanan kod sırayı bozamaz, öğe atlatamaz. Kısıtlama aynı zamanda gerçeklemeyi de kolaylaştırır: yalnız iki uç hızlı olmak zorundadır.

8.1.3Kuyruk ADT'sinin işlemleri ve arayüzü

İki temel işleme birkaç yardımcı işlem eklenince kuyruk ADT'si tamamlanır. Tablo 8.1 bu işlemleri özetler.

Bu işlemlerden yalnız enqueue ve dequeue kuyruğu değiştirir. Ötekiler yalnız bilgi verir. first() ile dequeue() arasındaki fark yığındaki top() ile pop() arasındaki farka benzer: ikisi de öndeki öğeyi döndürür, ama first() onu yerinde bırakır. Öndeki öğeye bakıp karar vermek, sonra gerekiyorsa çıkarmak gereken durumlarda önce first() kullanılır.

isFull() yalnız kapasitesi baştan belirlenmiş gerçeklemelerde anlamlıdır. Bağlı liste ile gerçeklenen ya da dolunca büyüyen bir kuyruk hiçbir zaman “dolu” olmaz; bellek yettiği sürece yeni öğe kabul eder.

ADT'yi Java'da yazmanın doğal yolu bir arayüz (interface) tanımlamaktır. Arayüz yalnız metotların imzalarını verir, gövdelerini vermez. Aşağıdaki arayüz, Goodrich, Tamassia ve Goldwasser'in ders kitabındaki kuyruk arayüzünün kısaltılmış biçimidir:

public interface Queue<E> {
    int size();
    boolean isEmpty();
    void enqueue(E e);
    E first();    // boşsa null
    E dequeue();  // boşsa null
}

Queue<E> içindeki E bir tür parametresidir: kuyruğun hangi türden öğe tutacağı, kuyruk oluşturulurken belirlenir. Queue<Integer> tamsayı, Queue<String> dize tutan bir kuyruktur. Böyle tür parametresi alan sınıf ve arayüzlere jenerik (generic) denir. Arayüzde rear() ve isFull() yoktur. İlki kuyruğun temel kullanımında gerekmez; ikincisi ise arayüzün sınırsız bir kuyruğu da kapsaması için bilerek dışarıda bırakılmıştır.

Yorum satırları önemli bir sözleşmeyi kaydeder: kuyruk boşken first() ve dequeue() null döndürür. Boş kuyruktan çıkarma denemesine alt taşma (underflow), sabit kapasiteli dolu bir kuyruğa ekleme denemesine taşma (overflow) denir. İkisi de hata durumudur. Hatanın nasıl bildirileceği ise bir tasarım kararıdır. Goodrich'in arayüzü boş kuyrukta null döndürür; bazı gerçeklemeler istisna (exception) fırlatır. Bu notta dizi tabanlı dairesel kuyruk ve bağlı liste kuyruğu istisna fırlatır, çift uçlu kuyruk ise null döndürür. Seçilen yol, kodu kullanan programcıyı doğrudan ilgilendirir: null dönüşü denetlenmezse hata sessizce ilerler, istisna ise programı hemen durdurur.

8.1.4Kuyruk işlemleri adım adım

İşlemlerin birlikte nasıl çalıştığını küçük bir işlem dizisi üzerinde izleyelim. Boş bir kuyruğa sırayla enqueue(20), enqueue(10), enqueue(15) ve üç kez dequeue() uygulanıyor. Kuyruğun önünü gösteren referansın adı on, arkasını gösteren referansın adı arka'dır. Java'da değişken adında Türkçe karakter kullanılabilse de kodlarda alışkanlık olarak “ö” yerine “o” yazılır.

Örnekte iki uç durum dikkat çeker. Birincisi boş kuyruğa ilk eklemedir: bu öğe hem ön hem arka olduğu için iki referansın da güncellenmesi gerekir. İkincisi son öğenin çıkarılmasıdır: kuyruk boşalınca yalnız on değil, arka da null yapılmalıdır. Gerçeklemelerdeki hataların büyük çoğunluğu bu iki uç durumdan çıkar.

Kuyruk sorularını çözerken pratik bir yöntem şudur: her işlemden sonra kuyruğun içeriği önden arkaya tek satıra yazılır, işlemin döndürdüğü değer de yanına not edilir. Sıra hep aynı yönde yazılırsa yanlış uçtan çıkarma hatası pek yapılmaz.

8.1.5Java'da kuyruk: java.util.Queue

Java kütüphanesi kuyruk için java.util.Queue<E> arayüzünü sunar. Bu arayüzde her işlemin iki biçimi vardır. Birinci biçim başarısızlıkta istisna fırlatır, ikinci biçim özel bir değer döndürür. Tablo 8.2 iki grubu yan yana gösterir.

Boş bir kuyrukta remove() ve element() NoSuchElementException fırlatır; poll() ve peek() ise null döndürür. Kapasitesi sınırlı bir kuyruk dolduğunda add(e) IllegalStateException fırlatır, offer(e) ise false döndürür. Sınırsız kuyruklarda (aşağıdaki iki sınıf da sınırsızdır) offer her zaman true döndürür.

Queue bir arayüz olduğu için doğrudan nesnesi oluşturulamaz. Onu gerçekleyen iki yaygın sınıf vardır:

• ArrayDeque: dairesel dizi ile gerçeklenir ve genellikle en hızlı seçenektir. Bu notta anlatılan dairesel kuyruğun büyüyebilen bir biçimidir.
• LinkedList: bağlı liste ile gerçeklenir. Liste işlemlerini de destekler, ama her öğe için ayrı bir düğüm nesnesi oluşturur.

Aşağıdaki kod ArrayDeque ile oluşturulmuş bir kuyruk üzerinde temel işlemleri gösterir. Değişkenin türü Queue<Integer>'dır; böylece kod yalnız kuyruk işlemlerini kullanabilir ve ileride gerçekleyen sınıf kolayca değiştirilebilir.

Queue<Integer> q = new ArrayDeque<>();
q.offer(20);
q.offer(10);
q.offer(15);        // [20, 10, 15]
q.peek();           // 20, çıkarmaz
q.poll();           // 20 → [10, 15]
q.poll();           // 10 → [15]
q.size();           // 1
q.poll();           // 15 → []
q.poll();           // null (boş)

İzlemede iki nokta önemlidir. peek() 20'yi döndürür ama kuyruğu değiştirmez; hemen ardından gelen poll() yine 20'yi verir. Son poll() boş kuyrukta çağrılmıştır. Bu çağrı istisna fırlatmaz, null döndürür. Aynı noktada remove() çağrılsaydı program NoSuchElementException ile dururdu.

Adlandırma konusunda da bir not düşmek gerekir. Kendi yazdığımız sınıflarda işlem adları ADT'deki gibi enqueue/dequeue (ya da Türkçe ekle/cikar) olur. Java kütüphanesinde ise aynı işlemler offer/poll/peek üçlüsüyle yapılır. Ad farklıdır, davranış aynıdır.

8.1.6Kuyrukların kullanıldığı yerler

Kuyruk, “işler geldiği sırayla yapılsın” istenen her yerde doğal çözümdür. Dört yaygın örnek şunlardır:

• İşletim sistemi çizelgeleyicisi. Çalışmaya hazır süreçler bir hazır kuyruğunda bekler. İşlemci (CPU) sırayla bu süreçlere dağıtılır. Bu fikrin en sade biçimi olan round robin çizelgeleme 8.5.1'de ayrıntılı işlenir.
• Yazdırma kuyruğu. Bir yazıcıya aynı anda birden çok belge gönderilebilir. Yazıcı belgeleri geliş sırasıyla basar; sonradan gelen belge bekler.
• Tamponlar (buffer). Klavye girdisi, ağ paketleri ve video akışı bir tamponda bekletilir. Veriyi üreten taraf ile kullanan taraf farklı hızlarda çalışabilir. Tampon bu hız farkını dengeler: üretici hızlıyken veri birikir, tüketici hızlıyken birikmiş veri eritilir.
• Genişlik öncelikli arama (breadth-first search, BFS). Bir çizgede ya da ağaçta keşfedilen düğümler kuyrukta sıraya alınır. Böylece başlangıca yakın düğümler uzak olanlardan önce ziyaret edilir ve gezinme seviye seviye ilerler. 8.5.4'teki ikilik sayı üretimi bu fikrin küçük bir örneğidir.

Bu örneklerin ortak noktası adalet ve sıranın korunmasıdır. Yazıcı, önce gönderilen belgeyi önce basmalıdır. Ağ paketleri, gönderildikleri sırayla işlenmezse bir video karıştırılmış kareler gösterir. Çizelgeleyici, bir süreci sürekli bekletmemelidir. Kuyruk bu gereksinimleri yapısı gereği karşılar: bir öğe kuyruğa girdikten sonra, ondan önce girmiş öğeler çıkınca sıra mutlaka ona gelir.

8.2Dizi ile kuyruk

Kuyruğu gerçeklemenin ilk aklagelen yolu öğeleri bir dizide tutmaktır. Dizi bellekte ardışık hücrelerden oluşur ve her hücreye indisiyle O(1) zamanda erişilir. Kuyruk için gereken tek şey iki ucun yerini bilmektir. Bu kesim önce en basit fikri dener, onun neden yer israf ettiğini gösterir ve ardından sorunu dairesel kuyrukla çözer.

8.2.1Dizi temsili

Öğeler bir dizide tutulur ve iki indis kuyruğun uçlarını gösterir:

• on (ön, front): ilk öğenin, yani bir sonraki çıkarmada alınacak öğenin indisi.
• arka (rear): son öğenin, yani en son eklenen öğenin indisi.

Eklemede arka bir artar ve yeni öğe dizi[arka]'ya yazılır. Çıkarmada dizi[on] alınır ve on bir artar. Öğeler yerinden kaydırılmaz; yalnız iki indis ilerler. Bu yüzden iki işlem de sabit sayıda adım atar ve O(1)'dir. Yöntem basit ve hızlıdır, ama dizinin kapasitesi sabittir.

Şekil 8.4 yöntemin zayıf noktasını şimdiden gösterir. Kuyruğun önü çıkarmalarla sağa kayar. Önde boşalan yuvalar geride kalır ve bir daha kullanılmaz. Öğe sayısı kuyruğun içeriğine değil, şimdiye kadar yapılan ekleme sayısına bağlı olarak dizinin sonuna yaklaşır.

8.2.2Basit dizi kuyruğunun sorunu

Sorunu somut bir örnekle görelim. Kapasitesi N = 6 olan basit dizi kuyruğu on = 0, arka = −1 ile başlıyor. arka = −1, henüz hiç öğe eklenmediğini gösterir: ilk eklemede arka 0'a çıkacak ve öğe 0. indise yazılacaktır. Kuyruğa sırayla 10, 20, 30, 40 ekleniyor, üç kez çıkarma yapılıyor ve ardından 50, 60, 70 eklenmek isteniyor.

İlk dört eklemede arka 0'dan 3'e çıkar. Üç çıkarma 10, 20 ve 30'u döndürür ve on'u 3'e taşır. Bu noktada on ve arka aynı yuvayı, 40'ı gösterir; kuyrukta tek öğe vardır. 50 ve 60 eklenince arka 5'e, yani dizinin son indisine (N − 1) ulaşır. enqueue(70) için arka + 1 = 6 = N olur. Dizinin sonunda yer kalmamıştır ve kuyruk “dolu” der.

Oysa kuyrukta yalnız üç öğe vardır: 40, 50 ve 60. 0, 1 ve 2. indisler boştur, ama basit dizi kuyruğu boşalan yuvaları yeniden kullanamaz. Altı yuvalık dizinin yarısı boşa gitmiştir. Daha kötüsü, kuyruk hiç dolmadan, örneğin her eklemeden hemen sonra bir çıkarma yapılsa bile, altı eklemeden sonra arka dizinin sonuna dayanır. Basit dizi kuyruğunun ömrü, içindeki öğe sayısıyla değil toplam ekleme sayısıyla sınırlıdır.

Sorunun iki çözümü vardır.

Çözüm 1: kaydırma. Her çıkarmada kalan öğeler bir yuva sola kaydırılır. Böylece kuyruğun önü hep dizi[0]'da kalır ve on indisine gerek bile kalmaz. Aşağıdaki metot bu fikri gerçekler; boyut, kuyruktaki öğe sayısıdır:

public int dequeue() {              // kaydırmalı basit dizi kuyruğu
    if (boyut == 0)
        throw new IllegalStateException("boş");
    int sonuc = dizi[0];            // ön her zaman dizi[0]
    for (int i = 1; i < boyut; i++)
        dizi[i - 1] = dizi[i];      // herkes bir yuva sola
    boyut--;
    return sonuc;
}

Döngü boyut − 1 öğeyi kaydırır. Kuyrukta n öğe varken bir çıkarma n − 1 atama yapar; çıkarma O(n) olur. 1000 öğelik bir kuyruğun tamamını boşaltmak 999 + 998 + … + 1 + 0 = 499.500 atama gerektirir. Yer israfı biter, ama hız gider.

Çözüm 2: dairesel dizi. İndisler dizinin sonuna gelince başa sarar. Öğeler hiç kaydırılmaz, boşalan yuvalar yeniden kullanılır ve her işlem O(1) kalır. Bu yapıya dairesel kuyruk denir.

8.2.3Dairesel kuyruk

Basit dizi kuyruğunda dizinin sonu bir duvardır: arka son indise ulaşınca ilerleyecek yer kalmaz. Dairesel kuyruk bu duvarı kaldırır. Dizinin son yuvasından sonra ilk yuvaya dönülür. Dizinin başı ve sonu mantıksal olarak birleşir ve bir halka oluşturur. Bellekte dizi yine düz bir hücre sırasıdır; halka yalnız indislerin hesaplanma biçiminde vardır.

Dairesel kuyruk normal bir kuyruk gibi FIFO düzeninde çalışır. Fark yalnız indislerin ilerleme biçimindedir. Basit dizide i + 1 olan “bir sonraki indis”, dairesel dizide (i + 1) % N olur. i < N − 1 iken iki ifade aynı sonucu verir. i = N − 1 olduğunda ise (N − 1 + 1) % N = N % N = 0 çıkar ve indis başa sarar. Boşalan yuvalar böylece yeniden kullanılır ve öğe kaydırmaya gerek kalmaz.

Bu notta dairesel kuyruk iki alanla tutulur: bas (ilk öğenin indisi) ve boyut (öğe sayısı). Arka uç ayrı bir alan olarak saklanmaz. Bir sonraki öğenin yazılacağı boş yuva gerektiğinde (bas + boyut) % N ile hesaplanır.

Halka görünümü dizinin “sonu” diye bir şey olmadığını açıkça gösterir. 7. yuvanın komşusu hem 6. hem 0. yuvadır. Kuyruk saat yönünde büyür ve küçülür: ekleme arkada saat yönünde ilerler, çıkarma da önü saat yönünde ilerletir. Kuyruk halkanın herhangi bir yerinde başlayıp herhangi bir yerinde bitebilir.

8.2.4İndislerin mod ile hesaplanması

Dairesel kuyrukta bütün indisler bas, boyut ve N'den hesaplanır. Mod işlemi (%), bir sayının N'ye bölümünden kalanı verir. Negatif olmayan her a için a % N sonucu 0 ile N − 1 arasındadır; yani her zaman geçerli bir dizi indisidir. Tablo 8.5 dört temel formülü N = 8, bas = 6, boyut = 4 için hesaplar.

Formüllerin hepsi aynı düşünceden çıkar: kuyruğun k. öğesi, baştan k adım ötededir. Düz dizide bu yer bas + k olurdu. Dairesel dizide bas + k dizinin sınırını aşabilir; % N taşan kısmı başa sarar. Örnekte C kuyruğun 2. öğesidir (k = 2). 6 + 2 = 8 dizinin dışındadır, ama 8 % 8 = 0 C'nin gerçek yerini verir.

Sonraki boş yuva formülü de bu kuralın özel bir durumudur: kuyrukta boyut öğe varsa 0'dan boyut − 1'e kadar indisler dolu, boyut. konum ise boştur. Son öğe boyut − 1. konumdadır. Mod işlemi dizinin sonundan başına geçişi tek bir ifadeyle çözer; if ile “sona geldiysem başa dön” denetimi yazmaya gerek kalmaz.

Formüllerde toplananlar negatif değildir ve bas < N, boyut ≤ N olduğu için toplam 2N'yi geçmez. Bu yüzden % en fazla bir tur geri sarar. Bir indisi geri almak gerektiğinde ise dikkat gerekir. Örneğin önün bir öncesindeki yuva (bas − 1) % N ile hesaplanırsa, bas = 0 için Java −1 % N = −1 verir. Java'da % işleminin sonucu bölünenin işaretini taşır. Doğru ifade (bas − 1 + N) % N'dir. Çift uçlu kuyruğun diziyle gerçeklenmesinde başa ekleme tam bu ifadeyi kullanır.

8.2.5Dolu mu, boş mu?

Dairesel kuyruğu yalnız iki indisle tutmak ilk bakışta yeterli görünür: bas ilk öğeyi, arka bir sonraki yazma yerini göstersin. Ancak bu temsilde boş ve dolu kuyruk ayırt edilemez. Boş kuyrukta bas ile arka aynı yuvayı gösterir. Kuyruğa N öğe eklendiğinde ise arka halkayı tam bir tur dolaşıp yine bas'a gelir. İki durumda da bas == arka'dır.

Bu belirsizliği gidermenin iki yaygın yolu vardır.

1. Öğe sayacı tutmak. İndislerin yanında bir boyut alanı tutulur. Boş koşulu boyut == 0, dolu koşulu boyut == N'dir. Dizinin N yuvasının tamamı kullanılır. Bu notta (ve sunumda) kullanılan yöntem budur. Sayaç zaten tutulduğu için arka indisini ayrıca saklamaya da gerek kalmaz; (bas + boyut) % N ile hesaplanır.

2. Bir yuvayı boş bırakmak. Kuyruk hiçbir zaman N öğeye ulaşmaz; en fazla N − 1 öğe saklanır. Boş koşulu bas == arka, dolu koşulu (arka + 1) % N == bas'tır. Dolu kuyrukta arka, bas'ın hemen bir gerisinde kalır ve aradaki tek yuva boştur. Sayaç gerekmez, ama bir yuva hep boşa gider.

İki yöntem arasındaki fark küçüktür. Sayaç yöntemi bir tamsayı alanı fazla tutar, ama dizinin bütün yuvalarını kullanır ve kodu daha okunur kılar: boyut == 0 ve boyut == N ifadeleri ne denetlendiğini doğrudan söyler. Bir yuva boş yöntemi ise sayacın güncellenmesinin pahalı ya da sakıncalı olduğu yerlerde tercih edilir. Örneğin bir üretici ve bir tüketici aynı tamponu eş zamanlı kullanıyorsa, üretici yalnız arka'yı, tüketici yalnız bas'ı değiştirir. Ortak bir sayaç olmadığı için iki tarafın aynı alanı güncellemesi gerekmez.

8.2.6Dairesel kuyruk adım adım

Sayaç yöntemiyle çalışan dairesel kuyruğu, kapasitesi N = 5 olan bir dizi üzerinde izleyelim. Başlangıçta bas = 0, boyut = 0'dır. Ekleme ekle, çıkarma cikar adıyla yapılır. Her eklemede yeni öğe (bas + boyut) % 5 yuvasına yazılır ve boyut bir artar. Her çıkarmada dizi[bas] döndürülür, yuva boşaltılır, bas (bas + 1) % 5 olur ve boyut bir azalır.

İzlemenin ilk beş satırı basit dizi kuyruğundakinden farksızdır. Üç ekleme 0, 1 ve 2. yuvaları doldurur. İki çıkarma 10 ve 20'yi döndürür ve bas'ı 2'ye taşır. Öğeler yerinden oynamaz; yalnız bas ilerler.

Asıl fark ekle(60) satırında görülür. Ekleme yeri (2 + 3) % 5 = 0'dır: dizinin sonu aşılmış ve indis başa sarmıştır. Basit dizi kuyruğu bu noktada “dolu” derdi. Dairesel kuyruk ise boşalmış 0. yuvayı kullanır. ekle(70) 1. yuvaya yazılır ve boyut 5'e ulaşır. Kuyruk artık gerçekten doludur: beş yuvanın beşi de doludur ve hiçbiri boşa gitmemiştir.

Dolu kuyrukta bir sonraki yazma yeri (2 + 5) % 5 = 2'dir, yani bas'ın kendisi. Yalnız indislere bakılsaydı kuyruk boş sanılabilirdi. boyut == 5 bilgisi bu karışıklığı önler.

Ardından gelen beş çıkarma önden arkaya 30, 40, 50, 60 ve 70'i döndürür. Üçüncü çıkarmada bas (4 + 1) % 5 = 0 olur; bu kez ön de başa sarmıştır. Son çıkarmadan sonra boyut = 0'dır ve kuyruk yine boştur. Çıkış sırası 30, 40, 50, 60, 70'tir. Bu, öğelerin giriş sırasıyla aynıdır: dairesel düzen FIFO kuralını bozmaz.

8.2.7Kod: DaireselKuyruk sınıfı

Aşağıdaki sınıf sayaç yöntemiyle çalışan dairesel kuyruğun alanlarını, yapıcısını ve durum sorgularını içerir. Ekleme ve çıkarma metotları 8.2.8'dedir.

public class DaireselKuyruk<E> {
    private E[] dizi;       // öğeleri saklar
    private int bas = 0;    // ilk öğenin indisi (front)
    private int boyut = 0;  // öğe sayısı (size)

    @SuppressWarnings("unchecked")
    public DaireselKuyruk(int kapasite) {
        dizi = (E[]) new Object[kapasite];
    }
    public int boyut()      { return boyut; }
    public boolean bosMu()  { return boyut == 0; }
    public boolean doluMu() { return boyut == dizi.length; }
    public E ilk()          { return bosMu() ? null : dizi[bas]; }
    // ekle(), cikar()
}

Kod satır satır şöyle çalışır:

• dizi öğeleri tutar. bas ilk öğenin indisi, boyut öğe sayısıdır. İkisi de 0 ile başlar, çünkü yeni kuyruk boştur.
• Yapıcı istenen kapasitede bir dizi ayırır. Java'da new E[kapasite] yazılamaz: tür parametresi E çalışma zamanında bilinmediği için jenerik dizi doğrudan oluşturulamaz. Bunun yerine bir Object dizisi oluşturulur ve (E[]) ile dönüştürülür. Derleyici bu dönüşüm için denetlenmemiş dönüşüm uyarısı verir. @SuppressWarnings("unchecked") bu uyarıyı yalnız yapıcı için susturur. Dizi sınıfın dışına hiç verilmediği sürece dönüşüm güvenlidir.
• boyut() öğe sayısını döndürür. bosMu() yalnız boyut == 0 sorusunu sorar. doluMu() ise boyut == dizi.length sorusunu sorar; dizinin uzunluğu kapasitedir.
• ilk() kuyruk boşsa null, değilse dizi[bas]'ı döndürür ve kuyruğu değiştirmez. Burada ? : koşul işlecidir: koşul doğruysa ilk, yanlışsa ikinci değeri verir.

Arka indisi ayrıca saklanmaz; gerektiğinde (bas + boyut) % dizi.length ile hesaplanır. Bunun bir yararı vardır. Hem arka hem boyut saklansaydı, her işlemde ikisinin birlikte ve doğru güncellenmesi gerekirdi. Bir metotta birini güncelleyip ötekini unutmak, iki alanın birbirine uymadığı tutarsız bir duruma yol açardı. Aynı bilgiyi tek yerde tutmak bu riski ortadan kaldırır.

Bütün metotlar döngüsüzdür ve sabit sayıda adım atar; her biri O(1)'dir. Sınıf, kapasite kadar yuvalı bir dizi kullanır. Alan, kuyrukta kaç öğe olduğundan bağımsız olarak O(N)'dir.

8.2.8Kod: ekle() ve cikar()

Sınıfın iki temel metodu şunlardır:

public void ekle(E oge) {           // enqueue
    if (doluMu())
        throw new IllegalStateException("dolu");
    int son = (bas + boyut) % dizi.length;
    dizi[son] = oge;
    boyut++;
}

public E cikar() {                  // dequeue
    if (bosMu())
        throw new IllegalStateException("boş");
    E oge = dizi[bas];
    dizi[bas] = null;               // referansı bırak
    bas = (bas + 1) % dizi.length;
    boyut--;
    return oge;
}

ekle önce doluluğu sorar. Kuyruk doluysa IllegalStateException("dolu") fırlatılır; bu, taşmanın kodda bildirilme biçimidir. Yer varsa ekleme yeri son değişkenine hesaplanır, öğe oraya yazılır ve boyut bir artar. bas değişmez: eklemek kuyruğun önünü etkilemez.

cikar önce boşluğu sorar. Kuyruk boşsa IllegalStateException("boş") fırlatılır; bu da alt taşmadır. Değilse öndeki öğe oge'ye alınır. Ardından üç güncelleme yapılır: yuvaya null yazılır, bas bir ilerler, boyut bir azalır. Son olarak saklanan öğe döndürülür.

dizi[bas] = null; satırı kuyruğun doğruluğu için gerekli değildir. Bu satır olmasa da cikar doğru öğeyi döndürür; o yuva bir sonraki sarmada zaten üzerine yazılır. Satırın amacı bellekle ilgilidir. Java'da belleği çöp toplayıcı (garbage collector) geri alır ve bunu yalnız hiçbir referansın göstermediği nesneler için yapar. Kuyruktan çıkmış ama dizide hâlâ duran bir nesne temizlenemez. Büyük nesneler (görüntüler, dosya tamponları) taşıyan bir kuyrukta bu fark bellekte belirgin bir sızıntıya dönüşebilir.

Satırların sırası da önemlidir. oge = dizi[bas] satırı, null atamasından önce gelmelidir; yoksa döndürülecek değer silinmiş olur. bas da null atamasından sonra ilerlemelidir; yoksa yanlış yuva boşaltılır.

8.2.9Kod izleme: ekle()

ekle metodunu, dizinin sonundan başa sarmayı gerektiren bir durumda izleyelim. Başlangıçta dizi.length = 5, bas = 2, boyut = 2'dir; kuyrukta önden arkaya 30 (2. yuva) ve 40 (3. yuva) vardır. Kuyruğa sırayla 50, 60, 70 ve 80 eklenecektir. İzlemede kullanılan metot şudur:

public void ekle(E oge) {
  if (doluMu())
    throw new IllegalStateException("dolu");
  int son = (bas + boyut) % dizi.length;
  dizi[son] = oge;
  boyut++;
}

ekle(50)'de denetim boyut'u (2) kapasiteyle (5) karşılaştırır; yer vardır. Ekleme yeri (2 + 2) % 5 = 4'tür. Bu hesapta mod işlemi bir şey değiştirmez, çünkü 4 zaten dizinin içindedir. dizi[4] = 50 yazılır ve boyut 3 olur. bas değişmez; ön hâlâ dizi[2]'dir.

ekle(60)'ta ekleme yeri (2 + 3) % 5 = 5 % 5 = 0'dır. Dizinin sonu aşılmış ve indis başa sarmıştır. 60, 0. yuvaya yazılır. Mantıksal olarak 60 kuyruğun en arkasındadır, fiziksel olarak ise dizinin en başında durur. ekle(70) aynı biçimde (2 + 4) % 5 = 1'e yazılır ve boyut 5'e çıkar.

ekle(80)'de denetim 5 == 5 sonucunu verir. Kuyruk doludur ve IllegalStateException("dolu") fırlatılır. Dizi ve alanlar değişmeden kalır. Kapasite tam 5 öğede tükenmiştir; hiçbir yuva boşa gitmemiştir.

8.2.10Kod izleme: cikar()

Önceki izlemenin sonundaki dolu kuyruktan devam edelim. bas = 2'dir ve kuyruk önden arkaya 30, 40, 50, 60, 70'tir. Üç kez cikar() çağrılacaktır.

public E cikar() {
  if (bosMu())
    throw new IllegalStateException("boş");
  E oge = dizi[bas];
  dizi[bas] = null;           // referansı bırak
  bas = (bas + 1) % dizi.length;
  boyut--;
  return oge;
}

Her çağrı aynı beş adımı atar. Önce bosMu() sorulur; boyut sıfırdan büyük olduğu için devam edilir. Sonra oge = dizi[bas] ile öndeki, yani en eski öğe alınır. İlk çağrıda bu dizi[2] = 30'dur. Ardından dizi[2] = null ile yuva boşaltılır. bas (2 + 1) % 5 = 3'e ilerler, boyut 4'e iner ve 30 döndürülür.

Üçüncü çağrıda öndeki öğe dizinin son yuvasındadır: dizi[4] = 50. bas (4 + 1) % 5 = 5 % 5 = 0 olur, yani ön de başa sarar. Kuyrukta 60 (0. yuva) ve 70 (1. yuva) kalır ve ön artık 60'tır. Fiziksel olarak dizinin başında duran bu iki öğe, mantıksal olarak da kuyruğun önündedir.

Çıkarmalarda hiçbir öğe yerinden oynamaz ve hiçbir döngü çalışmaz. Her çağrı sabit sayıda adım atar: O(1).

8.2.11Dolu dairesel kuyruğu büyütme

Sabit kapasiteli kuyruk dolunca hata verir. Kapasitenin önceden bilinmediği durumlarda daha iyi bir yol vardır: dolu kuyruğa ekleme yapılırken iki katı büyüklükte yeni bir dizi ayırıp öğeleri oraya taşımak. Aşağıdaki kod ekle'yi bu biçimde değiştirir:

private void buyut(int yeniKap) {
  E[] yeni = (E[]) new Object[yeniKap];
  for (int k = 0; k < boyut; k++)
    yeni[k] = dizi[(bas + k) % dizi.length];
  dizi = yeni;
  bas = 0;
}
public void ekle(E oge) {
  if (boyut == dizi.length) buyut(2 * dizi.length);
  dizi[(bas + boyut) % dizi.length] = oge;
  boyut++;
}

buyut metodu, istenen kapasitede yeni bir dizi ayırır. Ardından kuyruktaki öğeleri mantıksal sırayla yeni dizinin başına kopyalar: kuyruğun k. öğesi eski dizide (bas + k) % dizi.length yuvasındadır ve yeni dizinin k. yuvasına yazılır. Kopyalama bitince eski dizi bırakılır ve bas 0 yapılır, çünkü kuyruğun önü artık yeni dizinin başındadır. ekle, dolu kuyrukta önce kapasiteyi ikiye katlar, sonra her zamanki gibi yazar.

Örnek olarak kapasitesi 4 olan dolu bir kuyruk düşünelim. bas = 2'dir; kuyruk mantıksal olarak A, B, C, D, dizide ise fiziksel olarak C, D, A, B biçimindedir. Kuyruk daha önce başa sarmıştır. Şimdi ekle(E) çağrılıyor.

k = 2 adımında mod işlemi devreye girer: (2 + 2) % 4 = 0. Eski dizinin sonu aşılmış ve kopyalama başa sarmıştır. Bu sayede başa sarmış C ve D, A ile B'nin hemen arkasına, doğru sıraya yerleşir. Büyütmeden sonra kuyruk yeni dizide düzgün bir sıra hâlindedir ve bas = 0'dır. E, (0 + 4) % 8 = 4. yuvaya yazılır.

Büyütme bütün öğeleri kopyaladığı için tek başına O(n) sürer. Buna karşın kapasite her seferinde iki katına çıktığı için büyütme seyrek yapılır. Bu durumda tek tek işlemlere değil, uzun bir işlem dizisinin toplam maliyetine bakmak daha anlamlıdır. Bu tür incelemeye amortize analiz (amortized analysis) denir.

Somut bir sayı verelim. Kapasitesi 4 olan boş kuyruğa hiç çıkarma yapmadan 17 öğe eklensin. Büyütmeler 5. eklemede (4 kopya), 9. eklemede (8 kopya) ve 17. eklemede (16 kopya) yapılır: toplam 4 + 8 + 16 = 28 kopya. 17 yazmayla birlikte toplam maliyet 45'tir ve 3 · 17 = 51'in altındadır. Teoremin söylemediği bir şeye de dikkat etmek gerekir: tek bir ekleme yine O(n) sürebilir. Örnekteki 17. ekleme tek başına 16 kopya yapmıştır. Her işlemin kısa sürmesi gereken gerçek zamanlı sistemlerde amortize sınır yetmez; en kötü durum sınırı önemlidir.

8.3Bağlı liste ile kuyruk

Dizi tabanlı kuyruğun kapasitesi baştan belirlenir; büyütme mümkündür ama kopyalama gerektirir. Bağlı liste ise öğe geldikçe yeni bir düğüm oluşturur ve hiç kopyalama yapmaz. Bu kesim kuyruğu tek yönlü bağlı listeyle gerçekler ve iki gerçeklemeyi karşılaştırır.

8.3.1Bağlı liste temsili

Bağlı liste kuyruğunda her öğe bir düğümdür (node). Düğüm iki alan taşır: öğenin değeri (veri) ve listede kendisinden sonra gelen düğümün referansı (sonraki). Kuyruğun kendisi iki referans ve bir sayaç tutar: on listenin ilk düğümünü, arka son düğümünü gösterir; uzunluk öğe sayısıdır.

class Dugum {
    int veri;
    Dugum sonraki;
    Dugum(int veri) {
        this.veri = veri;
    }
}
// alanlar:
Dugum on, arka;
int uzunluk;

Ekleme listenin sonuna, çıkarma listenin başından yapılır. Boyut dinamiktir: her ekleme yeni bir düğüm ayırır, her çıkarma bir düğümü serbest bırakır. Bu yüzden kapasite sınırı, yani “dolu kuyruk” durumu yoktur; kuyruk bellek yettiği kadar büyür. Bunun bedeli, her düğüm için fazladan bir referans saklamak ve her eklemede yeni bir nesne oluşturmaktır.

Neden ekleme sona, çıkarma başa yapılır da tersi yapılmaz? Cevap tek yönlü listenin yapısındadır. Listenin başından düğüm silmek kolaydır: on = on.sonraki tek bir atamadır ve O(1) sürer. Sona ekleme de arka referansı sayesinde kolaydır: yeni düğüm arka.sonraki'ye bağlanır ve arka ona ilerler. Oysa sondan silmek için sondan bir önceki düğümün bulunması gerekir, çünkü yeni son o düğüm olacaktır. Tek yönlü listede geriye doğru referans yoktur. O düğüme ulaşmak için listeyi baştan sona gezmek gerekir; bu da O(n)'dir. Uçlar ters seçilseydi dequeue O(n) olurdu.

8.3.2enqueue ve dequeue algoritması

Gerçekleme ne olursa olsun, iki temel işlemin adımları aynıdır. Önce algoritmayı gerçeklemeden bağımsız olarak yazalım.

enqueue(x)

1. Kuyruk dolu mu? (Yalnız sabit kapasiteli dizide sorulur.)
2. Doluysa taşma hatası ver ve bitir.
3. Değilse x'i arka konuma yaz.
4. Arkayı bir sonraki konuma ilerlet.
5. Öğe sayısını artır ve başarıyla dön.

dequeue()

1. Kuyruk boş mu?
2. Boşsa alt taşma hatası ver ve bitir.
3. Değilse öndeki öğeyi al.
4. Önü bir sonraki öğeye ilerlet.
5. Öğe sayısını azalt ve alınan öğeyi döndür.

İki gerçekleme bu adımları farklı kodlarla yapar. Tablo 8.10 adımların karşılıklarını yan yana verir.

Dairesel dizide “arkayı ilerletmek” ayrı bir adım değildir; boyut artınca bir sonraki yazma yeri kendiliğinden ilerler. Bağlı listede ise arkaya yazmak ile arkayı ilerletmek iki atamadır: önce eski son düğüm yenisine bağlanır, sonra arka yeni düğüme taşınır.

8.3.3Kod izleme: enqueue

Bağlı liste kuyruğunun enqueue metodu şudur:

public void enqueue(int veri) {
    Dugum gecici = new Dugum(veri);
    if (bosMu()) {
        on = gecici;
    } else {
        arka.sonraki = gecici;
    }
    arka = gecici;
    uzunluk++;
}

Metot önce yeni bir düğüm oluşturur. new Dugum(veri) çağrısı, veri alanı verilen değer ve sonraki alanı null olan bir düğüm döndürür. Bu düğüm henüz listeye bağlı değildir. Ardından iki durum ayrılır. Kuyruk boşsa yeni düğüm aynı zamanda ilk düğümdür ve on ona yöneltilir. Boş değilse eski son düğümün sonraki alanı yeni düğümü gösterecek biçimde ayarlanır. İki durumda da yeni düğüm artık son düğümdür; bu yüzden arka = gecici satırı if/else'in dışındadır. Son olarak uzunluk bir artar.

Boş kuyruğa sırayla enqueue(10), enqueue(15) ve enqueue(20) uygulayalım.

İlk çağrıda kuyruk boştur. on = gecici ile 10 düğümü ilk düğüm olur, arka = gecici ile son düğüm de olur. Tek düğüm hem öndür hem arkadır.

İkinci çağrıda else dalı çalışır. arka.sonraki = gecici satırı eski son düğümü (10) yeni düğüme (15) bağlar. Bu atama arka değişmeden önce yapılmalıdır, çünkü eski son düğüme yalnız arka üzerinden ulaşılır. Ardından arka = gecici ile arka 15'e ilerler. on değişmez. Üçüncü çağrı aynı adımları 20 için tekrarlar.

Hiçbir çağrıda liste gezilmemiştir. Her enqueue bir düğüm oluşturur, en çok iki referans atar ve bir sayaç artırır: O(1).

8.3.4Kod izleme: dequeue

Bağlı liste kuyruğunun dequeue metodu şudur:

public int dequeue() {
    if (bosMu())
        throw new NoSuchElementException();
    int sonuc = on.veri;
    on = on.sonraki;
    if (on == null)
        arka = null;
    uzunluk--;
    return sonuc;
}

Metot önce boşluğu sorar; kuyruk boşsa NoSuchElementException fırlatılır. Değilse öndeki değer sonuc'a alınır ve on bir sonraki düğüme ilerler. Eski ilk düğüme artık hiçbir referans bakmaz; onu çöp toplayıcı temizler. Ardından gelen if (on == null) arka = null; satırı uç durumu ele alır: çıkarılan düğüm listenin tek düğümüyse on null olmuştur ve kuyruk boşalmıştır. Bu durumda arka da null yapılır. Son olarak uzunluk bir azalır ve sonuc döndürülür.

Önceki izlemenin sonundaki 10 → 15 → 20 kuyruğuna üç kez dequeue() uygulayalım.

İlk iki çağrı aynı biçimde ilerler: öndeki değer alınır, on bir düğüm ilerler, on null olmadığı için arka'ya dokunulmaz. İkinci çağrıdan sonra on ve arka aynı düğümü (20) gösterir.

Üçüncü çağrı uç durumdur. sonuc = 20 alınır ve on = on.sonraki ile on null olur. Ama arka hâlâ silinen 20 düğümünü gösterir. on == null koşulu doğrudur ve arka = null çalışır. Bu satır olmasaydı kuyruk boşken arka silinmiş düğümü göstermeye devam ederdi. Böyle bir tutarsız durumda rear() gibi bir sorgu kuyrukta olmayan bir değeri döndürür ve düğüm bellekten atılamaz.

Üç çağrının çıkış sırası 10, 15, 20'dir; giriş sırasıyla aynıdır. Her çağrı sabit sayıda adım atar: O(1).

8.3.5Dairesel dizi mi, bağlı liste mi?

İki gerçeklemenin de temel işlemleri O(1)'dir. Seçimi belirleyen, bellek kullanımı ve pratik hızdır.

Dairesel dizinin öğeleri bellekte ardışıktır. İşlemci belleği bloklar hâlinde okuduğu için ardışık veriye erişim, bellekte dağınık duran düğümlere erişimden hızlıdır; bu özelliğe önbellek dostu olmak denir. Öğe başına ek referans da yoktur. Buna karşın kapasite sabittir. Kapasite dolunca ya taşma hatası verilir ya da daha büyük bir diziye kopyalama yapılır; bu kopyalama tek başına O(n), amortize O(1)'dir. Dizi ayrıca kapasite kadar yer kaplar; kuyrukta az öğe varken yuvaların çoğu boş durur.

Bağlı listenin kapasite sınırı yoktur ve gerektiği kadar büyür. Her ekleme ve çıkarma, amortize değil, kesin O(1)'dir; hiçbir zaman toplu kopyalama yapılmaz. Bellek öğe sayısıyla orantılıdır. Buna karşın her düğüm ek bir referans taşır ve her eklemede yeni bir nesne oluşturulur. Nesne oluşturma ve sonradan çöp toplama, dizideki bir yuvaya yazmaktan pahalıdır.

Pratikte çoğu durumda dairesel dizi tercih edilir; Java'nın ArrayDeque sınıfının bu yolu seçmesi de bu yüzdendir. Bağlı liste, her işlemin kesin olarak kısa sürmesi gereken ya da kuyruk boyunun çok geniş bir aralıkta dalgalandığı durumlarda öne çıkar.

8.4Kuyruk türleri ve çift uçlu kuyruk

Temel kuyruk, ekleme ve çıkarmayı iki sabit uca bağlar. Bu kuralın gevşetildiği ya da değiştirildiği birkaç kuyruk türü vardır. Bu kesim türleri tanıtır ve en genel olanı, iki uçtan da ekleme ve çıkarma yapılabilen çift uçlu kuyruğu ayrıntılı işler.

8.4.1Kuyruk türleri

Tablodaki türler iki gruba ayrılır. Dairesel kuyruk yeni bir davranış tanımlamaz; basit kuyruğun bir gerçekleme biçimidir. Kullanıcı açısından basit kuyruktan farkı yoktur. Öteki türler ise ADT'yi değiştirir.

Çift uçlu kuyruk iki uçta da hem ekleme hem çıkarma yapar ve en genel türdür. Giriş sınırlı ve çıkış sınırlı kuyruklar onun kısıtlanmış biçimleridir. Giriş sınırlı kuyrukta ekleme yalnız arkadan yapılır, ama çıkarma iki uçtan da yapılabilir. Böyle bir yapı hem kuyruk (önden çıkararak) hem yığın (arkadan çıkararak) gibi kullanılabilir. Çıkış sınırlı kuyrukta ise öğe iki uçtan da girebilir, ama yalnız önden çıkar. Örneğin acil bir iş sıranın önüne, sıradan bir iş sona eklenebilir.

Öncelikli kuyruk (priority queue) ise geliş sırasını hiç dikkate almaz. Her öğenin bir önceliği vardır ve çıkarma her zaman en yüksek öncelikli öğeyi verir. Hastanenin acil servisinde hastalar geliş sırasıyla değil, durumlarının ciddiyetine göre muayene edilir. Bu yapı genellikle heap ile gerçeklenir ve ayrı bir konu olarak incelenir. Burada akılda tutulması gereken, adında “kuyruk” geçse de FIFO olmadığıdır.

8.4.2Çift uçlu kuyruk (deque)

Çift uçlu kuyruk FIFO kuralına bağlı değildir. Hangi davranışı göstereceği, onu kullanan kodun hangi uçları seçtiğine bağlıdır. Yalnız arka uçtan ekleyip yine arka uçtan çıkaran bir çift uçlu kuyruk yığın (LIFO) gibi davranır. Arkadan ekleyip önden çıkaran bir çift uçlu kuyruk ise kuyruk (FIFO) olur. Bu yüzden çift uçlu kuyruk, yığın ve kuyruğun ikisini de içine alan genel bir yapıdır. Java'nın ArrayDeque sınıfının hem yığın hem kuyruk olarak önerilmesinin nedeni budur.

Şekil 8.16'daki öğe sırası da bu esnekliği yansıtır. 20 ilk eklenen öğe olsun. Ardından 21 ve 22 öne, 23 ve 24 arkaya, 26 ve 27 yine öne, 25 arkaya eklenmiş olabilir. Sonuçta kuyrukta öğeler ne geliş sırasındadır ne de ters sırada; her öğenin yeri hangi uca eklendiğine bağlıdır.

Tablo 8.15 bu notta kullanılan işlem adlarını ve Java'daki ArrayDeque karşılıklarını verir.

ArrayDeque bunlara ek olarak yığın işlemlerini de sunar: push(e) başa ekler (addFirst), pop() baştan çıkarır (removeFirst). Kuyruk işlemleri offer ve poll ise sırasıyla offerLast ve pollFirst'tür. Aynı nesne üzerinde iki takımı karıştırmak kafa karıştırabilir. push ile eklenen öğe öne girer; offer ile eklenen öğe ise arkaya girer.

Çift uçlu kuyruk iki yoldan gerçeklenebilir. Dairesel dizi yolunda başa ekleme, bas = (bas − 1 + N) % N ile önü bir yuva geri alır ve yeni öğeyi oraya yazar. Sondan çıkarma ise boyut'u bir azaltmakla yetinir. ArrayDeque bu yolu kullanır. Bu notta ise ikinci yol, çift yönlü bağlı liste işlenir.

boolean palindromMu(String s) {
    Deque<Character> d = new ArrayDeque<>();
    for (char c : s.toCharArray())
        d.offerLast(c);
    while (d.size() > 1)
        if (!d.pollFirst().equals(d.pollLast()))
            return false;
    return true;
}

8.4.3Çift uçlu kuyruk işlemleri adım adım

Çift uçlu kuyruğu çift yönlü bağlı liste (doubly linked list) ile gerçekleyeceğiz. Her düğümde iki referans vardır: onceki bir önceki düğümü, sonraki bir sonraki düğümü gösterir. Kuyruğun kendisi bas (ilk düğüm), son (son düğüm) ve boyut alanlarını tutar.

Boş bir çift uçlu kuyruğa sırayla sonaEkle(5), sonaEkle(8), basaEkle(3), sonaEkle(9), sondanCikar() ve bastanCikar() uygulayalım.

İlk ekleme özel bir durumdur: liste boş olduğu için yeni düğüm hem baş hem son olur. Sonraki eklemelerde yeni düğüm, eklendiği uçtaki düğüme iki yönde bağlanır. Sona eklemede yeni düğümün onceki'si eski son düğümü, eski son düğümün sonraki'si yeni düğümü gösterir. Başa ekleme bunun aynadaki görüntüsüdür.

Her iki uç da referansla tutulduğu için bütün eklemeler O(1)'dir. Çıkarmalarda ise onceki referansının değeri ortaya çıkar. sondanCikar(), yeni son düğümü son.onceki ile tek adımda bulur. Tek yönlü listede sondan çıkarma O(n) olurdu, çünkü sondan bir önceki düğüm baştan gezilerek bulunmak zorundaydı. onceki referansı bu işlemi O(1) yapar. Bunun bedeli düğüm başına bir referans daha saklamaktır.

8.4.4Kod: başa ve sona ekleme

Çift yönlü listenin düğüm sınıfı şudur:

class Dugum<E> {
    E veri;
    Dugum<E> onceki, sonraki;
    Dugum(E veri) { this.veri = veri; }
}

Ekleme metotları:

public void basaEkle(E veri) {
    Dugum<E> d = new Dugum<>(veri);
    if (bosMu()) {
        bas = son = d;
    } else {
        d.sonraki = bas;
        bas.onceki = d;
        bas = d;
    }
    boyut++;
}

public void sonaEkle(E veri) {
    Dugum<E> d = new Dugum<>(veri);
    if (bosMu()) {
        bas = son = d;
    } else {
        d.onceki = son;
        son.sonraki = d;
        son = d;
    }
    boyut++;
}

İki metot aynı kalıbı izler. Önce yeni düğüm oluşturulur; onceki ve sonraki alanları null'dır. Çift uçlu kuyruk boşsa yeni düğüm hem baş hem son olur: bas = son = d; atama zinciri sağdan sola çalışır, önce son'a sonra bas'a d atanır. Boş değilse üç atama yapılır.

basaEkle'de önce yeni düğüm eski başı gösterir (d.sonraki = bas). Sonra eski baş geri bağlantıyla yeni düğümü gösterir (bas.onceki = d). En son baş referansı yeni düğüme geçer (bas = d). Bu sıra önemlidir: bas = d önce yapılsaydı eski başa ulaşılamaz ve bağlar kurulamazdı.

İki metot birbirinin aynadaki görüntüsüdür. basaEkle'de bas yerine son, onceki yerine sonraki (ve tersi) yazılırsa sonaEkle elde edilir. Hiçbir metotta döngü yoktur; ikisi de O(1)'dir.

8.4.5Kod izleme: basaEkle()

Boş bir çift uçlu kuyruğa önce basaEkle(5), sonra basaEkle(3) uygulayalım. 3 başa geçecektir.

İzlemenin sonunda liste 3 ⇄ 5'tir. Baştan sona gezilirse 3, 5; sondan başa gezilirse 5, 3 okunur. İki yönde de gezilebilmesi, d.sonraki = bas ve bas.onceki = d atamalarının ikisinin de yapılmasına bağlıdır. Hiç gezinme yoktur; işlem O(1)'dir.

8.4.6Kod: baştan ve sondan çıkarma

public E bastanCikar() {
    if (bosMu()) return null;
    E veri = bas.veri;
    bas = bas.sonraki;
    if (bas == null)
        son = null;       // boşaldı
    else
        bas.onceki = null;
    boyut--;
    return veri;
}

public E sondanCikar() {
    if (bosMu()) return null;
    E veri = son.veri;
    son = son.onceki;
    if (son == null)
        bas = null;       // boşaldı
    else
        son.sonraki = null;
    boyut--;
    return veri;
}

İki metot da önce boşluğu sorar. Boş çift uçlu kuyrukta, Goodrich'in arayüzündeki gibi null döndürülür. Değilse uçtaki değer veri'ye alınır ve uç referansı içeri doğru bir düğüm ilerler: bastanCikar'da bas = bas.sonraki, sondanCikar'da son = son.onceki.

Ardından iki durum ayrılır. Uç referansı null olduysa çıkarılan düğüm tek düğümdü ve liste boşalmıştır. Bu durumda öbür uç da null yapılır. Liste boşalmadıysa yeni uç düğümün dışarıyı gösteren bağı koparılır: bas.onceki = null ya da son.sonraki = null. Böylece çıkarılan düğüme listeden hiçbir bağ kalmaz. Son olarak boyut azalır ve değer döndürülür.

8.4.7Kod izleme: sondanCikar()

Çift uçlu kuyruk 3 ⇄ 5 olsun. İki kez sondanCikar() çağrılacaktır: önce 5, sonra 3 çıkacak ve kuyruk boşalacaktır.

İlk çağrıda son = son.onceki satırı, sondan bir önceki düğümü aramadan bulur. son null olmadığı için else dalı çalışır ve son.sonraki = null ile 5 düğümüne giden bağ koparılır. 5 düğümü listeden ayrılmıştır.

İkinci çağrıda tek düğüm vardır ve son.onceki null'dır. son null olur, ama bas hâlâ 3 düğümünü gösterir. son == null koşulu doğru olduğu için bas = null çalışır. Bu satır olmasaydı bas silinmiş düğümü göstermeye devam ederdi. Her iki çağrı da sabit sayıda adım atar: O(1).

8.4.8Kayan pencerede en büyük

Çift uçlu kuyruğun iki ucunu birlikte kullanan klasik bir problem şudur: bir a dizisi ve bir k pencere genişliği verilsin. Dizi üzerinde soldan sağa k uzunluğunda bir pencere kaydırılır. Her pencere konumundaki en büyük değer istenir. Bu tür probleme kayan pencere (sliding window) problemi denir. Örneğin a = {1, 3, −1, −3, 5, 3, 6} ve k = 3 için beş pencere vardır: {1, 3, −1}, {3, −1, −3}, {−1, −3, 5}, {−3, 5, 3}, {5, 3, 6}. En büyükler sırasıyla 3, 3, 5, 5, 6'dır.

Kaba kuvvet çözüm her pencerede k öğeyi tarar. n − k + 1 pencere olduğu için maliyet O(n·k)'dir. k büyüdükçe bu yavaşlar; k = n/2 için O(n²)'ye çıkar. Daha iyi bir çözüm, pencere kayarken önceki hesaplardan yararlanır. Fikir şudur: bir öğenin sağında ondan büyük ya da ona eşit bir öğe varsa, o öğe bundan sonraki hiçbir pencerede en büyük olamaz. Çünkü pencere sağa kaydıkça soldaki öğe pencereden daha önce çıkar, sağdaki büyük öğe ise pencerede kalmaya devam eder. Böyle öğeler aday listesinden hemen atılabilir.

Algoritma, adayların indislerini bir çift uçlu kuyrukta tutar. Kuyruktaki indislere karşılık gelen değerler önden arkaya azalan sıradadır; bu yüzden en büyük değer hep öndedir. Her yeni i indisi için üç iş yapılır:

1. Önden atma: Öndeki indis pencerenin dışına düştüyse (≤ i − k) çıkarılır.
2. Arkadan atma: Arkadaki indislerin değeri a[i]'den küçük ya da ona eşitse bunlar artık aday değildir; arkadan çıkarılır.
3. Ekleme: i arkaya eklenir. İlk tam pencereye ulaşıldıysa (i ≥ k − 1) öndeki indisin değeri o pencerenin en büyüğüdür.

int[] pencereMax(int[] a, int k) {
  int[] enb = new int[a.length - k + 1];
  Deque<Integer> d = new ArrayDeque<>(); // indis
  for (int i = 0; i < a.length; i++) {
    if (!d.isEmpty() && d.peekFirst() <= i - k)
      d.pollFirst();        // pencere dışı
    while (!d.isEmpty() && a[d.peekLast()] <= a[i])
      d.pollLast();         // aday değil
    d.offerLast(i);
    if (i >= k - 1) enb[i - k + 1] = a[d.peekFirst()];
  }
  return enb;
}

Kodda d indis tutar; değerlere a[d.peekFirst()] ve a[d.peekLast()] ile ulaşılır. İndis tutulur, çünkü bir öğenin pencereden çıkıp çıkmadığı konumundan anlaşılır. Yalnız değer tutulsaydı, aynı değerden birden çok olduğunda hangisinin çıktığı bilinemezdi. enb dizisi n − k + 1 sonucu tutar ve i. indisle biten pencerenin sonucu enb[i − k + 1]'e yazılır.

İzlemenin kritik adımı i = 4'tür. Pencere artık 2–4. indisleri kapsar ve öndeki 1. indis 1 ≤ 4 − 3 = 1 olduğu için pencerenin dışındadır; önden atılır. Ardından gelen 5, arkadaki −3 ve −1'den büyüktür. İkisi de bundan sonra hiçbir pencerede en büyük olamaz ve arkadan atılır. Kuyrukta yalnız 4:5 kalır. i = 3'te ise −3 arkaya eklenmiş ama hiçbir şey atılmamıştı: −3 küçüktür, ama ileride 3 ve −1 pencereden çıktığında en büyük olma şansı vardı.

Bu ispattaki sayma tekniği, yani “her öğe bir kez girer, en çok bir kez çıkar” gözlemi, kuyruk ve yığın algoritmalarında çok sık kullanılır. İki yığınla kuyruk gerçeklemesinin amortize analizi de aynı fikre dayanır.

8.5Kuyruk uygulamaları

Bu kesimdeki dört problemde kuyruk, işleri adil bir sırayla döndürmek ya da bir yapıyı seviye seviye gezmek için kullanılır. Son problem ise kuyruğun yığınla nasıl kurulabileceğini gösterir.

8.5.1Round robin çizelgeleyici

Bir işletim sisteminde aynı anda çalışmak isteyen birçok süreç vardır, ama tek bir işlemci çekirdeği bir anda yalnız bir süreç çalıştırabilir. İşlemciyi süreçler arasında paylaştıran bileşene çizelgeleyici (scheduler) denir. En sade ve en adil yöntemlerden biri round robin (sırayla dönen çizelgeleme) yöntemidir.

Yöntemde çalışmaya hazır süreçler bir FIFO hazır kuyruğunda bekler. Kuyruğun önündeki süreç alınır ve en fazla q birim süre çalıştırılır. Bu süreye zaman dilimi (time slice, quantum) denir. Süreç bu sürede biterse sistemden ayrılır. Bitmezse kalan süresiyle birlikte kuyruğun arkasına döner ve sırası yeniden gelene kadar bekler. Hiçbir süreç işlemciyi uzun süre tekeline alamaz; her süreç en geç bir tur sonra yeniden çalışır.

Round robin'in başarımı zaman diliminin seçimine bağlıdır. q çok büyük seçilirse her süreç bir dilimde biter ve yöntem “ilk gelen ilk hizmet alır” düzenine döner; kısa süreçler uzun süreçlerin arkasında bekler. q çok küçük seçilirse süreçler arasında çok sık geçiş yapılır. Her geçişin (bağlam değiştirme) kendi maliyeti olduğu için işlemci zamanının önemli bir kısmı asıl işe değil, geçişlere harcanır. Pratikte q, süreçlerin çoğunun bir dilimde etkileşimli bir işi bitirebileceği kadar uzun seçilir.

Örnekteki süreçlerin bekleme sürelerini de hesaplayalım. Bekleme süresi, tamamlanma zamanından çalışma süresinin çıkarılmasıyla bulunur: P1 için 10 − 5 = 5, P2 için 9 − 3 = 6, P3 için 6 − 2 = 4. Ortalama bekleme 15/3 = 5 birimdir. Aynı süreçler sırayla, kesintisiz çalıştırılsaydı (P1, sonra P2, sonra P3) tamamlanma zamanları 5, 8 ve 10, bekleme süreleri 0, 5 ve 8 olurdu; ortalama 13/3 ≈ 4,33. Round robin ortalama beklemeyi her zaman azaltmaz. Kazandırdığı şey, hiçbir sürecin ilk kez çalışmak için uzun süre beklememesidir: üç süreç de ilk 6 birim içinde işlemciye ulaşmıştır.

8.5.2Kod izleme: roundRobin()

Round robin çizelgeleyicinin kodu kısadır. Süreçler aşağıdaki küçük sınıfla temsil edilir:

class Surec {
    String ad;   // süreç adı (P1, P2, …)
    int kalan;   // kalan çalışma süresi
    Surec(String ad, int kalan) { this.ad = ad; this.kalan = kalan; }
}

void roundRobin(Queue<Surec> q, int dilim) {
  int t = 0;
  while (!q.isEmpty()) {
    Surec p = q.poll();
    int calis = Math.min(dilim, p.kalan);
    t += calis;
    p.kalan -= calis;
    if (p.kalan > 0) q.offer(p);
    else System.out.println(p.ad + " t=" + t);
  }
}

t o ana kadar geçen süredir. Döngü kuyruk boşalana kadar döner. Her turda öndeki süreç poll() ile alınır. Çalışma süresi calis = Math.min(dilim, p.kalan)'dır: süreç dilimden önce bitecekse yalnız kalan süresi kadar çalışır. t bu kadar ilerler ve sürecin kalan süresi bu kadar azalır. Kalan süre sıfırdan büyükse süreç offer(p) ile kuyruğun arkasına döner; değilse tamamlanma zamanı yazdırılır.

Kod, örnekteki elle yapılan hesabın aynısını yürütür. 5. ve 6. turlarda calis 1'dir: süreçlerin kalan süresi dilimden kısadır ve dilimin tamamı kullanılmaz. Kuyruk boşalınca döngü biter. Çıktı sırası “P3 t=6”, “P2 t=9”, “P1 t=10”dur.

Her tur bir poll ve en çok bir offer yapar; bir turun maliyeti O(1)'dir. Toplam tur sayısı, her sürecin kaç dilime bölündüğüne bağlıdır: süresi s olan süreç ⌈s/q⌉ tur alır. Örnekte bu ⌈5/2⌉ + ⌈3/2⌉ + ⌈2/2⌉ = 3 + 2 + 1 = 6 turdur.

8.5.3Josephus problemi

Josephus problemi eski bir bilmeceye dayanır. n kişi bir halka oluşturur. Belirli bir kişiden başlanarak sayılır ve her k. kişi halkadan çıkarılır. Sayma, çıkarılanın yanındaki kişiden devam eder. Halkada tek kişi kalana kadar sürer. Soru, kimin kalacağıdır.

Kuyruk, halkayı döndürmenin en doğal yoludur. Kişiler sırayla kuyruğa konur. Öndeki kişiyi alıp arkaya eklemek, sayıyı bir ilerletmek demektir. Her turda öndeki k − 1 kişi arkaya geçirilir; ardından öndeki, yani k. kişi çıkarılır ve elenir.

String josephus(Queue<String> q, int k) {
  while (q.size() > 1) {
    for (int i = 1; i < k; i++)
      q.offer(q.poll());      // öndekini arkaya
    String elenen = q.poll();
    System.out.println(elenen + " elendi");
  }
  return q.poll();
}

for döngüsü i = 1'den k − 1'e kadar döner ve her adımda q.offer(q.poll()) çalıştırır: öndeki kişi alınır ve hemen arkaya eklenir. Döngü bitince öndeki kişi poll() ile çıkarılır, adı yazdırılır ve bir daha kuyruğa girmez. Dış while kuyrukta birden çok kişi olduğu sürece döner. En sonda kalan kişi döndürülür.

n = 5 kişi (A, B, C, D, E) ve k = 3 için izleyelim.

Eleme sırası C, A, E, B'dir ve kazanan D'dir. Dördüncü tur dikkat çekicidir: kuyrukta iki kişi vardır ve her ikisi de arkaya geçer. B ve D bir tam tur atar, sayma yeniden B'ye gelir ve B elenir. Halka küçüldükçe sayma halkayı birden çok kez dolaşabilir; kuyruk bunu hiçbir özel durum yazmadan doğru yapar.

Maliyet hesabı kolaydır. n kişiden n − 1'i elenir; her eleme turu k − 1 taşıma ve bir çıkarma, yani k kuyruk işlemi yapar. Toplam (n − 1) · k işlem, yani O(n·k)'dir. Örnekte 4 · 3 = 12 kuyruk işlemi yapılmıştır.

Yalnız kazananı bulmak isteniyorsa kuyruk kullanmadan da bir yineleme bağıntısı vardır. Kişiler 0'dan numaralanırsa J(1) = 0 ve J(n) = (J(n − 1) + k) % n'dir. k = 3 için J(2) = 1, J(3) = 1, J(4) = 0, J(5) = 3 bulunur. 3 numaralı kişi dördüncü kişi, yani D'dir. Bu yöntem O(n)'de çalışır, ama eleme sırasını vermez. Kuyruk çözümü ise süreci adım adım canlandırır.

8.5.41'den n'e kadar ikilik sayılar

Problem şudur: 1'den n'e kadar sayıların ikilik (binary) gösterimlerini artan sırada üretmek. Örneğin n = 3 için sonuç {"1", "10", "11"}, n = 5 için {"1", "10", "11", "100", "101"}'dir.

Her sayıyı ayrı ayrı ikiliğe çevirmek mümkündür. Kuyruk ise daha zarif bir yol sunar. Bir x sayısının ikilik gösteriminin sonuna “0” eklemek sayıyı 2x'e, “1” eklemek 2x + 1'e çevirir. Örneğin “10” (2) dizesinden “100” (4) ve “101” (5) elde edilir. Bu ilişki sayıları bir ağaç gibi düzenler: kök “1”'dir ve her düğümün iki çocuğu, sonuna “0” ve “1” eklenmiş hâlleridir.

Ağacı seviye seviye gezmenin yolu kuyruktur. Kuyruktan bir dize alınır ve sonuca yazılır; ardından onun iki çocuğu kuyruğun arkasına eklenir. Önce eklenen önce çıktığı için bir seviyedeki bütün dizeler, bir alt seviyedekilerden önce işlenir. Aynı seviyede de soldan sağa sıra korunur. Bu gezinme biçimine genişlik öncelikli gezinme denir. Aynı seviyedeki ikilik sayılar aynı uzunluktadır ve soldan sağa artar; daha alt seviyedekiler daha uzundur, dolayısıyla daha büyüktür. Sonuç olarak sayılar tam olarak artan sırada üretilir.

String[] ikilikSayiUret(int n) {
    String[] sonuc = new String[n];
    Queue<String> q = new LinkedList<>();
    q.offer("1");
    for (int i = 0; i < n; i++) {
        sonuc[i] = q.poll();
        q.offer(sonuc[i] + "0");
        q.offer(sonuc[i] + "1");
    }
    return sonuc;
}

8.5.5Kod izleme: ikilikSayiUret(4)

Metot n yuvalı bir sonuç dizisi ve boş bir kuyruk oluşturur. Kuyruk LinkedList ile gerçeklenir, ama değişkenin türü Queue olduğu için yalnız kuyruk işlemleri kullanılır. Kök “1” kuyruğa eklenir. Döngü n kez döner. Her turda öndeki dize çıkarılıp sonuca yazılır ve iki çocuğu arkaya eklenir.

Her turda kuyruğun önündeki dize, kuyrukta bekleyenlerin en küçüğüdür. i = 4'te 4 < 4 yanlıştır ve döngü biter. Metot {"1", "10", "11", "100"} döndürür. Kuyrukta kalan beş dize hiç kullanılmaz. Bu küçük bir israftır: son turlarda eklenen çocuklar gerekmez. İstenirse yalnız gerekli sayıda dize üretmek için ekleme bir sayaçla sınırlanabilir.

Maliyet iki düzeyde verilir. Kuyruk işlemi olarak sayılırsa n poll ve 2n offer yapılır: O(n) işlem. Ancak her işlem bir dize oluşturur ve n'ye kadarki bir sayının ikilik gösterimi yaklaşık log₂ n karakterdir. Dize birleştirme karakter sayısıyla orantılı sürdüğü için karakter düzeyinde toplam iş O(n log n)'dir. Kuyrukta en çok yaklaşık n + 1 dize bulunur.

8.5.6İki yığınla kuyruk

Son problem bir tasarım sorusudur: elimizde yalnız yığın varsa kuyruk kurulabilir mi? Tek yığın yetmez, çünkü yığın sırayı ters çevirir. Ama sırayı iki kez ters çevirmek onu eski hâline getirir. Bu gözlem iki yığınlı çözümün temelidir.

Bir yığın (gelen) eklemeler için, öteki (giden) çıkarmalar için kullanılır. enqueue öğeyi doğrudan gelen'e push eder. dequeue önce giden'e bakar. giden boşsa gelen'deki bütün öğeler tek tek pop edilip giden'e push edilir. Bu aktarım sırayı ters çevirir ve en eski öğe giden'in üstüne çıkar. Ardından giden'den pop yapılır.

Deque<Integer> gelen = new ArrayDeque<>();
Deque<Integer> giden = new ArrayDeque<>();
void enqueue(int x) {
  gelen.push(x);
}
int dequeue() {
  if (giden.isEmpty())
    while (!gelen.isEmpty())
      giden.push(gelen.pop());
  return giden.pop();
}

Kodda yığın olarak ArrayDeque kullanılmıştır; push ve pop baş uçta çalışır. Boş kuyrukta dequeue çağrılırsa iki yığın da boştur, aktarım hiçbir şey taşımaz ve giden.pop() NoSuchElementException fırlatır. Yani alt taşma istisnayla bildirilir.

Kuyruğa sırayla enqueue(1), enqueue(2), enqueue(3), dequeue(), enqueue(4) ve üç kez dequeue() uygulayalım. Yığınlar alttan üste yazılmıştır.

İlk dequeue'da giden boştur. gelen'in üstündeki 3 önce taşınır ve giden'in dibine yerleşir; ardından 2, en son 1 taşınır. 1, giden'in üstündedir ve pop edilir. FIFO kuralı korunmuştur: ilk eklenen ilk çıkmıştır.

enqueue(4), giden'de bekleyen 2 ve 3'e dokunmaz; 4 gelen'e girer. Sonraki iki dequeue'da giden boş değildir ve aktarım yapılmaz; 2 ve 3 sırayla çıkar. 4'ün gelen'de beklemesi doğrudur, çünkü 2 ve 3'ten sonra eklenmiştir. Son dequeue'da giden boşalmıştır ve 4 aktarılıp çıkarılır. Çıkış sırası 1, 2, 3, 4'tür; giriş sırasıyla aynıdır. Toplam 4 öğe aktarılmıştır.

Tek bir dequeue çağrısı pahalı olabilir: giden boşken gelen'de n öğe varsa aktarım n pop ve n push yapar. En kötü durumda tek çağrı O(n)'dir. Ama böyle pahalı çağrılar sık olamaz.

Tablo 8.23'teki 8 işlemlik dizi bu sınırı somut olarak gösterir. 4 push (gelen'e), 4 aktarım (her biri bir pop ve bir push) ve 4 pop (giden'den) yapılmıştır: toplam 4 + 8 + 4 = 16 yığın işlemi. Bu, 4 · 4 = 16 sınırına eşittir, çünkü her öğe tam bir kez aktarılmıştır.

Tersi soru da sorulabilir: yalnız kuyruk kullanarak yığın kurulabilir mi? Tek bir kuyrukla mümkündür. push(x) önce x'i kuyruğa ekler, sonra ondan önceki bütün öğeleri birer birer önden alıp arkaya ekler. Böylece x öne gelir ve pop doğrudan önden çıkarabilir. Bu tasarımda pop O(1), push ise O(n)'dir; maliyet bu kez amortize olarak da düşmez, çünkü her push bütün kuyruğu döndürür.

8.6Sık yapılan hatalar

Kuyruk kodundaki hataların çoğu birkaç tipe ayrılır. Not boyunca konuların yanında verilen hatalar burada bir arada toplanmıştır. Bir kuyruk kodunu gözden geçirirken kontrol listesi olarak kullanılabilir.

Son satırdaki kısıt bir tasarım kararıdır. poll() boş kuyrukta null döndürür. Kuyrukta null öğeler de bulunabilseydi, null dönüşünün “kuyruk boş” mu yoksa “öndeki öğe null” mı anlamına geldiği ayırt edilemezdi. ArrayDeque bu belirsizliği null eklemeyi yasaklayarak önler. LinkedList ise null kabul eder; bu yüzden onunla çalışırken poll sonucunu yorumlamak daha dikkat ister.

Bölümdeki problemlere geri dönüp bakıldığında ortak bir desen görülür. Kuyruk şu soru sorulduğunda doğru araçtır: “Bekleyenler arasında en uzun süredir bekleyen hangisi?” Round robin'de bu, işlemciyi en uzun süredir beklemeyen süreçtir. Josephus probleminde sayma sırası gelen kişidir. İkilik sayı üretiminde, henüz çocukları üretilmemiş en küçük sayıdır. Yığının sorusu ise bunun tersidir: “en son görülen ve henüz sonuçlanmamış öğe hangisi?” Bir problemde öğelerin geliş sırasıyla işlenmesi gerekiyorsa çözüm büyük olasılıkla bir kuyruk kullanır. İki uçla da çalışmak gerekiyorsa (kayan pencerede olduğu gibi) çift uçlu kuyruk gerekir.

8.7Özet

• Kuyruk, eklemenin arkadan, çıkarmanın önden yapıldığı bir ADT'dir ve FIFO (ilk giren ilk çıkar) düzeniyle çalışır. Temel işlemleri enqueue, dequeue, first/peek, size ve isEmpty'dir; iyi bir gerçeklemede hepsi O(1)'dir.
• Boş kuyruktan çıkarma alt taşma, sabit kapasiteli dolu kuyruğa ekleme taşmadır. Java'daki Queue arayüzünde add/remove/element istisna fırlatır, offer/poll/peek false ya da null döndürür. ArrayDeque dairesel diziyle, LinkedList bağlı listeyle gerçeklenir.
• Basit dizi kuyruğunda öndeki boşalan yuvalar yeniden kullanılamaz; kuyruk içi boşken bile “dolu” olur. Kaydırma bu sorunu çözer ama çıkarmayı O(n) yapar.
• Dairesel kuyruk indisleri (i + 1) % N ile ilerletir ve yuvaları yeniden kullanır. Sayaç yönteminde ekleme yeri (bas + boyut) % N, boş koşulu boyut == 0, dolu koşulu boyut == N'dir. “Bir yuva boş” yönteminde en fazla N − 1 öğe saklanır ve dolu koşulu (arka + 1) % N == bas'tır.
• Dolu dairesel kuyruk, öğeler (bas + k) % N sırasıyla yeni diziye kopyalanarak iki katına büyütülür. Tek büyütme O(n)'dir, ama n eklemenin toplamı 3n'den az olduğu için ekleme amortize O(1)'dir. Arrays.copyOf başa sarmış kuyruğun sırasını bozar.
• Bağlı liste kuyruğu on ve arka referanslarıyla çalışır: ekleme sona, çıkarma baştandır ve ikisi de kesin O(1)'dir. Boş kuyruğa ilk eklemede on, son öğe çıkınca arka ayrıca güncellenmelidir.
• Çift uçlu kuyruk (deque) iki uçtan da ekleme ve çıkarma yapar; yalnız bir uç kullanılırsa yığın, bir uçtan ekleyip öbüründen çıkarılırsa kuyruk olur. Çift yönlü bağlı listede onceki referansı sondan çıkarmayı O(1) yapar; son öğe çıkınca iki uç da null olmalıdır.
• Kayan pencerede en büyük problemi, değerleri önden arkaya azalan bir indis kuyruğuyla O(n)'de çözülür; her indis bir kez girer ve en çok bir kez çıkar.
• Round robin çizelgeleme, her süreci en fazla q birim çalıştırıp bitmeyeni kuyruğun arkasına döndürür. Josephus problemi, k − 1 kişiyi arkaya geçirip k.'yi eleyerek O(n·k)'de çözülür. İkilik sayılar, “x0” ve “x1” çocuklarını kuyruğa ekleyerek artan sırada üretilir.
• İki yığınla kuyruk, eklemeleri bir yığına yapar ve öbür yığın boşaldığında öğeleri aktarır. Her öğe en çok bir kez aktarıldığı için işlemler amortize O(1)'dir; tek bir dequeue en kötü durumda O(n)'dir.

8.8Kavram 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
• ön front
• arka rear
• enqueue (arkaya ekleme) enqueue
• dequeue (önden çıkarma) dequeue
• soyut veri tipi abstract data type (ADT)
• arayüz interface
• jenerik generic
• taşma overflow
• alt taşma underflow
• dizi array
• kapasite capacity
• dairesel kuyruk circular queue
• amortize analiz amortized analysis
• tek yönlü bağlı liste singly linked list
• çift yönlü bağlı liste doubly linked list
• düğüm node
• çift uçlu kuyruk deque (double-ended queue)
• öncelikli kuyruk priority queue
• kayan pencere sliding window
• çizelgeleyici scheduler
• round robin (sırayla dönen çizelgeleme) round robin
• zaman dilimi time slice (quantum)
• genişlik öncelikli arama breadth-first search (BFS)
• yığın stack
• zaman karmaşıklığı time complexity
• alan karmaşıklığı space complexity

8.9Kendini Dene

1. Boş bir kuyruğa sırayla enqueue(5), enqueue(8), dequeue(), enqueue(2), first(), enqueue(6), dequeue(), dequeue() uygulanıyor. Değer döndüren çağrılar ne döndürür ve sonda kuyrukta ne kalır?

   Cevap

   İlk dequeue() 5'i döndürür; kuyruk: 8. enqueue(2)'den sonra kuyruk 8, 2'dir ve first() 8'i çıkarmadan döndürür. enqueue(6)'dan sonra 8, 2, 6; ardından dequeue() 8'i, sonraki dequeue() 2'yi döndürür. Dönen değerler sırasıyla 5, 8, 8, 2'dir; sonda kuyrukta yalnız 6 kalır.

2. Sayaç yöntemli bir dairesel kuyrukta N = 8, bas = 5, boyut = 6'dır. Öğeler hangi indislerdedir? Son öğe hangi indistedir ve bir sonraki ekleme nereye yazılır?

   Cevap

   Öğeler önden arkaya (5 + k) % 8 indislerindedir (k = 0, …, 5): 5, 6, 7, 0, 1, 2. Son öğe (5 + 6 − 1) % 8 = 2. indistedir. Sonraki ekleme (5 + 6) % 8 = 3. yuvaya yazılır. Kuyruk iki kez daha ekleme kabul eder (3. ve 4. yuvalar), sonra boyut == 8 olur.

3. Kapasitesi 4 olan, sayaç yöntemli boş bir dairesel kuyruğa ekle(1), ekle(2), ekle(3), cikar(), cikar(), ekle(4), ekle(5), ekle(6) uygulanıyor. Sonda dizi, bas ve boyut nedir? Bir ekle(7) daha çağrılırsa ne olur?

   Cevap

   Üç ekleme 0, 1, 2. yuvaları doldurur; iki çıkarma 1 ve 2'yi döndürür ve bas = 2, boyut = 1 olur. 4, (2 + 1) % 4 = 3'e; 5, (2 + 2) % 4 = 0'a; 6, (2 + 3) % 4 = 1'e yazılır. Sonda dizi [5, 6, 3, 4], bas = 2, boyut = 4'tür; kuyruk önden arkaya 3, 4, 5, 6'dır ve doludur. ekle(7) IllegalStateException("dolu") fırlatır.

4. Kapasitesi 3 olan dolu bir dairesel kuyrukta dizi = [R, P, Q] ve bas = 1'dir. Büyüyen ekle(S) çağrısından sonra dizi, bas ve boyut ne olur?

   Cevap

   Mantıksal sıra P, Q, R'dir. boyut == 3 olduğu için buyut(6) çağrılır: yeni[0] = dizi[1] = P, yeni[1] = dizi[2] = Q, yeni[2] = dizi[(1 + 2) % 3] = dizi[0] = R; bas = 0. S, (0 + 3) % 6 = 3'e yazılır. Sonuç: [P, Q, R, S, _, _], bas = 0, boyut = 4.

5. Bağlı liste kuyruğunun dequeue metodundan if (on == null) arka = null; satırı silinmiş olsun. Boş kuyruğa enqueue(7), dequeue(), enqueue(9) uygulanırsa ara durumlar ve son durum ne olur? Hata hangi koşulda görünür hâle gelir?

   Cevap

   enqueue(7)'den sonra on ve arka 7 düğümünü gösterir. dequeue() 7'yi döndürür, on null olur, ama arka hâlâ 7 düğümünü gösterir ve uzunluk = 0'dır. enqueue(9)'da bosMu() doğrudur; on 9'u gösterir ve arka = gecici satırı arka'yı da 9'a taşır. Son durum doğrudur. Hata yalnız kuyruk boşken arka'ya bakıldığında (örneğin bir rear() çağrısında) görünür: kuyrukta olmayan 7 döner ve 7 düğümü bellekten atılamaz.

6. Deque<Integer> d = new ArrayDeque<>(); üzerinde sırayla d.offerLast(1), d.offerFirst(2), d.push(3), d.offer(4), d.pollLast(), d.pop() çağrılıyor. Son iki çağrı ne döndürür ve sonda d ne yazdırır?

   Cevap

   offerLast(1) → [1]; offerFirst(2) → [2, 1]; push(3) başa ekler → [3, 2, 1]; offer(4) sona ekler → [3, 2, 1, 4]. pollLast() 4'ü döndürür → [3, 2, 1]. pop() baştan çıkarır ve 3'ü döndürür → [2, 1]. System.out.println(d) [2, 1] yazdırır.

7. pencereMax({2, 7, 3, 1, 5, 4}, 2) ne döndürür? Çalışma boyunca toplam kaç kez pollLast() çağrılır?

   Cevap

   Sonuç [7, 7, 3, 5, 5]'tir. i = 1'de 7, arkadaki 0:2'yi atar (1. pollLast). i = 2'de 3 eklenir; i = 3'te 1:7 önden atılır (pencere dışı), 1 eklenir. i = 4'te önden 2:3 atılır; 5, arkadaki 3:1'i atar (2. pollLast). i = 5'te 4 eklenir. Toplam 2 pollLast ve 2 pollFirst yapılır; ikisinin toplamı 6 eklemeyi geçmez.

8. Hazır kuyruğunda sırayla P1 (3 birim), P2 (4 birim), P3 (1 birim) var; zaman dilimi q = 2'dir. Süreçler round robin ile hangi anlarda tamamlanır? Ortalama bekleme süresi nedir?

   Cevap

   0–2: P1 (kalan 1), kuyruk P2, P3, P1. 2–4: P2 (kalan 2), kuyruk P3, P1, P2. 4–5: P3 biter. 5–6: P1 biter. 6–8: P2 biter. Tamamlanma: P3 = 5, P1 = 6, P2 = 8. Bekleme süreleri 6 − 3 = 3, 8 − 4 = 4, 5 − 1 = 4; ortalama 11/3 ≈ 3,67 birimdir.

9. 1'den 6'ya numaralı altı kişi için josephus(q, 3) hangi sırayla eleme yapar ve kimi döndürür? Sonuç J(n) = (J(n − 1) + k) % n bağıntısıyla nasıl denetlenir?

   Cevap

   Elenenler sırasıyla 3, 6, 4, 2, 5'tir; kazanan 1'dir. Bağıntıyla (0'dan numaralı): J(1) = 0, J(2) = 1, J(3) = 1, J(4) = 0, J(5) = 3, J(6) = (3 + 3) % 6 = 0. 0 numaralı konum 1. kişidir; iki yöntem aynı sonucu verir. Toplam 5 · 3 = 15 kuyruk işlemi yapılır.

10. İki yığınla kuyruğa sırayla enqueue(a), enqueue(b), dequeue(), enqueue(c), enqueue(d), dequeue(), dequeue(), dequeue() uygulanıyor. Çıkarmalar ne döndürür? Hangi dequeue'larda aktarım yapılır ve toplam kaç öğe aktarılır?

    Cevap

    1. dequeue: giden boştur; b ve a aktarılır (2 öğe), a döner. enqueue(c) ve enqueue(d) gelen'e girer. 2. dequeue: giden'de b vardır, aktarım yok; b döner. 3. dequeue: giden boştur; d ve c aktarılır (2 öğe), c döner. 4. dequeue: d döner. Çıkış sırası a, b, c, d'dir; aktarım 1. ve 3. çağrılarda yapılır, toplam 4 öğe aktarılır.

8.10İleri okuma

• M. T. Goodrich, R. Tamassia ve M. H. Goldwasser, Data Structures and Algorithms in Java (6. baskı, 2014), Kesim 6.2 ve 6.3: kuyruk ADT'sini, dairesel dizi ve bağlı liste gerçeklemelerini ve çift uçlu kuyruğu bu nottakine yakın bir Java arayüzüyle anlatır.
• R. Sedgewick ve K. Wayne, Algorithms (4. baskı, 2011), Kesim 1.3: kuyruğu bağlı liste ve büyüyen diziyle gerçekler; yineleyiciler ve jeneriklerle birlikte kısa, açık kodlar verir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı, 2009), Kesim 10.1: kuyruğun dizi gerçeklemesini biçimsel olarak verir; alıştırmalarında iki yığınla kuyruk ve çift uçlu kuyruk yer alır.
• A. Silberschatz, P. B. Galvin ve G. Gagne, Operating System Concepts (10. baskı, 2018), Bölüm 5: round robin dahil işlemci çizelgeleme algoritmalarını, zaman diliminin seçimini ve bekleme süresi gibi ölçütleri ayrıntılı işler.

8.11Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009.
2. M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Java, 6. baskı, Wiley, 2014.
3. R. Lafore, Data Structures and Algorithms in Java, 2. baskı, Sams, 2002.
4. Oracle, Java SE 17 API Specification: java.util.Queue, java.util.Deque, java.util.ArrayDeque ve java.util.PriorityQueue belgeleri.
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
6. A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10. baskı, Wiley, 2018.

İlgili sayfalar: Bölüm 8 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.