CP #44: Queue Problemleri
Kisa bir queue hatirlatmasinin ardindan problemlere gececegiz.
Queue Neydi?
Queue iki basit operasyon icin vardir: enqueue (yani kuyruga ekleme) ve dequeue (kuyruktan cikarma). Bu operasyonlar ilk giren ilk cikar prensibi uzerinden sonuc verir. Queue'nun en sonundaki elemana genelde tail ve basindaki elemana da head adi verilir.
Linked list ile implemente edilebilir. Bu durumda enqueue ve dequeue islemleri O(1) maliyet ile yapilabilir. Array ile de implemente edilebilir ancak maliyetler daha yuksek olacaktir (buna gelecegiz). Ayrica queue yapisindan, head ve tail elemanlari koparmadan da gozatmak icin metodlar bulunur.
Ayrica python standart kutuphanesinde bulunan bir doubly-linked-list yapisi olan dequeue ile de queue davranisi elde edilebilir. En basa ekleme cikarma ve de en sona ekleme cikarma islemleri O(1) ile yapilabilir.
Siralamanin korunmasi gereken problemlerde queue yapisi one cikmaktadir.
Python Dequeue Class:
- q.append(e) ile queue'nun en sonuna eleman ekleyebiliriz
- q[0] ile head elemana bakis atabiliriz (koparmadan)
- q[-1] ile tail elemana bakis atabiliriz
- q.popleft() en bastaki elemani koparir yani dequeue islemi saglar.
Problemlere gecelim.
Binary Tree Level Order Traversal
Node(val, left, right) data yapisina sahip node'lardan olusan bir binary tree icin, node'larin val degerlerini level order'a gore dondurunuz. Her bir level kendine ait array icerisinde olmalidir. Ornek: [[1], [2, 3], [4,5,6,7]] gibi.
Cozum
Bu problemi gecmiste kac kere cozduk bilmiyorum. Ama fazla idman goz cikarmaz. Buradaki anahtar, level orderin korunmasi. Ayrica her bir level icin yeni bir array olusturulmasi gerekiyor. Bu da demek oluyor level_1'i ornegin olustururken, level_2'yi de bir taraftan bir yere kaydediyor olmamiz lazim. Bunu da tek bir queue ile, level1'i islerken yapabiliyoruz.
from collections import deque
def level_order(head):
# queue'ya head'i ekleyerek basliyoruz
q = deque([head])
ret = [] # tum levelleri tutacak olan buyuk array
# queue bitince, binary tree'deki elemanlar da bitmis demektir
while q:
# queue'da su ana kadar olan elemanlar
# tek bir array icerisinde konmali.
# o yuzden suan mevcut queue'de kac eleman varsa
# o kadar donecek bir dongu ayarlayalim
for _ in range(len(q)):
# bu leveldeki elemanlari tutacak array
level = []
# queue'den en bastaki elemani kopariyoruz
cur = q.popleft()
# val degerini level'a ekleyelim
level.append(cur.val)
# left ve right node'lar var ise, ki bunlar gelecek level
# bunlari queue'nun en sonuna ekliyoruz ki
# gelecek iterasyonda, yeni bir levelda
# bunlar islenecek
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
# level bitti, simdi bu arrayi buyuk donus arrayina ekleyebiliriz
ret.append(level)
# son olarak da buyuk arrayi donduruyoruz
return ret
Bakacak olursak binary tree'de bulunan tum elemanlari 1 kere ziyaret ettik. Ayrica queue popleft ve append disinda bir kompleksite kullanmadik. Sonuc olarak O(n) time compl. ve O(n) space compl. sahip bir cozum elde etmis olduk.
Implement A Circular Queue
Queue yapisi, bir array ve baslangicla bitis indexlerini tutan iki ek degisken ile implemente edilebilir. Bu tarz queue yapisina circular queue adi verilmektedir. Enqueue ve dequeue islemleri O(1) maliyet ile yapilabilmektedir.
Bu sekilde bir circular queue yapisi implemente ediniz. Queue'nun tutabilecegi maksimum sayi olan kapasite degeri constructor'da verimeli ve kapasite asilacagi zaman queue kendisini dinamik olarak resize edebilmelidir. Ayrica enqueue, dequeue ve de o an queue'de bulunan eleman sayisini veren size metodlarini da implemente ediniz.
Cozum
Yani hem circular queue hem de dynamic resizing var. Circular queue soyle gozukuyor:
Bu yapinin, normal bir array ile implemente edilmis olan queue'den farki ve avantaji su ki, on tarafta dequeue olmus elemanlardan bosalan yerleri, yeni gelen elemanlar ile doldurabiliyor. Bu sayede hafiza daha etkili kullanilmis oluyor. Ayni zamanda surekli tekrar eden islerin planlanmasinda yani ornegin eldeki calisan programlarin CPU'dan yeterince faydalanmasinda kullanilabiliyor.
Resimde front denilen indexe biz head demistik, rear da tail'e tekabul ediyor. Dequeue edilecegi zaman head'den ediyoruz, enqueue edilecegi zaman da tail'i 1 artirip (ya da taili zaten bos pozisyonda tutup) array elemani set ediyoruz.
class Queue:
# array doldugu zaman kac katina cikartalim?
RESIZE_FACTOR = 2
def __init__(self, capacity):
self.capacity = capacity
# kapasiteye gore, tum elemanlar None olacak sekilde
# arrayi olusturuyoruz
self.arr = [None] * self.capacity
# head, tail indexleri ve eleman sayisi
self.head = self.tail = self.num = 0 def enqueue(self, e):
# array dolu mu? resize gerekli mi?
if self.num == len(self.arr):
# resize gerekli
# resize etmeden once, 0 indexinden sonra gelen
# ve once gelen elemanlari ayni hizaya getirmemiz gerekiyor
self.arr = self.arr[self.head:] + self.arr[:self.head]
# kapasiteyi artiralim
self.arr += [None] * (len(self.arr) * Queue.RESIZE_FACTOR - len(self.arr))
self.head = 0
self.tail = self.num
# gelen elemani ekliyoruz
self.arr[self.tail] = e
self.tail = (self.tail + 1) % len(self.arr)
self.num += 1
def dequeue(self):
self.num -= 1
ret = self.arr[self.head]
self.head = (self.head + 1) % len(self.arr)
return ret
def size(self):
return self.num
Bakacak olursak, tamam dequeue O(1) ama egere kapasite asimi var ise, enqueue noktasinda bagzi komplikasyonlar var. Arrayi tekrar hizaya sokuyoruz ve kapasitesini iki katina cikariyoruz, O(n) bir maliyeti var. Ancak, kapasite asimi zaten her n elemanda bir oluyor. Bu durumda amortized time complexity yine O(1)'a tekabul ediyor.
Implement A Queue Using Stacks
Queue yapisi ilk giren ilk cikar mantigi ile calismaktadir. Stack ise, ilk giren son cikar mantiginia sahip. Array yerine stack veya stackler kullanarak Queue yapisi implemente ediniz.
Cozum
Baktigimiz zaman tek bir stack ile bunun yapilamayacagi ortada. Cunku zaten calisma mantiklari tam ters istikamette. Bu yuzden 2 tane kullanmayi deniyorum. A ve B diyecegim 2 stack olsun. A stack'inda da 3 eleman enqueue edilmis olsun.
3
2
1
A B
Simdi dequeue yapmak istesek, 1 elemanini geri dondurmemiz gerek. O zaman, A'da sadece 1 eleman kalana kadar bunlari alip, B'ye push etmemiz gerek. Sonuc soyle olacak:
2
1 3
A B
Artik burada A'dan pop edip dondurebilirz. Bir de B'nin haline bakarsak, siradaki dequeue islemini direk buradan yapabilecegimizi goruyoruz. Cunku zaten A'dan alip B'ye push ederek siralamayi reverse etmis olduk.
Dequeue icin mantik soyle o zaman, B'de eleman var ise direk pop et dondur. B guvenli stack. Egere B'de eleman yok ise, A'da sadece 1 eleman kalana kadar A'dan pop edip B'ye push et ve A'da son kalan tek elemani dondur. Ve de zaten enqueue'de gelen elemanlari A'ya push ediyoruz.
class Queue:
def __init__(self):
# stack olarak standart list kullanalim
self.A = []
self.B = []
def dequeue(self):
if self.B:
return self.B.pop()
else:
# A'da tek eleman birakmaca
while len(self.A) > 1:
self.B.append(self.A.pop())
# A'da tek eleman kaldi
return self.A.pop()
def enqueue(self):
self.A.append()
Bakacak olursak enqueue islemi amortize O(1) cunku alttaki list yapisi dynamic resize olabilir. Dequeue'de ise, en kotu senaryoda n-1 elemani A stack'ten pop edip, B stack'e push ediyoruz ki O(n) maliyet demek oluyor. Ancak, bunu ne siklikla yapiyoruz? Ilk dequeue islemi gelene kadar diyelim 10 item enqueue edildi. Ilk dequeue'de bunlarin hepsini B'ye aktariyoruz dogru ancak diger 9 dequeue islemi O(1) maliyete sahip olacak cunku direk B'den pop ediyoruz. O zaman amortize olarak O(1) time compl. sahip diyebiliriz.
Implement A Queue With Max API
Tuttugu elemanlar icinde max degerini donduren bilr queue yapisi implemente ediniz.
Cozum
Cok cok naive yontem, max degeri icin bir degisken tutmak. Enqueue'de is kolay, gelen eleman max'tan buyuk ise max degerini guncelleriz. Ama dequeue'de eger max eleman gitmisse, yeni max elemani bulmak icin kalan tum elemanlari traverse etmek gerekir ki O(n) maliyetinde bir islem.
Optimize edebiliriz. Max degeri icin bir int yerine, yine bir queue kullanabiliriz. Ben once stack kullanmayi dusunmustum ama siralamalari ters oldugu icin mantikli olmuyor. Max degerleri icin de bir queue tutttugumuzda da birkac edge case ortaya cikiyor. Queue'den dequeue ederken, en soldan ediyoruz. Ayni sekilde max queue'sunda da en solda, mevcut en buyuk eleman durmali. Yani,
q : 1 2 3 4 5
max : 5
gibi. Cunku zaten q'dan dequeu ettigimizde 5'e gelene kadar max item degismiyor. (Soldan deque ettigimizi gozunuzde canlandiriniz). Peki, ya dusme olursa,
q : 1 2 3 4 5 3 1
max : 5 3 1
seklinde olmali. Yani q'dan 5 de dequeue edildikten sonra, geriye max eleman olarak 3 kalmali. O da dequeue edildikten sonra, 1 kalmali. Demek ki, yeni gelen eleman (3) mesela, q'daki max elemandan kucuk ise onu max queue'sune eklemek lazim. Ancak:
q : 1 2 3 4 5 1 4
max : 5 4
Egere bir dusme bir cikma olur ise, (ornekte 5'ten 1'e ve 4'e) bu durumda aradaki 1'i max'a eklememek lazim. Daha dogrusu tabi 4 gelmeden once bunu bilemeyeiz, elbette ekleyecegiz ama 4 geldigi zaman 1'i cikarmak lazim. O zaman soyle yapiyoruz. Yeni bir eleman geldigi zaman, max-q'da sagdan sola dogru kendisinden kucuk elemanlari atiyoruz. Ancak kendisinden buyuk eleman geldigi zaman duruyoruz.
from collections import deque
class Queue:
def __init__(self):
self.q = deque()
self.m = deque()
def enqueue(self, x):
# max-q'da kendisinden kucuk eleman kalmayana kadar
# pop edelim
while self.m and self.m[-1] < x:
self.m.pop()
# simdi max-q'ya append edebiliriz
self.m.append(x)
self.q.append(x)
def dequeue(self):
# eger dequeue edilecek eleman mevcut max ise
# mevcut max'i da enqueue ediyoruz
if self.m[0] == self.q[0]:
self.m.popleft()
return self.q.popleft()
Bakacak olursak, dequeue O(1) maliyete sahip. Enqueue'de ise, bir miktar pop islemi yapiyoruz ki, worst case senaryoda (tum elemanlardan buyuk bir eleman gelmesi durumunda), n-1 kere donen bir while loop var. Soyle dusunelim: n eleman icin, (en buyugu ensonda olsun) toplamda maliyet ne kadar?
en buyuk elemandan onceki n-1 eleman icin: O(1) * (n-1)
en buyuk eleman icin: O(1) * (n-1) + O(1)
Yani toplamda O(n-1) + O(n). Yani O(2*n). Yani O(n). n eleman icin.
Yani bir elemanin amortize olarak enqueue edilmesi yine O(1)'e tekabul ediyor arkadaslar.
-------
Guzel bir chapter oldu umarim siz de eglenmissinizdir. Eglence demisken size cok begenerek okudugum bir kitabi da nacizane onermis olayim: Linus Torwalds'tan geliyor, Sadece Eglenmek Icin.
Stay hungry, stay foolish, stay healthy :)
Ciao!
Yorumlar
Yorum Gönder