Yan yana
YığınvsKuyruk
Yığın ile kuyruk arasındaki fark nedir?
Güncellendi 2 dk okuma7 fark
Kısaca
Yığın en son ekleneni ilk çıkarır (son giren ilk çıkar, LIFO); kuyruk ise en eskiyi ilk çıkarır (ilk giren ilk çıkar, FIFO), tabak yığını ile kasa sırası gibi.
Yığın
Yığı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.
Yığın sayfasını okuKuyruk
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 sayfasını okuYığın ve Kuyruk karşılaştırması
| Özellik | Yığın | Kuyruk |
|---|---|---|
| Sıra | LIFO: son giren ilk çıkar | FIFO: ilk giren ilk çıkar |
| Ekleme | Tepeye push | Arkaya enqueue |
| Çıkarma | Tepeden pop | Önden dequeue |
| Kullanılan uçlar | Hem ekleme hem çıkarma için tek uç | İki uç: arkadan eklenir, önden çıkarılır |
| Günlük hayattan benzetme | Üst üste konmuş tabaklar | Kasada bekleyen insanların sırası |
| Algoritmalarda | Derinlik öncelikli arama, özyineleme ve geri izleme | Genişlik öncelikli arama, zamanlama ve arabelleğe alma |
| Tipik kullanımlar | Çağrı yığını, geri alma geçmişi, ifade ayrıştırma | İş kuyrukları, mesaj kuyrukları, yazdırma kuyruğu |
Fark, açıklamalı
Yığın, elemanları aynı uçtan, yani tepeden ekleyip çıkardığınız bir koleksiyondur: push bir eleman ekler, pop bir eleman çıkarır. Kuyruk ise elemanları arkadan eklediğiniz ve önden çıkardığınız bir koleksiyondur; işlemlere genellikle enqueue ve dequeue denir.
Fark çıkarma sırasıdır ve her birinin neye uygun olduğunu bu belirler. Yığının LIFO sırası, fonksiyon çağrıları, geri alma geçmişi ve parantez eşleştirme gibi iç içe geçmiş ya da geri alınabilir işleri doğal biçimde izler. Kuyruğun FIFO sırası ise yazdırma işleri, ağ istekleri ve bir çalışanı bekleyen görevler gibi şeyleri adil ve geliş sırasında tutar.
İkisi de soyut veri tipleridir; dizilerle ya da bağlı listelerle kurulabilirler ve iyi gerçeklendiğinde ikisinde de ekleme ve çıkarma O(1)'dir. Algoritmalarda da yan yana görünürler: derinlik öncelikli arama yığın kullanır, genişlik öncelikli arama ise kuyruk.
Sık yapılan bir yanlış, her dizinin verimli bir kuyruk olabileceği düşüncesidir. Birçok dilde bir dizinin başından eleman çıkarmak, JavaScript'te shift() ya da Python'da pop(0) gibi, kalan tüm elemanları kaydırır; bu yüzden büyük kuyruklar için Python'daki collections.deque gibi özel bir yapı kullanılmalıdır.
Hangisini kullanmalısınız?
Yığın şu durumlarda doğru seçim:
- En yeni eleman ilk işlenmeli.
- Adımları geri almanız ya da geriye doğru izlemeniz gerekiyor.
- Parantezler ya da fonksiyon çağrıları gibi iç içe yapıları işliyorsunuz.
Kuyruk şu durumlarda doğru seçim:
- Elemanlar geliş sırasına göre işlenmeli.
- Çalışanlara işi adil biçimde dağıtıyorsunuz.
- Genişlik öncelikli aramada olduğu gibi seviye seviye gezmeniz gerekiyor.
Üç eleman ekleyip birini çıkarmak
# Stack: last in, first out
stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack.pop()) # "c", the newest item# Queue: first in, first out
from collections import deque
queue = deque()
queue.append("a")
queue.append("b")
queue.append("c")
print(queue.popleft()) # "a", the oldest itemSık sorulan sorular
Yığın mı kuyruk mu daha hızlı?
Doğru gerçeklendiğinde ikisi de eleman ekler ve çıkarırken O(1) zaman alır. Seçim hıza değil, ihtiyaç duyduğunuz sıraya bağlıdır.
İki yığından kuyruk yapılabilir mi?
Evet. Yeni elemanları bir yığına itin, ikinci yığından çıkarın; ikincisi boşaldığında her şeyi ona aktarın. Bu sırayı tersine çevirir ve amortize O(1) zamanda FIFO davranışı verir.
Öncelik kuyruğu bir kuyruk mudur?
Bir çeşididir: elemanlar geliş sırasına göre değil öncelik sırasına göre çıkar ve genellikle düz bir liste yerine bir yığın (heap) üzerine kurulur.