Kuyruklara Giriş
Kuyruk, sıralı bir veri kümesi içeren veri yapısı olarak tanımlanabilir. Kuyruklar etkileşim için üç yöntem sağlar:
- `Enqueue()`: Kuyruğun arkasına yani sonuna yeni veriyi ekler.
- `Dequeue()`: Sıranın önünden yani başından verileri kaldırır ve kaldırılan değeri geri döndürür.
- `Peek()`: Kuyruğun önündeki veriyi sıradan çıkarmadan görmemizi sağlar.
Bu veri yapısı, sinema bileti satın alan bir grup insan gibi somut bir durumu taklit ediyor olarak düşünebilirsiniz. Her kişinin bir adı yani verileri vardır. Sıraya giren ilk kişi bir sonraki kişi gelene kadar sıranın hem başı hem de sonudur. Her yeni kişi sıraya girdikçe, kuyruğun yeni arkası yani son elemanı olur. Kasiyer birine hizmet ettiğinde, sıranın önünden başlar aksi taktirde sırada bekleyen insanlardan tepki gelecektir. Hizmet verilen her kişi sıranın önünden alınır, bir bilet alır ve sıradan yani kuyruktan ayrılır. Sırada kimin olduğunun bilinmesi için onları sıradan çıkarmadan göz atabilir ve isimlerini alabiliriz. Kuyruktaki ilk kişi hizmet verilmesi gereken ilk kişidir. Kuyruklar, yığınların (stacks) aksine ilk giren ilk çıkar (FIFO: First In, First Out) prensibine göre çalışır.
Kuyruğunun Uygulanması
Kuyruklar, yığınlarda olduğu gibi temel bir veri yapısı olan bağlantılı listeler (linked list) kullanılarak uygulanabilir. Kuyruğun önü, bağlantılı bir listenin baş düğümüne eş değerdir. Kuyruk veri yapısı yalnızca kuyruğun önünü veya arkasını etkileyen işlemlere izin verdiği için, bağlantılı listelerdeki gibi diğer düğümlerde herhangi bir geçiş veya değişiklik yapılmasına izin verilmez. Kuyruğun her iki ucunun da erişilebilir olması gerektiğinden hem baş düğüme hem de kuyruk düğümünde birer referans korunmalıdır. Bir kuyruğa yerleştirilebilecek bir diğer kısıtlama ise uzunluğudur. Bir kuyruğun içine yerleştirilebilecek veri miktarının bir sınırı varsa, bu bir “sınırlı kuyruk” olarak tanımlanır.
Yığınlara benzer şekilde, verileri zaten dolu olan bir kuyruğa yeni bir veri eklemeye çalışmak kuyruk taşmasına (queue overflow) yol açacaktır. Hiç verisi olmayan bir kuyruktan veri çıkarmaya çalışırsak ise bu durumda da kuyruğun yetersiz kalmasına (queue underflow) neden olur.
Python ile Kuyruklara Giriş
Yukarıda da belirtildiği gibi, kuyruklar bir FIFO (First In, First Out) yani ilk giren ilk çıkar protokolünü izleyen sıralı bir veri kümesini içeren bir veri yapısıdır. Bunu markette sıra bekleyen insanları ve kasiyeri göz önüne alarak somutlaştıralım.
- Sıranın yani kuyruğun başındaki müşteri ilk hizmet alan müşteri olmalıdır.
- Herhangi bir yeni müşteri sıranın arkasına (kuyruğuna) gitmeli ve önündeki herkese hizmet verilinceye kadar beklemeli.
- Kasiyer yalnızca mevcut kişi ve aldığı ürünlerle ilgilenmelidir.
Bu üç temel kuyruk prensibini bir Queue sınıfı oluşturmak için Python’u kullanabiliriz:
`enqueue()`: Kuyruğa yeni bir düğüm eklememiz için gerekli olan yöntem.
`dequeue()`: Kuyruğun başındaki bir düğümü kaldırmamızı ve değerini döndürmemizi sağlayan yöntem.
`peek()`: Kuyruğun başındaki değeri kaldırmadan sadece değeri görmemizi yani okumamızı sağlayan yöntem.
İlk olarak yine kullanmamız gerek Node sınıfı kodlarına bir göz gezdirelim.
class Node:
def __init__(self, value, next_node = None):
self.value = value
self.next_node = next_node
def set_next_node(self, next_node):
self.next_node = next_node
def get_next_node(self):
return self.next_node
def get_value(self):
return self.value
Sıranın taşmasını veya yetersiz kalmasını önlemek amacıyla boyutunu izlememize yardımcı olacak birkaç değişken de ayarlamamız gerekecek.
from node import Node
# Queue sınıfını oluşturalım
class Queue:
def __init__(self):
self.head = None
self.tail = None
def peek(self):
return self.head.get_value()
Sınırlı kuyruklar, içerilebilecek düğüm sayısı için sınırlar gerektirirken diğer kuyruklar bu sınırlamaları gerektirmez. Bunu hesaba katmak için, Queue sınıfımızda bazı değişiklikler yapmamız gerekecek, böylece gerektiğinde boyutu izleyip sınırlandırabilirsiniz. Bize yardımcı olmak için iki yeni özellik eklememiz gerekecektir:
- Sıranın mevcut boyunu takip etmek için biz `size` değişkeni.
- Sınırlı kuyrukların toplam düğüm sayısını sınırlamak için bir `max_size` değişkeni tanımlamalıyız.
Ek olarak üç yeni yöntem eklememiz gerekecektir.
- `get_size()`: `size` değişkenin değerini dönderecektir.
- `has_space()`: Kuyrukta başka bir düğüm için yer varsa doğru yani `True` değerini döndürecektir.
- `is_empty()`: `size` değişkeni değerimiz sıfıra eşitse doğru yani `True` değerini döndürecektir.
from node import Node
# Queue sınıfını oluşturalım
class Queue:
def __init__(self, max_size=None):
self.head = None
self.tail = None
self.max_size = max_size
self.size = 0
def peek(self):
if self.size > 0:
return self.head.get_value()
else:
print("Görüntülenecek bir değer yok !")
# get_size(), has_space() ve is_empty() metotlarını tanımlayalım
def get_size(self):
return self.size
def has_space(self):
if self.max_size == None:
return True
else:
return self.max_size > self.get_size()
def is_empty(self):
return self.size == 0
`enqueue`, sıraya ekle demenin süslü bir yolu olarak düşünülebilir ve `enqueue()` yöntemi tam olarak bunu yapar. Kuyruğa bir düğüm eklerken ilgilenmemiz gereken üç senaryo bulunmaktadır.
- Kuyruk boş ise eklediğimiz düğüm kuyruğun hem başı hem de kuyruğu yani sonudur.
- Kuyruğun halihazırda en az bir tane düğümü varsa, eklenen yeni düğüm yeni kuyruk olmalıdır.
- Kuyruk belirtilen sınırda dolu ise kuyrukta taşma istemediğimiz için yeni düğüm eklenmeyecektir.
Queue sınıfı için bir `enqueue()` yöntemi oluşturalım:
# Ekleme metodumuzu tanımlayalım
def enqueue(self, value):
if self.has_space():
item_to_add = Node(value)
print("Kuyruğa " + str(item_to_add.get_value())+ " ekleniyor . . . ")
if self.is_empty():
self.head = item_to_add
self.tail = item_to_add
else:
self.tail.set_next_node(item_to_add)
self.tail = item_to_add
self.size += 1
else:
print("Kuyrukta yeterli alan yok !")
Kuyruğumuza nasıl yeni veriler ekleyeceğimize baktığımıza göre şimdi sırada nasıl kaldırırız sorusu var. Kuyruktan kaldır demenin bir yolu ise `dequeue()` olarak bilinen bir yöntemdir. Ekleme yönteminde yaptığımız gibi burada da kuyruğun boyutunu önemsiyoruz ama ekleme de taşma durumu varken burada yetersiz kalmasını (underflow) önlemek istiyoruz. `peek()` yöntemi ekleme yöntemimizde olduğu gibi sıranın ilk düğümünde bulunan veriyi döndürür. Düğümü kaldırma işleminde ise mevcut baş (head) düğümümüzü kaldıracak ve onu bir sonraki düğüme atayacaktır. Sıradan çıkarma işlemini tanımlarken dikkat etmemiz gereken üç senaryo vardır.
- Kuyruk tamamıyla boş ise kuyruğun yetersiz kalması (underflow) durumu oluşur.
- Kuyrukta sadece bir düğüm olması durumunda onu kaldırmamız gerekir. Bu nedenle kaldırdığımızda kuyruk boş olacaktır ve kuyruğun başını ve sonunu `None` olarak atamamız gerekecektir.
- Kuyrukta birden fazla düğüm var ise ilk düğümü kaldırır ve yeni ilk düğümü sıradaki bir sonraki düğüm olarak atayabiliriz.
# Düğüm kaldırma fonksiyonumuzu tanımlayalım
def dequeue(self):
if self.get_size() > 0:
item_to_remove = self.head
print("Kuyruktan " + str(item_to_remove.get_value())+ " kaldırılıyor . . . ")
if self.get_size() == 1:
self.head = None
self.tail = None
else:
self.head = self.head.get_next_node()
self.size -= 1
return item_to_remove.get_value()
else:
print("Kuyruk boş ! ")
