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

Çift Uçlu Kuyruklar


Doğuhan ELMA

205 views

Double-Ended Queues (Çift Uçlu Kuyruklar), veya genellikle "deque" olarak adlandırılan veri yapısı, her iki ucunda da ekleme ve çıkarma işlemlerinin yapılabildiği bir kuyruk türüdür. Bu, deque'nin daha esnek bir veri yapısı olmasını sağlar, çünkü hem kuyruk (FIFO - First-In, First-Out) hem de yığıt (LIFO - Last-In, First-Out) olarak kullanılabilir.

Deque İşlemleri:

Append (Ekleme): Deque'nin sağ ucuna bir öğe ekler.

Append Left (Sol Tarafa Ekleme): Deque'nin sol ucuna bir öğe ekler.

Pop (Çıkarma): Deque'nin sağ ucundan bir öğe çıkarır.

Pop Left (Sol Taraftan Çıkarma): Deque'nin sol ucundan bir öğe çıkarır.

Peek (Gözlemleme): Sağ veya sol uçtaki öğeyi döndürür ama çıkarmaz.

Python'da collections.deque:

Python'un collections modülü, deque veri yapısını içerir. İşte basit bir kullanım örneği:

from collections import deque

d = deque()

# Sağ tarafa ekleme
d.append(5)
d.append(10)

# Sol tarafa ekleme
d.appendleft(1)

# Sağ taraftan çıkarma
right_item = d.pop()

# Sol taraftan çıkarma
left_item = d.popleft()

Performans:

Deque işlemleri genellikle oldukça etkilidir. Her iki uçta da ekleme ve çıkarma işlemleri genellikle O(1) zaman karmaşıklığına sahiptir. Bununla birlikte, deque'nin ortasında bir işlem yapmak O(n) zaman karmaşıklığına sahip olabilir, n'de deque'nin uzunluğu olmak üzere.

Kullanım Durumları:

Deque, birden fazla kullanım durumuna uyarlanabilir. Örneğin, bir pencere içinde bir dizi öğenin hareketli ortalamasını hesaplarken, belirli bir sayıda en son öğeyi tutmak için kullanılabilir.

Sonuç:

Çift uçlu kuyruklar, hem kuyruk hem de yığıt işlevselliğine sahip olduklarından oldukça esnek ve kullanışlı veri yapılarıdır. Bunlar, belirli bir probleme uygun olarak her iki ucunda da işlemler yapma esnekliği gerektiren bir dizi uygulamada kullanılabilir.

 

Çift uçlu kuyruk (deque) oluşturmak için dairesel bir dizi kullanma konsepti oldukça ilginç ve yararlıdır. Bu yapı, her iki ucunda da ekleme ve çıkarma işlemlerinin yapılabildiği bir veri yapısıdır. İşte dairesel bir dizi kullanarak bir deque nasıl uygulanacağına dair ayrıntılı bir açıklama:

Dairesel Dizi Nedir?

Dairesel bir dizi, sabit boyutta bir dizidir, ancak başlangıç ve bitiş noktaları birbirine bağlıdır, böylece bir çember oluşturur. Bu, dizi içinde boş bir yer kalmaksızın verileri düzenlemeyi kolaylaştırır.

Deque Uygulaması:

1. Başlangıç Durumu:

Sabir bir boyutta bir dizi oluşturun ve baş ve son işaretçileri (pointer) kullanarak dizinin hangi bölümünün kullanıldığını izleyin.

2. Sağa Ekleme (Append):

Son işaretçisine bir öğe ekleyin. Eğer deque doluysa, ekleme yapmayın. Son işaretçisini artırın ve gerekirse başa sarın.

3. Sola Ekleme (Append Left):

Baş işaretçisine bir öğe ekleyin. Eğer deque doluysa, ekleme yapmayın. Baş işaretçisini azaltın ve gerekirse sona sarın.

4. Sağdan Çıkarma (Pop):

Son işaretçiden bir öğe çıkarın. Eğer deque boşsa, çıkarma yapmayın. Son işaretçisini azaltın ve gerekirse başa sarın.

5. Soldan Çıkarma (Pop Left):

Baş işaretçiden bir öğe çıkarın. Eğer deque boşsa, çıkarma yapmayın. Baş işaretçisini artırın ve gerekirse sona sarın.

6. Doluluk ve Boşluk Durumları:

Deque'nin dolu veya boş olup olmadığını kontrol edin ve buna uygun olarak işlemleri yürütün.

Dairesel Dizi İle Deque'nin Avantajları:

Zaman Etkinliği: Her iki uçta da ekleme ve çıkarma işlemleri O(1) zaman karmaşıklığına sahiptir.

Alan Etkinliği: Dairesel dizinin yapısı, veri eklemesi ve çıkarması sırasında dizinin tamamının kullanılmasına olanak tanır.

Dezavantajları:

Sabit Kapasite: Deque'nin boyutu sabittir ve yeniden boyutlandırma karmaşıktır.

Uygulama Karmaşıklığı: İşaretçilerin dairesel davranışını ve dolu ve boş durumları uygun şekilde işlemek dikkat gerektirir.

Dairesel dizi kullanarak bir deque uygulaması, hem zaman hem de alan açısından etkili bir yoldur, ancak dikkatli bir uygulama gerektirir. Her iki uçta da sabit zamanlı işlemler sunar ve dizinin tamamını verimli bir şekilde kullanır.

Aşağıda, dairesel bir dizi kullanarak bir deque (çift uçlu kuyruk) nasıl uygulanacağını gösteren Python kodu bulunmaktadır:

class CircularDeque:
    def __init__(self, capacity):
        self.capacity = capacity
        self.size = 0
        self.array = [None] * capacity
        self.front = 0
        self.rear = 0

    def is_full(self):
        return self.size == self.capacity

    def is_empty(self):
        return self.size == 0

    def append(self, value):
        if self.is_full():
            print("Deque is full.")
            return
        self.array[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1

    def appendleft(self, value):
        if self.is_full():
            print("Deque is full.")
            return
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.array[self.front] = value
        self.size += 1

    def pop(self):
        if self.is_empty():
            print("Deque is empty.")
            return
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        removed_item = self.array[self.rear]
        self.size -= 1
        return removed_item

    def popleft(self):
        if self.is_empty():
            print("Deque is empty.")
            return
        removed_item = self.array[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return removed_item

    def display(self):
        i = self.front
        for _ in range(self.size):
            print(self.array[i], end=" ")
            i = (i + 1) % self.capacity
        print()

Bu kod, dairesel bir dizi kullanarak bir deque sınıfını tanımlar. Her iki uçta da ekleme ve çıkarma işlemlerini destekler.

deque = CircularDeque(5)

deque.append(1)
deque.append(2)
deque.appendleft(0)
deque.display()  # Output: 0 1 2

print(deque.popleft())  # Output: 0
print(deque.pop())      # Output: 2

Bu örnek, CircularDeque sınıfının nasıl kullanılacağını gösterir. Ekleme ve çıkarma işlemleri, dairesel dizinin sabit kapasitesi dolana kadar her iki uçta da yapılabilir.

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...