Bölüm 8 · SimülasyonDairesel Kuyruk Simülatörü ? ← Bölüm 8 Değer Enqueue · ekle Dequeue · cikar Peek · ilk İptal Kapasite N4568 Kuyruk doluncathrow "dolu"büyüt: buyut(2 · N) Başa Sarma Örneği Temizle Halka görünümü Dizi görünümü Adım Bir işlem seçin. Kod Kapat Dairesel Kuyruk Simülatörü Diziyi bir halka gibi kullanan dizi tabanlı kuyruk. Kuyruğu yalnızca iki sayı tanımlar: bas (öndeki öğenin indisi) ve boyut (öğe sayısı). Sıradaki boş hücre saklanmaz, hesaplanır: son = (bas + boyut) % dizi.length. Kullanım Enqueue ekle(deger), Dequeue cikar(), Peek ilk() metodunu çalıştırır. Her adımda o anki Java satırı vurgulanır ve indis hesabı gösterilir. Kapasite N o boyutta boş bir kuyruk başlatır. Kuyruk dolunca listesinden "dolu" hatası fırlatmak ya da diziyi buyut(2 · N) ile iki katına çıkarmak seçilir. Başa Sarma Örneği N = 5, bas = 2, boyut = 2 (30, 40) durumunu yükler: ekle(50) dizi[4] hücresine yazar, sonraki iki yazma dizi[0] ve dizi[1] hücrelerine sarar. İptal çalışan işlemi durdurur ve kuyruğu işlemden önceki hâline getirir. Görünümleri okuma Halka görünümü: her dilim bir dizi hücresidir; kırmızı kenar bas konumunu, turuncu dilim okunan ya da yazılan hücreyi gösterir. Dizi görünümü: aynı hücreler indis sırasıyla, ▲bas ve ▲son işaretleriyle gösterilir; büyütme sırasında yeni dizi yeni altta belirir. Notlar Dolu ve boş kuyrukta bas == son olur; ikisini boyut ayırt eder. cikar() boşalan hücreye null yazar, böylece nesne çöp toplayıcı tarafından toplanabilir; hiçbir öğe kaydırılmaz. Büyütme öğeleri kuyruk sırasıyla kopyalar (yeni[k] = dizi[(bas + k) % N]) ve bas = 0 yapar; düz bir Arrays.copyOf sarılmış sırayı korurdu ve kuyruğu bozardı. Karmaşıklık İşlemSüre ekle (büyütmesiz), cikar, ilkO(1) buyut ile ekleBir kez O(n), amortize O(1)