Jump to content
  • entries
    33
  • comments
    0
  • views
    69,722

Dizi Tabanlı Kuyruk Tanımlama


Doğuhan ELMA

138 views

Array-Based Queue Implementation, bir kuyruk (queue) veri yapısının dizi (array) kullanılarak nasıl uygulanacağını ifade eder. Bu uygulama, belirli bir boyuttaki bir dizi üzerinde işlemler yapmayı içerir.

Bu tür bir kuyruk yapısında, iki önemli gösterge (genellikle "front" ve "rear" olarak adlandırılır) kullanılır. Bunlar, dizideki en ön ve en son öğelerin konumlarını belirtir.

class ArrayQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = self.rear = -1

    def enqueue(self, item):
        if (self.rear + 1) % self.capacity == self.front: # Kuyruk dolu
            return "Kuyruk dolu."
        elif self.is_empty(): # Kuyruk boş
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            return "Kuyruk boş."
        removed_item = self.queue[self.front]
        if self.front == self.rear: # Sadece bir öğe var
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return removed_item

    def is_empty(self):
        return self.front == -1

    def size(self):
        if self.rear >= self.front:
            return self.rear - self.front + 1
        else:
            return self.capacity - (self.front - self.rear) + 1

Açıklama:

capacity değeri, kuyruk kapasitesini belirtir.

front ve rear değerleri, dizideki ön ve arka konumları gösterir.

enqueue fonksiyonu, bir öğeyi kuyruğa ekler.

dequeue fonksiyonu, bir öğeyi kuyruktan çıkarır.

is_empty fonksiyonu, kuyruğun boş olup olmadığını kontrol eder.

size fonksiyonu, kuyruktaki öğe sayısını döndürür.

Bu uygulama, dizilerin sabit boyutlu olması nedeniyle kapasite sınırlamasına sahiptir. Dolayısıyla, kuyruğun dolup dolmadığını kontrol etmek de önemlidir. Ayrıca, dizi bazlı kuyrukta öğelerin eklenip çıkarılmasıyla oluşan boşluklar yerine, halka şeklinde bir yapı (circular array) kullanarak daha etkili bir kullanım sağlanmıştır. Bu, enqueue ve dequeue işlemlerinde kullanılan modüler aritmetikle (% işareti) elde edilir.

Array-Based Queue (Dizi Tabanlı Kuyruk) uygulamasının analizi, bu yapıyı anlamak ve etkinliğini değerlendirmek için önemlidir. İşte bu uygulamanın bazı temel yönlerinin analizi:

1. Veri Yapısı:

Dizi tabanlı bir kuyruk, altta yatan dizi veri yapısını kullanır. Bu, kuyruk içindeki öğeleri düzenlemek ve saklamak için kullanılır.

2. İşlemler:

Enqueue (Ekleme): Kuyruğun sonuna bir öğe ekler. Eğer kuyruk dolu ise ve yeniden boyutlandırma gerekmiyorsa, bu işlem O(1) zaman karmaşıklığına sahiptir.

Dequeue (Çıkarma): Kuyruğun başındaki öğeyi çıkarır. Bu işlem de O(1) zaman karmaşıklığına sahip olabilir, ancak bazı uygulamalarda O(n) olabilir (örneğin, çıkarma sonrası tüm öğelerin kaydırılması gerekiyorsa).

Peek (Üstteki Öğeyi Gözlemleme): Kuyruğun en üstündeki öğeyi döndürür ama çıkarmaz. Bu işlem O(1) zaman karmaşıklığına sahiptir.

3. Yeniden Boyutlandırma:

Dizi dolu olduğunda, genellikle kapasitesini artırmak için yeniden boyutlandırılır. Bu, O(n) zaman karmaşıklığına sahip bir işlemdir, çünkü tüm öğelerin yeni diziye kopyalanması gerekir.

4. Bellek Kullanımı:

Dizi tabanlı kuyruk, önceden belirlenmiş bir kapasiteye sahip olabilir veya dinamik olarak yeniden boyutlandırılabilir. Dinamik yeniden boyutlandırma, daha esnek bir bellek kullanımı sağlar, ancak performans üzerinde belirli bir etkisi olabilir.

5. Circular Array Kullanımı:

Dairesel bir dizi kullanılarak kuyruk uygulanabilir. Bu, front ve rear indekslerin dizi sınırları içinde kalmak üzere modüler aritmetikle güncellenmesini içerir. Bu, eklemelerin ve çıkarmaların etkin bir şekilde yapılmasını sağlar ve kuyruğun kapasitesinin tam olarak kullanılmasına yardımcı olur.

Sonuç:

Dizi tabanlı kuyruk, oldukça etkin bir veri yapısıdır ve en yaygın kuyruk uygulamalarından biridir. İhtiyaca göre düzenlenebilir, yeniden boyutlandırılabilir ve performansı optimize edilebilir. Ancak, yeniden boyutlandırma gereksinimleri ve belirli bir kapasitenin olması gibi bazı kısıtlamalara sahip olabilir. Uygun bir uygulama seçimi, belirli bir kullanım durumu ve ihtiyaçlara bağlı olarak değişebilir.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...