İki stack'li kuyruk işlemleri
Görev tanımı
Problem
Yalnız tepeye push, tepeden pop ve tepeyi okumayı kullanarak iki stack'ten ilk giren ilk çıkar bir kuyruk kur. Bir işlem listesini işle: ["push", x] x'i ekler, ["pop"] en eski değeri çıkarır ve bildirir, ["peek"] de onu çıkarmadan bildirir. Bildirilen değerleri sırasıyla döndür; pop ya da peek kuyruğu boş bulursa None bildir. Her işlem amortize (amortized) O(1) zamana mal olmalı.
Örnekler
Input: ops = [["push", 1], ["push", 2], ["peek"], ["pop"],
["push", 3], ["pop"], ["pop"]]
Output: [1, 1, 2, 3]
Neden: değerler geldikleri sırayla çıkıyor
Input: ops = [["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]]
Output: [7, 8]
Neden: 7 çıktıktan sonra kalan en eski değer 8
Input: ops = [["pop"], ["push", 4], ["peek"]]
Output: [None, 4]
Neden: edge case: boş bir kuyruğu pop etmek None bildirir
İpuçları
0 / 3
Bir stack'i diğerine boşaltmak değerlerinin sırasını ters çevirir. Gelenlerden oluşan bir stack'i boşalttıktan sonra tepede hangi değer olur?
Gelen değerler için bir stack, pop ve peek'leri karşılamak için ikinci bir stack kullan. Asıl soru, ilkinden ikincisine ne zaman boşaltılacağı.
Yalnız hizmet eden stack boşken boşalt ve o zaman her şeyi karşıya taşı. Hizmet eden stack'te değer oldukça tepesi her zaman kuyrukta hâlâ duran en eski değerdir.
- Hedef zaman
- O(m)
- Hedef alan
- O(m)
Kısıtlar
- O(1) amortized time per operation
- stacks allow only push, pop and top
Çözüm
Yeni değerler bir gelen kutusu stack'ine gider. Pop ve peek'ler bir giden kutusu stack'inden okur; yalnız giden kutusu boşken bütün gelen kutusu ona boşaltılır; bu da gelişleri ters çevirir ve en eskisi tepeye çıkar. Hâlâ değer tutan bir giden kutusuna boşaltmak eski değerleri yenilerin altına gömerdi; sırayı doğru tutan boşluk kontrolüdür. Her değer en fazla iki kez push ve iki kez pop edilir; bu yüzden m işlem toplamda O(m) tutar, bu da işlem başına amortize O(1)'dir. Saklanan değerler için alan O(n).
def run_queue(ops):
inbox, outbox, out = [], [], []
for op in ops:
if op[0] == "push":
inbox.append(op[1])
continue
if not outbox:
while inbox: # reverse once: the oldest ends on top
outbox.append(inbox.pop())
if not outbox:
out.append(None) # the queue is empty
elif op[0] == "pop":
out.append(outbox.pop())
else:
out.append(outbox[-1])
return out
print(run_queue([["push", 1], ["push", 2], ["peek"], ["pop"], ["push", 3], ["pop"], ["pop"]])) # -> [1, 1, 2, 3]
print(run_queue([["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]])) # -> [7, 8]
print(run_queue([["pop"], ["push", 4], ["peek"]])) # -> [None, 4]Kodda değil de fikirde mi takıldın? İki stack'ten kuyruk bunu anlatıyor.