Implement Queue Using Stacks
Yalnızca iki yığını depolama alanı olarak kullanan, ilk giren ilk çıkar kuyruğu oluştur. Bir yığın yalnızca en üste bir öğe ekleyebilir, en üstteki öğeyi çıkarabilir, en üstteki öğeyi okuyabilir ve boş olup olmadığını belirtebilir. Kuyruk push x (sona x ekle), pop (öndeki öğeyi çıkarıp döndür), peek (öndeki öğeyi döndür) ve empty (kuyruk boş mu?) işlemlerini destekler.
İşlemler sana sıralı olarak ops biçiminde verilir; args[i], bir push işlemi için değeri, diğer tüm işlemler için 0 değerini içerir. İşlemleri boş başlayan tek bir kuyruk üzerinde çalıştır ve her işlem için bir dize döndür: push için "null", pop veya peek için sayı metin olarak, empty için "true" veya "false".
Fonksiyon
- opsstring-array
- işlemler, çalıştırıldıkları sırayla
- argsinteger-array
- her push işlemi için değer, diğer tüm işlemler için 0
- Döndürürstring-array
- işlem başına metin olarak bir yanıt
Kısıtlar
1 ≤ ops.length ≤ 2000args.length == ops.length- Her
ops[i],push,pop,peekveyaemptydeğerlerinden biridir. -109 ≤ args[i] ≤ 109bir push işlemi için,args[i] == 0ise diğer tüm işlemler için.popvepeekyalnızca kuyrukta en az bir öğe olduğunda çağrılır.
Örnekler
- Girdi
- ops = ["push", "push", "peek", "pop", "empty"]args = [1, 2, 0, 0, 0]
- Çıktı
- ["null", "null", "1", "1", "false"]
- Açıklama
- Önce 1'i, ardından 2'yi ekledikten sonra öndeki değer 1'dir; bu nedenle
peekvepopikisi de"1"değerini döndürür. 2 hâlâ içeride olduğundanempty,"false"değerini döndürür.
- Girdi
- ops = ["push", "push", "pop", "push", "pop", "pop", "empty"]args = [4, 7, 0, 9, 0, 0, 0]
- Çıktı
- ["null", "null", "4", "null", "7", "9", "true"]
- Açıklama
- İlk pop 4 değerini, yani en eski öğeyi döndürür. 7 hâlâ beklerken 9 gelir ve 7'den sonra geldiği için 7'den sonra çıkar. Ardından kuyruk boşalır, bu nedenle son yanıt
"true"olur.
- Girdi
- ops = ["empty", "push", "peek", "pop", "empty"]args = [0, -3, 0, 0, 0]
- Çıktı
- ["true", "null", "-3", "-3", "true"]
- Açıklama
- Kuyruk boş başlar, bu nedenle ilk yanıt
"true"olur. Negatif bir sayı da diğerleri gibi saklanır: peek ve pop ikisi de"-3"döndürür ve ardından kuyruk yeniden boş olur.
Gönderirken +15 gizli test
Ek soru
Diğerlerinin amortize sınırını bozmadan, en yeni öğeyi O(1) zamanda döndüren bir back işlemini nasıl eklersin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Yığın öğeleri en yeniden en eskiye doğru, kuyruk ise en eskiden en yeniye doğru verir. Bir yığındaki tüm öğeleri çıkarıp başka bir yığına eklerseniz sıralama nasıl değişir?
Bir yığını diğerine boşaltmak, sıralamayı tersine çevirir; böylece en eski öğe en üste gelir. Her yığına bir görev ver: biri yeni öğeleri ekler, diğeri çıkarma ve en üstteki öğeyi görme işlemlerine hizmet eder.
Push yığınından pop yığınına yalnızca pop yığını boşken aktarın. Daha erken aktarmak, orada hâlâ bekleyen eski öğelerin üzerini yeni öğelerle örter. Böylece her öğe en fazla bir kez taşınır.
Çözüm
Bir yığın, öğeleri geldikleri sıranın tersine, bir kuyruk ise geldikleri sırayla geri verir. Bir yığını ikinci bir yığına boşaltmak, sıralamayı bir kez daha tersine çevirir ve yığın sırasını kuyruk sırasına dönüştürür. Asıl soru, ne zaman boşaltılacağıdır: bunu her işlemde yapmak her seferinde O(n) maliyet getirirken, yalnızca ikinci yığın boşaldığında boşaltmak her öğenin yalnızca bir kez aktarılmasını sağlar.
Tüm yığını her eklemede yeniden sırala
Sezgi
Her öğeyi main adlı tek bir yığında, en eski öğe en üstte olacak şekilde tut. Böylece pop, peek ve empty tek yığın işlemleri olur.
İşin büyük kısmı push işlemine kalır. Yeni öğe, bekleyen her şeyin altına, en alta eklenmelidir; ancak bir yığın yalnızca en üste ekleme yapabilir. Bu yüzden main içindeki her öğeyi ikinci yığın olan helper üzerine taşı, yeni öğeyi boş main yığınına ekle ve her şeyi geri taşı. Her taşıma sırayı tersine çevirir; iki taşıma sırayı eski hâline getirir ve yeni öğe en alta yerleşir.
Bu yöntem doğrudur, ancak her ekleme işleminde depolanan her öğeye iki kez dokunulur. Arka arkaya 1.000 öğe eklemek yaklaşık 2 × (0 + 1 + ... + 999), yani yaklaşık bir milyon taşıma gerektirir; oysa gerçek bir kuyrukta 1.000 adım yeterlidir.
Algoritma
- İki yığın tut: en eski öğe üstte olacak şekilde
mainve boş birhelper. push xiçin:mainiçindeki her öğeyihelperüzerine taşı,xöğesinimainüzerine ekle, ardındanhelperiçindeki her öğeyi tekrarmainüzerine taşı.popvepeekiçin:mainyığınının en üstündeki öğeyi çıkar veya oku.emptyiçin:mainyığınının boş olup olmadığını bildir.- Her yanıtı metin olarak kaydet ve listeyi döndür.
class TwoStackQueue:
def __init__(self):
self.main = [] # the oldest item is on top
self.helper = []
def push(self, x):
# Move everything aside, put x at the bottom, move everything back.
while self.main:
self.helper.append(self.main.pop())
self.main.append(x)
while self.helper:
self.main.append(self.helper.pop())
def pop(self):
return self.main.pop()
def peek(self):
return self.main[-1]
def empty(self):
return not self.main
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return resultGecikmeli aktarım kullanan gelen kutusu ve giden kutusu yığınları
Sezgi
Yığınlara ayrı görevler ver. Her push, O(1) sürede inbox yığınına eklenir. Pop ve peek işlemleri, tepesinde her zaman kuyruktaki en eski öğenin bulunduğu outbox yığınından okur.
outbox boşken bir pop veya peek işlemi geldiğinde, inbox içindeki her şeyi outbox yığınına aktar. En yeni öğe önce inbox yığınından çıkar, bu yüzden outbox yığınının en altına gelir; en eski öğe ise en üste gelir. Yalnızca outbox boşken aktarım yap: içinde hâlâ öğeler varken bunlar inbox içindeki her şeyden daha eskidir, dolayısıyla önce çıkarılmaları gerekir. İkinci örnekte, ilk pop işlemi için 4 ve 7 aktarılır; ardından 9, 7 çıkana kadar inbox içinde bekler.
Tek bir pop işlemi birçok öğeyi taşıyabilir, ancak işi öğe başına say: her değer inbox yığınına bir kez eklenir, outbox yığınına bir kez aktarılır ve bir kez pop edilir. Bu nedenle n işlem toplamda O(n) maliyetlidir; işlem başına amortize maliyet ise O(1)'dir. Her iki yığın da boş olduğunda kuyruk boştur.
Algoritma
inboxveoutboxadında iki boş yığın tut.push xiçin:x'iinboxyığınına ekle.popveyapeekiçin:outboxboşsa,inboxiçindeki her öğeyioutboxyığınına aktararak çıkar. Ardındanoutboxyığınının en üstündeki öğeyi çıkar veya oku.emptyiçin: her iki yığının da boş olup olmadığını bildir.- Her yanıtı metin olarak kaydet ve listeyi döndür.
class TwoStackQueue:
def __init__(self):
self.inbox = [] # new items go on top
self.outbox = [] # the oldest item is on top
def push(self, x):
self.inbox.append(x)
def _refill(self):
# Only when the outbox is empty: pouring the inbox over reverses it,
# so the oldest item lands on top.
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._refill()
return self.outbox.pop()
def peek(self):
self._refill()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
def queueOps(ops, args):
queue = TwoStackQueue()
result = []
for op, arg in zip(ops, args):
if op == "push":
queue.push(arg)
result.append("null")
elif op == "pop":
result.append(str(queue.pop()))
elif op == "peek":
result.append(str(queue.peek()))
else:
result.append("true" if queue.empty() else "false")
return result
Tuzaklar ve uç durumlar
Çoğu hata, yanlış zamanda aktarım yapmaktan veya yalnızca tek bir yığını kontrol etmekten kaynaklanır.
outboxhâlâ öğeler içerirkeninbox’ıoutbox’a aktarmak. Yeni öğeler eskilerin üzerine gelir ve önce çıkar; bu da kuyruk sırasını bozar. İkinci örnekte 9, 7’den önce çıkar.- Yalnızca
outbox’a bakarakemptybildirmek. Bir push işleminden hemen sonra yeni öğeinbox’ta bulunur; bu yüzdenoutboxboş olsa da kuyruk boş değildir. peekişleminin depopile aynı yeniden doldurma işlemini gerektirdiğini unutmak. İlk push işlemlerinden hemen sonra yapılan bir peek,outbox’ın boş olduğunu görür.- Bir kuyruk kitaplığı kullanmak veya yığının tabanını indeksle okumak. Amaç, yalnızca yığın işlemlerini kullanarak kuyruk sırasını elde etmektir.
- Metin yerine sayılar veya boolean değerler döndürmek. Push işlemi için
"null"dâhil, her yanıt bir dizgedir.
Sıkça sorulan sorular4
İki yığından oluşturulan bir kuyruğun zaman karmaşıklığı nedir?
Push işlemi O(1)'dir. Pop ve peek işlemleri amortize O(1)'dir: tek bir çağrı her öğeyi bir yığından diğerine taşıyabilir, ancak her öğe kullanım ömrü boyunca en fazla bir kez taşınır; bu nedenle n işlem toplamda O(n) maliyetlidir. İki yığın birlikte her öğeyi bir kez tutar, dolayısıyla alan karmaşıklığı O(n)'dir.
Burada amortize O(1) ne anlama geliyor?
Bu, tek bir işlem yavaş olabilse de tüm dizi boyunca işlem başına ortalama maliyetin sabit olduğu anlamına gelir. 1.000 öğeyi boşaltan bir pop işleminin maliyeti, öncesindeki 1.000 ucuz push işlemiyle karşılanır; çünkü bu öğeler bir daha asla boşaltılmaz. n işlemden oluşan hiçbir dizi, yaklaşık 4n yığın adımından fazlasına mal olmaz.
Neden bir değil de iki yığına ihtiyacın var?
Tek bir yığın yalnızca en yeni öğesini gösterir, kuyruk ise en eskisine ihtiyaç duyar. Bir yığının en altına ulaşmak, üstündeki her şeyi kaldırmak anlamına gelir ve bu öğelerin bekleyecek bir yere ihtiyacı vardır; bu yer de ikinci yığındır. Öğeleri diğer yığına taşımak sıralarını tersine çevirir ve en yeniden başlayanı en eskiden başlayana dönüştüren de bu tersine çevirmedir.
Bunun yerine kuyrukları kullanarak bir yığın uygulayabilir misin?
Evet, ancak alışılmış yöntemler amortize edilmiş bir tasarruf sağlamaz. Yaygın bir yöntemde tek bir kuyruk kullanılır: yeni bir öğe ekledikten sonra, eski öğelerin her birini önden alıp arkaya eklersin; böylece yeni öğe en öne gelir. Bu, push işlemini O(n), pop işlemini ise O(1) yapar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def queueOps(ops, args):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
ops = ["push", "push", "peek", "pop", "empty"] args = [1, 2, 0, 0, 0]
Beklenen
["null", "null", "1", "1", "false"]