3.5: Queue Analizi ve Big O

⏱️ Zaman Karmaşıklığı (Time Complexity)

Operasyon	List	Deque	Circular Queue	Açıklama
Enqueue	O(1)*	O(1)	O(1)	Sona ekleme
Dequeue	O(n) ⚠️	O(1)	O(1)	Baştan silme
Peek/Front	O(1)	O(1)	O(1)	Başa bakma
isEmpty	O(1)	O(1)	O(1)	Boşluk kontrolü
Size	O(1)	O(1)	O(1)	Eleman sayısı

* List.append() amortize O(1)'dir ancak pop(0) her zaman O(n)!

💾 Alan Karmaşıklığı (Space Complexity)

🔄 Circular Queue

O(n) - Sabit boyut

Bellek kullanımı öngörülebilir. Önceden ayrılmış alan.

📏 Dinamik Queue

O(n) - Değişken boyut

Yeniden boyutlandırma maliyeti. Hafıza parçalanması riski.

🔍 Neden List ile Dequeue Yavaş?

Shifting Problemi: Python listesi bitişik hafızada tutulur. Baştan sildiğinizde TÜM elemanlar kaymak zorundadır.

Görsel: pop(0) Sonrası Kaydırma

Önce: [A, B, C, D, E]

A

B

C

D

E

⬇️ pop(0) → A çıkarılıyor

Sonra: [B, C, D, E] - 4 kaydırma işlemi!

B

C

D

E

-

1 milyon eleman = 999,999 kaydırma işlemi! 😱

🧪 Performans Karşılaştırma Testi

Farklı Queue implementasyonlarını 50,000 enqueue/dequeue ile test edelim:

Python Kodu

import time
from collections import deque

N = 50_000
print(f"🧪 {N} enqueue + {N} dequeue testi\n")
print("=" * 50)

# 1. Python List (Kötü Yöntem)
liste = []
start = time.time()
for i in range(N):
    liste.append(i)
for _ in range(N):
    liste.pop(0)  # O(n) - Her seferinde kaydırma!
list_time = time.time() - start
print(f"📋 List (pop(0))  : {list_time:.4f} sn")

# 2. collections.deque (İyi Yöntem)
kuyruk = deque()
start = time.time()
for i in range(N):
    kuyruk.append(i)
for _ in range(N):
    kuyruk.popleft()  # O(1) - Sabit zaman!
deque_time = time.time() - start
print(f"🔄 Deque (popleft): {deque_time:.4f} sn")

# 3. Circular Queue (Numpy)
import numpy as np

class CircularQueue:
    def __init__(self, capacity):
        self.data = np.zeros(capacity, dtype=int)
        self.head = self.tail = self.size = 0
        self.capacity = capacity
    def enqueue(self, val):
        if self.size < self.capacity:
            self.data[self.tail] = val
            self.tail = (self.tail + 1) % self.capacity
            self.size += 1
    def dequeue(self):
        if self.size > 0:
            val = self.data[self.head]
            self.head = (self.head + 1) % self.capacity
            self.size -= 1
            return val

cq = CircularQueue(N)
start = time.time()
for i in range(N):
    cq.enqueue(i)
for _ in range(N):
    cq.dequeue()
cq_time = time.time() - start
print(f"⭕ Circular Queue : {cq_time:.4f} sn")

print("=" * 50)
print(f"\n📊 Sonuç:")
print(f"   Deque, List'ten {list_time/deque_time:.0f}x daha hızlı!")
print(f"   Circular Queue saf Python olmasına rağmen O(1) garanti ediyor.")

import time
from collections import deque
import numpy as np

N = 50_000
print(f"🧪 {N} enqueue + {N} dequeue testi\n")
print("=" * 50)

# 1. Python List
liste = []
start = time.time()
for i in range(N): liste.append(i)
for _ in range(N): liste.pop(0)
list_time = time.time() - start
print(f"📋 List (pop(0))  : {list_time:.4f} sn")

# 2. collections.deque
kuyruk = deque()
start = time.time()
for i in range(N): kuyruk.append(i)
for _ in range(N): kuyruk.popleft()
deque_time = time.time() - start
print(f"🔄 Deque (popleft): {deque_time:.4f} sn")

# 3. Circular Queue
class CircularQueue:
    def __init__(self, capacity):
        self.data = np.zeros(capacity, dtype=int)
        self.head = self.tail = self.size = 0
        self.capacity = capacity
    def enqueue(self, val):
        if self.size < self.capacity:
            self.data[self.tail] = val
            self.tail = (self.tail + 1) % self.capacity
            self.size += 1
    def dequeue(self):
        if self.size > 0:
            val = self.data[self.head]
            self.head = (self.head + 1) % self.capacity
            self.size -= 1
            return val

cq = CircularQueue(N)
start = time.time()
for i in range(N): cq.enqueue(i)
for _ in range(N): cq.dequeue()
cq_time = time.time() - start
print(f"⭕ Circular Queue : {cq_time:.4f} sn")

print("=" * 50)
print(f"\n📊 Sonuç: Deque, List'ten {list_time/deque_time:.0f}x hızlı!")

Çıktı bekleniyor...

📈 Karmaşıklık Grafiği

■ O(1) - Deque/Circular ■ O(n) - List pop(0)

💡 Ne Zaman Hangisini Kullanmalı?

Durum	Önerilen	Neden?
Genel Amaçlı Queue	`collections.deque`	O(1) performans, kolay kullanım
Sabit Boyutlu Buffer	Circular Queue	Bellek öngörülebilirliği, gömülü sistemler
Thread-Safe Queue	`queue.Queue`	Dahili kilit mekanizması
Öncelikli İşlemler	`heapq`	Priority Queue için optimize