Kuyruk
- İngilizcesi
- Queue
- Okunuşu
- kyu
Günlük kullanımda iki ad da yaygın.
Kısaca
Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
Kuyruk (queue) veri yapısı nedir?
Kuyruk, öğelerin bir uçtan, yani arkadan (back ya da rear) eklendiği ve diğer uçtan, yani önden (front) çıkarıldığı bir koleksiyondur. Öğe eklemeye enqueue, çıkarmaya dequeue denir. Bu kural FIFO olarak bilinir: first in, first out (ilk giren ilk çıkar).
Tıpkı bir kahve dükkanındaki sıra gibi çalışır: yeni müşteriler arkaya katılır ve öndeki kişiye sıradaki olarak hizmet verilir. Bağlı liste, dairesel tampon (uçları başa saran sabit boyutlu bir dizi) ya da çift uçlu kuyruk üzerine iyi kurulmuş bir kuyruk, enqueue ve dequeue işlemlerini O(1) sürede yapar. Yaygın bir hata, düz bir dizi kullanıp baştan JavaScript'in shift() ya da Python'ın list.pop(0) ifadesiyle silmektir; kalan her öğenin bir konum kayması gerektiği için bunlar O(n) sürer.
Kuyruklar, işin geliş sırasıyla ele alınması gereken her yerde kullanılır: yazdırma işleri, klavye ve fare olayları, gönderilmeyi bekleyen ağ paketleri ve bir iş sistemindeki arka plan görevleri. Bir çizgede genişlik öncelikli arama, en yakın düğümleri önce ziyaret etmek için kuyruk kullanır. Daha büyük ölçekte mesaj kuyruğu, aynı fikri programlar arasında uygulayan ve bir tüketici işlemeye hazır olana kadar mesajları tutan ayrı bir servistir.
Kuyruğun tersi, en yeni öğeyi önce çıkaran (LIFO) yığındır. Öncelik kuyruğu da farklıdır: en eski öğeyi değil en yüksek öncelikli öğeyi çıkarır ve genellikle bir heap üzerine kurulur. Deque (çift uçlu kuyruk, deck gibi telaffuz edilir) her iki uçtan da ekleme ve çıkarmaya izin verir; bu yüzden hem kuyruk hem de yığın gibi davranabilir.
Bir bakışta
Önemli noktalar
- Kuyruk FIFO sırasını izler: ilk giren ilk çıkar.
- Enqueue arkaya ekler, dequeue önden çıkarır; iyi uygulandığında her biri O(1) sürer.
- Python'da
list.pop(0)yerinecollections.dequeileappend()vepopleft()kullanın. - Genişlik öncelikli arama, iş zamanlama ve tamponlama kuyruklara dayanır.
- Öncelik kuyruğu en eskiyi değil, en yüksek öncelikli öğeyi önce çıkarır.
Örnek
from collections import deque
queue = deque()
queue.append("first job") # enqueue at the back: O(1)
queue.append("second job")
queue.append("third job")
print(queue.popleft()) # dequeue from the front: O(1), prints "first job"
print(queue.popleft()) # "second job"
print(queue[0]) # peek at the next item without removing it: "third job"
# Avoid list.pop(0) for queues: it shifts every remaining item, which is O(n)Sık sorulan sorular
Kuyruk ile yığın arasındaki fark nedir?
Kuyruk ilk eklenen öğeyi çıkarırken (FIFO) yığın en son eklenen öğeyi çıkarır (LIFO). Adil, sıralı işleme için kuyruk; geri alma, geri izleme (backtracking) ve iç içe yapılar için yığın kullanın.
JavaScript'te array.shift() yavaş mı?
Olabilir. shift() ilk öğeyi çıkarır ve diğer her öğeyi bir indeks aşağı kaydırır; bu O(n)'dir, dolayısıyla büyük bir diziyi bir döngüde bununla boşaltmak O(n^2) olur. Büyük kuyruklarda kaydırmak yerine öne işaret eden bir indeks tutun ya da özel bir kuyruk uygulaması kullanın.
Öncelik kuyruğu nedir?
Öncelik kuyruğu, her öğenin bir önceliği olduğu ve ne zaman geldiğine bakılmaksızın en yüksek öncelikli öğenin önce çıkarıldığı bir kuyruktur. Genellikle bir heap ile uygulanır; bu da hem eklemeyi hem çıkarmayı O(log n) yapar.
Sık karşılaştırılanlar
İlgili sayfalar
- YığınVeri Yapıları, s. 36Yığın, öğeleri son giren ilk çıkar (LIFO) sırasıyla saklayan bir veri yapısıdır; en son eklenen öğe her zaman ilk çıkarılan öğedir.
- Bağlı ListeVeri Yapıları, s. 4Bağlı liste, öğeleri ayrı düğümlerde saklayan bir veri yapısıdır; her düğüm bir değer ile zincirdeki sonraki düğüme bir referans tutar.
- HeapVeri Yapıları, s. 19Heap, en küçük ya da en büyük öğeyi kökünde tutan ağaç tabanlı bir veri yapısıdır; bu öğeyi O(1)'de okuyabilir ve O(log n)'de çıkarabilirsiniz.
- ÇizgeVeri Yapıları, s. 8Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.
- Mesaj KuyruğuBackend ve API'ler, s. 28Mesaj kuyruğu, bir servisten gelen mesajları bir başkası işlemeye hazır olana kadar saklayan ve sistemin parçalarını eşzamansız çalıştıran bir bileşendir.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- DequeVeri Yapıları, s. 10Deque, hem önden hem arkadan sabit sürede öğe eklemeye ve çıkarmaya izin veren çift uçlu bir kuyruktur; hem yığın hem kuyruk gibi davranabilir.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin