Tarayıcıda “Geri” düğmesine bastığında en son açtığın sayfaya dönersin; bir hizmet merkezindeki elektronik kuyrukta ise ilk bileti alan ilk hizmet alır. Bu iki gündelik kural, iki temel veri yapısının, yani yığıtın (stack) ve kuyruğun (queue) özüdür. Onların altında daha da basit tuğlalar vardır: dizi ve bağlı liste. Her yapının güçlü ve zayıf yanlarını bilmek, programın hızını çoğu zaman algoritmadan bile fazla belirler.
Dizi ve dinamik dizi
DiziTanım
Eşit boyutlu elemanların bellekte art arda, boşluksuz saklandığı yapı. Bir elemanın adresi indeksinden basit bir formülle hesaplanır; bu yüzden herhangi bir elemana erişim O(1) sürer.
Burada
- base
- dizinin başlangıç adresi (A[0]'ın adresi)
- i
- eleman indeksi (0'dan başlar)
- s
- bir elemanın boyutu, bayt
İndekslerin 0'dan başlamasının nedeni de budur: i, elemanın başlangıçtan kaç adım uzakta olduğunu gösterir.
Örnek 1: adres hesabı
Problem
4 baytlık tam sayılardan oluşan bir dizi 1000 adresinden başlıyor. A[25] hangi adrestedir? A[5]'ten A[6]'ya geçince adres ne kadar değişir?
Çözümü gösterÇözümü gizle
Çözüm
Komşu elemanlar arasındaki fark s = 4 bayt'tır.
Hesap, i ne olursa olsun bir çarpma ve bir toplamadır; erişimin O(1) olmasının nedeni budur.
Bunun bir bedeli var: dizinin ortasına eleman eklemek için sağdaki bütün elemanlar bir yer kaydırılmalıdır, yani O(n). Boyut da önceden sabittir. Dinamik dizi (Python list, Java ArrayList, C++ vector) bunu şöyle çözer: yer bitince iki kat büyük yeni bir dizi ayırır ve eski elemanları oraya kopyalar.
Burada
- n
- eklenen eleman sayısı
- 1 + 2 + … + 2ᵏ
- tüm büyütmelerde kopyalanan eleman sayısı (< 2n)
Amortize maliyet: n eklemenin toplam işi 3n'den azdır; yani ara sıra yapılan “pahalı” büyütmelere rağmen bir ekleme ortalama O(1)'dir.
class DynamicArray:
def __init__(self):
self.cap, self.n, self.copies = 1, 0, 0
self.data = [None]
def append(self, x):
if self.n == self.cap:
self.cap *= 2
new = [None] * self.cap
for i in range(self.n):
new[i] = self.data[i]
self.copies += 1
self.data = new
self.data[self.n] = x
self.n += 1
arr = DynamicArray()
for k in range(1, 1025):
arr.append(k)
if k in (1, 2, 3, 5, 9, 17, 1024):
print(k, arr.cap, arr.copies)
print('copies per append:', arr.copies / arr.n)Beklenen çıktı
1 1 0 2 2 1 3 4 3 5 8 7 9 16 15 17 32 31 1024 1024 1023 copies per append: 0.9990234375
Bağlı listeler
Bağlı listeTanım
Her düğümün bir değer ve sonraki düğüme bir işaretçi tuttuğu zincir. Düğümler belleğin herhangi bir yerinde olabilir; ilk düğüme baş (head) denir. Çift yönlü bağlı listede her düğüm bir öncekini de gösterir.
| İşlem | Dinamik dizi | Tek yönlü bağlı liste |
|---|---|---|
| i. elemana erişim | O(1) | O(n) |
| başa ekleme / baştan silme | O(n) | O(1) |
| sona ekleme | amortize O(1) | O(1) (tail işaretçisiyle) |
| bilinen bir düğümden sonra ekleme | O(n) (kaydırma) | O(1) |
| değere göre arama | O(n) | O(n) |
| bellek | sıkışık, önbellek dostu | düğüm başına ek işaretçi, dağınık |
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, value):
self.head = Node(value, self.head)
def reverse(self):
prev, cur = None, self.head
while cur:
nxt = cur.next
cur.next = prev
prev, cur = cur, nxt
self.head = prev
def items(self):
cur = self.head
while cur:
yield cur.value
cur = cur.next
lst = LinkedList()
for city in ['Shaki', 'Ganja', 'Baku']: lst.push_front(city)
print(list(lst.items()))
lst.reverse()
print(list(lst.items()))Beklenen çıktı
['Baku', 'Ganja', 'Shaki'] ['Shaki', 'Ganja', 'Baku']
push_front yeni düğümü başa O(1)'de bağlar. reverse, her düğümün işaretçisini geriye çevirerek listeyi tek geçişte, O(n) zaman ve O(1) ek bellekle ters çevirir. Bu, mülakatların klasik bir sorusudur.Yığıt (LIFO) ve kuyruk (FIFO)
| Yapı | İlke | İşlemler (hepsi O(1)) | Kullanım alanları |
|---|---|---|---|
| Yığıt | LIFO — son giren ilk çıkar | push, pop, peek | çağrı yığıtı, geri alma, parantez denetimi, DFS |
| Kuyruk | FIFO — ilk giren ilk çıkar | enqueue, dequeue, front | yazdırma kuyruğu, ağ tamponları, görev zamanlayıcıları, BFS |
Örnek 2: sonek ifadeyi yığıtla hesaplamak
Problem
Sonek (ters Leh) gösteriminde işleç, işlenenlerinden sonra gelir. 5 1 2 + 4 * + 3 - ifadesini yığıtla hesapla.
Çözümü gösterÇözümü gizle
Çözüm
5 → [5]
1 → [5, 1]
2 → [5, 1, 2]
+ → 1 + 2 = 3 → [5, 3]4 → [5, 3, 4]
* → 3 · 4 = 12 → [5, 12]+ → 5 + 12 = 17 → [17]3 → [17, 3]
- → 17 − 3 = 14 → [14]Cevap: 14 (olağan gösterimde 5 + (1 + 2) · 4 − 3). Her simge bir kez işlenir → O(n).
from collections import deque
def balanced(text):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in text:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
for s in ['(a[i] + b) * {c}', '(]', '((x)']:
print(s, balanced(s))
queue = deque(['Aysel', 'Murad', 'Leyla'])
queue.append('Elvin')
print(queue.popleft(), 'is served;', list(queue), 'wait')Beklenen çıktı
(a[i] + b) * {c} True
(] False
((x) False
Aysel is served; ['Murad', 'Leyla', 'Elvin'] waitdeque iki uçtan da O(1)'de ekleme ve silme yapar; ideal bir kuyruktur.Kuyruk sabit boyutlu bir dizi üzerinde de kurulabilir: dairesel tampon baş (head) ve kuyruk (tail) indekslerini tutar, dizinin sonuna gelince mod işlemiyle başa “sarar”. Böyle bir kuyruk bellek ayırmaz; ağ kartlarında, ses kartlarında ve klavye tamponunda kullanılır.
Burada
- head
- kuyruğun ilk elemanının indeksi
- size
- kuyruktaki eleman sayısı
- m
- dizinin kapasitesi
- tail
- sonraki elemanın yazılacağı indeks
Örnek 3: dairesel tampon
Problem
Kapasitesi m = 6 olan dairesel bir tamponda head = 4, size = 3. Yeni eleman hangi indekse yazılır? Ardından iki eleman çıkarılıyor. head kaç olur?
Çözümü gösterÇözümü gizle
Çözüm
tail = (4 + 3) mod 6 = 7 mod 6 = 1 → yeni eleman A[1]'e yazılır, size = 4.
İki çıkarma: head = (4 + 1) mod 6 = 5, sonra (5 + 1) mod 6 = 0; size = 2.
Klasik bir mülakat sorusu: iki yığıttan kuyruk kurmak. Yeni elemanlar in yığıtına push edilir. Çıkarma gerektiğinde out yığıtı boşsa, in'deki bütün elemanlar tek tek out'a taşınır; bu sırada sıra tersine döner ve en eski eleman tepeye çıkar. Tek bir çıkarma O(n) sürebilir, ama her eleman en fazla bir kez taşınır; bu yüzden n işlemin toplamı O(n), yani işlem başına amortize O(1)'dir.
Unutma
- Dizi elemanının adresi base + i · s'dir; erişim O(1), ortaya ekleme O(n).
- Dinamik dizi kapasitesini geometrik artırır; bu yüzden sona ekleme amortize O(1)'dir.
- Bağlı listede başa veya bilinen düğümden sonra ekleme O(1), indeksle erişim ise O(n)'dir.
- Yığıt LIFO'dur (çağrılar, geri alma, parantezler), kuyruk FIFO'dur (tamponlar, BFS); ikisinin de işlemleri O(1)'dir.
- Dairesel tampon indeksleri mod m ile sarar ve sabit bellekte bir kuyruk sağlar.