Stack ve Queue: İşler Hangi Sırayla Yapılmalı?
LIFO ve FIFO yapılarını çağrı yığını, undo, görev kuyruğu ve breadth-first search örnekleriyle öğrenin.
Bir metin editöründe son yapılan işlemi geri almakla, yazdırma isteklerini geliş sırasıyla işlemek aynı sıralama problemi değildir. İlki son girenin önce çıktığı stack, ikincisi ilk girenin önce çıktığı queue gerektirir.
Stack: LIFO
Stack, Last In First Out düzenidir. push üste eleman ekler, pop en üsttekini çıkarır, peek çıkarmadan gösterir. Bu işlemler uygun uygulamada O(1) sürer.
const history: string[] = [];
history.push('başlık değişti');
history.push('paragraf silindi');
const lastAction = history.pop();lastAction, en son eklenen paragraf silindi değeridir. Undo geçmişi, parantez doğrulama, depth-first search ve fonksiyon çağrı yığını stack mantığını kullanır.
Queue: FIFO
Queue, First In First Out düzenidir. enqueue sona ekler, dequeue baştan çıkarır. Siparişlerin geliş sırası, yazdırma işleri ve breadth-first search bunun örnekleridir.
JavaScript dizisinde shift() baştaki elemanları kaydırabileceği için O(n) olabilir. Yoğun kuyrukta baş indeksi tutmak veya ring buffer (halka tampon) kullanmak daha uygundur. Ring buffer sabit boyutlu dizinin sonuna gelince başına döner; elemanları kaydırmadan kuyruk işlemleri yapar.
Varyasyonlar
Deque (double-ended queue), iki uçtan ekleme ve çıkarma sağlar. Priority queue (öncelik kuyruğu), geliş sırasına değil önceliğe göre eleman seçer ve çoğunlukla en öncelikli öğeyi kökte tutan heap veri yapısıyla uygulanır. Acil işlerin normal işleri geçmesi gerekiyorsa priority queue; adaletli geliş sırası gerekiyorsa FIFO queue kullanılır.
Yaygın hatalar
- Boş yapıdan
popveyadequeuesonucunu kontrol etmemek - Sınırsız kuyruğun belleği tüketebileceğini unutmak
- Priority queue’da eşit öncelikli işlerin sırasını tanımlamamak
- Queue’yu mesaj broker sanmak; broker kalıcılık, yeniden deneme ve dağıtım gibi ek garantiler sunar
Alıştırma
Bir metindeki ()[]{} parantezlerinin dengeli olup olmadığını stack ile kontrol edin. Açılan parantezi push, doğru türde kapanış gördüğünüzde pop edin.