Kuyruk Uygulaması ve Çift Uçlu Kuyruk
Python’un deque yapısıyla bir kuyruk oluşturun, döngüsel kuyruk uygulayın ve tekdüze kuyruk kullanarak kayan pencere maksimumunu bulun.
Kuyruk Uygulaması ve Çift Uçlu Kuyruk, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Kuyruk Veri Yapısı
Bir kuyruk, ilk giren ilk çıkar (FIFO) veri yapısıdır. Kuyruğa ilk eklenen öğe, ilk çıkarılan öğedir; bu, bir mağazadaki kasa kuyruğuna benzer. Temel işlemler enqueue (arkaya ekleme) ve dequeue (önden çıkarma) işlemleridir. Kuyruğun verimli olabilmesi için her ikisinin de O(1) olması gerekir.
Python listesini kuyruk olarak kullanmak cazip görünse de yanlıştır: list.pop(0) tüm öğeleri kaydırdığı için O(n)'dir. Doğru araç, O(1) zamanda appendleft, append, popleft ve pop sağlayan collections.deque yapısıdır.
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Çift Uçlu Kuyruk Kullanılarak Kuyruk Sınıfı
Mülakatçıların beklediği adlandırılmış işlemleri sağlamak için deque yapısını bir Queue sınıfıyla sarmalayın. İçeride enqueue, append çağırır; dequeue ise popleft çağırır. peek işlemi, öğeyi kaldırmadan queue[0] değerini okur.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2Kuyruk ile BFS
Kuyruğun klasik uygulaması Genişlik Öncelikli Arama (BFS)'dır. Kökü kuyruğa ekleyin; kuyruk boş olmadığı sürece bir düğüm çıkarın, işleyin ve ziyaret edilmemiş komşularını kuyruğa ekleyin. Düğümleri seviye seviye işlediğimiz için BFS, ağırlıksız bir grafikte en kısa yolu doğal olarak bulur. Kuyrukta her zaman en fazla iki komşu seviyeden düğümler bulunur.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Dairesel Kuyruk (LeetCode 622)
LeetCode 622 'Dairesel Kuyruk Tasarlama': etrafında dolaşan, sabit kapasiteli bir kuyruk uygulayın. k boyutunda bir dizi ve iki işaretçi kullanın: head ve tail. Arka uçta enqueue, başta dequeue işlemi yapın ve konumları k'ye göre modülüs alarak hesaplayın. Bir count değişkeni, kuyruğun dolu ve boş durumlarını birbirinden ayırır; aksi hâlde her iki durumda da head == tail olur.
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMonotonik Çift Uçlu Kuyrukla Kayan Pencere Maksimumu
LeetCode 239 'Kayan Pencere Maksimumu': k boyutundaki her pencere için en büyük öğeyi bulun. Kaba kuvvet yaklaşımı O(n*k)'dir. O(n) yaklaşımı, indeksleri depolayan azalan monotonik çift uçlu kuyruk kullanır. Her yeni öğe için: pencerenin dışındaki indeksleri önden çıkarın; daha küçük değerlere sahip indeksleri arkadan çıkarın (bunlar gelecekteki hiçbir pencerede maksimum olamaz). Ön uç her zaman maksimumu tutar.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Kuyruk için Neden Yalnızca Liste Değil, Çift Uçlu Kuyruk?
Python'un list.pop(0) işlemi, kalan her öğenin bir konum sola kaydırılması gerektiği için ilk öğeyi O(n) zamanda kaldırır. n ekleme ve n silme için toplam maliyet O(n²) olur. collections.deque, sabit boyutlu bloklardan oluşan çift bağlı bir listedir; popleft yalnızca bir işaretçiyi ayarladığı için O(1)'dir. 10^5 düğümlü bir grafikte BFS için O(n) ile O(n²) arasındaki fark, 100 ms ile 100 saniye arasındaki farktır.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')İkili Ağaçta Seviye Sıralı Gezinme (LeetCode 102)
LeetCode 102 'İkili Ağaçta Seviye Sıralı Gezinme': tüm düğüm değerlerini seviyelere göre döndürün. Bir kuyruk kullanın; her seviyenin başında kuyruğun boyutunu kaydedin (bu, o seviyede kaç düğüm bulunduğunu gösterir). Tam olarak bu sayı kadar düğüm çıkarın; değerlerini toplayın ve çocuklarını kuyruğa ekleyin. Kuyruk boşalana kadar tekrarlayın.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]heapq ile Öncelik Kuyruğu
Python'ın heapq modülü bir minimum yığın (öncelik kuyruğu) sağlar: en küçük öğe her zaman ilk olarak kuyruktan çıkarılır. heapq.heappush(h, item) bir öğeyi O(log n) zamanda ekler ve heapq.heappop(h) minimum öğeyi O(log n) zamanda çıkarır. Dijkstra algoritması ve en iyi k öğe gibi problemler için heapq, basit kuyruğun yerini alır.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Duvar Kâğıdı Deseni: Kelime Merdiveni için Kuyruk
LeetCode 127 'Kelime Merdiveni': yalnızca sözlükteki sözcükleri kullanarak bir sözcüğü diğerine dönüştürmek için gereken en az sayıdaki tek karakter değişikliğini bulun. Bunu, kenarların bir karakter farklılık gösteren sözcükleri birbirine bağladığı bir grafik olarak modelleyin. Bu grafik üzerinde BFS kullanmak, sözlüğün boyutu n ve sözcük uzunluğu L olmak üzere O(n * L²) zamanda en kısa yolu (en az adımı) bulur.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5Çift Uçlu Kuyruk Yapısı
collections.deque, her iki uçtan da verimli biçimde ekleme ve çıkarma yapabileceğiniz bir çift uçlu kuyruktur. Yöntemler: ön uç için appendleft ve popleft; arka uç için append ve pop. Böylece çift uçlu kuyruk hem bir FIFO kuyruğu (sağa ekleme + popleft) hem de bir LIFO yığını (append + pop) olarak kullanılabilir. Kayan pencere maksimumu her iki ucu da kullanır: eski indeksleri soldan, daha küçük değerleri sağdan çıkarır.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Özet: Kuyruk, Çift Uçlu Kuyruk ve Öncelik Yığını
Problem için doğru aracı seçin. FIFO işleme ve BFS için basit bir kuyruk (çift uçlu kuyruk) kullanın. Kayan pencerenin maksimum veya minimum değerine ihtiyaç duyduğunuzda monotonik çift uçlu kuyruk kullanın; bu yapı, baskın öğeleri çıkararak sıralı bir değişmez koşulu korur. Sırasından bağımsız olarak genel minimum veya maksimum değere, örneğin Dijkstra ya da en iyi k öğe problemlerinde, ihtiyaç duyduğunuzda öncelik kuyruğu (heapq) kullanın. Hangi aracı ne zaman ve neden seçmeniz gerektiğini bilmek, mülakatlarda sınanan önemli bir beceridir.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: collections.deque, O(1) zamanda kuyruğa ekleme ve kuyruktan çıkarma sağladığı için Python'daki doğru kuyruk uygulamasıdır, BFS, düğümleri seviyeler hâlinde işlemek için kuyruk kullanır ve ağırlıksız graflarda en kısa yolları bulur ve monotonik azalan çift uçlu kuyruk, baskın indeksleri çıkararak kayan pencere maksimumunu O(n) zamanda bulur. Sırada monotonik yığın desenini ayrıntılı olarak inceleyeceğiz.
Sıkça Sorulan Sorular
“Kuyruk Uygulaması ve Çift Uçlu Kuyruk” dersi ücretsiz mi?
Evet — “Kuyruk Uygulaması ve Çift Uçlu Kuyruk” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Kuyruk Uygulaması ve Çift Uçlu Kuyruk” dersinde ne öğreneceğim?
Python’un deque yapısıyla bir kuyruk oluşturun, döngüsel kuyruk uygulayın ve tekdüze kuyruk kullanarak kayan pencere maksimumunu bulun. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Kuyruk Uygulaması ve Çift Uçlu Kuyruk” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yığın Uygulaması ve Kullanım Alanları
- Kuyruk Uygulaması ve Çift Uçlu Kuyruk
- Tekdüze Yığın Kalıbı
- Yığın ve Kuyruğun Birbirini Simüle Etmesi