Bir deque (çift yönlü kuyruk), hem baştan hem de sondan öğe eklemeye ve çıkarmaya izin veren bir veri yapısıdır. İkili bağlı bir liste kullanarak deque oluşturmak, son derece uygun ve verimli bir yaklaşımdır.

İşte bir deque'nin ikili bağlı bir liste kullanarak nasıl uygulanacağına dair bir örnek:

1. Düğüm Sınıfı

Öncelikle, her düğümü temsil eden bir sınıf oluşturmalıyız. Her düğüm, bir değer ve iki bağlantı içerir: prev (önceki düğüme işaret eder) ve next (sonraki düğüme işaret eder).

class Node:
    def __init__(self, value, prev_node=None, next_node=None):
        self.value = value
        self.prev = prev_node
        self.next = next_node

2. Deque Sınıfı

Sonra, ikili bağlı bir listeyi kullanarak deque'yi temsil eden bir sınıf oluşturmalıyız. Bu sınıf, başlangıçta iki sentinel düğüm (header ve trailer) içerebilir, böylece ekleme ve çıkarma işlemleri daha düzenli hale gelir.

class Deque:
    def __init__(self):
        self.header = Node(None)
        self.trailer = Node(None)
        self.header.next = self.trailer
        self.trailer.prev = self.header
        self.size = 0

    def append_left(self, value):
        new_node = Node(value, self.header, self.header.next)
        self.header.next.prev = new_node
        self.header.next = new_node
        self.size += 1

    def append_right(self, value):
        new_node = Node(value, self.trailer.prev, self.trailer)
        self.trailer.prev.next = new_node
        self.trailer.prev = new_node
        self.size += 1

    def pop_left(self):
        if self.size == 0:
            print("Deque is empty")
            return None
        value = self.header.next.value
        self.header.next = self.header.next.next
        self.header.next.prev = self.header
        self.size -= 1
        return value

    def pop_right(self):
        if self.size == 0:
            print("Deque is empty")
            return None
        value = self.trailer.prev.value
        self.trailer.prev = self.trailer.prev.prev
        self.trailer.prev.next = self.trailer
        self.size -= 1
        return value

Bu Deque sınıfı, deque işlemlerini gerçekleştirebilmek için dört yöntem içerir:

append_left: Deque'nin sol tarafına bir öğe ekler.

append_right: Deque'nin sağ tarafına bir öğe ekler.

pop_left: Deque'nin sol tarafından bir öğe çıkarır.

pop_right: Deque'nin sağ tarafından bir öğe çıkarır.

Bu uygulama, hem baştan hem de sondan ekleme ve çıkarma işlemlerinin O(1) zaman karmaşıklığında gerçekleşmesine olanak tanır, bu da veri yapısının oldukça verimli olmasını sağlar.

# Deque oluşturuluyor
my_deque = Deque()

# Sol tarafa öğeler ekleniyor
my_deque.append_left(3)
my_deque.append_left(2)
my_deque.append_left(1)

# Sağ tarafa öğeler ekleniyor
my_deque.append_right(4)
my_deque.append_right(5)
my_deque.append_right(6)

# Deque'deki öğeleri yazdırmak için bir fonksiyon
def print_deque(deque):
    current = deque.header.next
    while current != deque.trailer:
        print(current.value, end=' ')
        current = current.next
    print()

print_deque(my_deque)  # 1 2 3 4 5 6

# Sol ve sağ taraftan öğeler çıkarılıyor
print(my_deque.pop_left())  # 1
print(my_deque.pop_right()) # 6

print_deque(my_deque)  # 2 3 4 5

# Deque boşaltılıyor
while my_deque.size > 0:
    print(my_deque.pop_left(), end=' ') # 2 3 4 5

print("\nDeque is empty now!") # Deque şimdi boş