Implement Stack using Queues
Yalnızca kuyrukları depolama olarak kullanan, son giren ilk çıkar yığını oluşturun. Bir kuyruk yalnızca sona öğe ekleyebilir, öndeki öğeyi kaldırabilir veya okuyabilir ve boyutunu bildirebilir. Yığın push x (x'i üste koy), pop (üstteki öğeyi kaldırıp döndür), top (üstteki öğeyi döndür ve yığında tut) ve empty (yığın boş mu?) işlemlerini destekler.
İşlemler ops içinde sırayla gelir; args[i], bir push için değeri, aksi durumda 0 değerini tutar. İşlemleri boş bir yığın üzerinde çalıştırın ve her işlem için bir dize döndürün: push için "null", pop veya top için metin olarak sayı ve empty için "true" ya da "false".
Fonksiyon
- opsstring-array
- işlemler, çalıştırılma sırasına göre
- 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 bir yanıt, metin olarak
Kısıtlar
1 ≤ ops.length ≤ 1000args.length == ops.length- Her
ops[i],push,pop,topveyaemptydeğerlerinden biridir. -109 ≤ args[i] ≤ 109bir push işlemi için, diğer herhangi bir işlem içinargs[i] == 0.popvetopyalnızca yığında en az bir öğe bulunduğunda çağrılır.
Örnekler
- Girdi
- ops = ["push", "push", "top", "pop", "empty"]args = [1, 2, 0, 0, 0]
- Çıktı
- ["null", "null", "2", "2", "false"]
- Açıklama
- 2 en son girdi, bu yüzden en üstte:
topvepopikisi de"2"değerini döndürür. 1 hâlâ içeride, bu yüzdenempty"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", "7", "null", "9", "4", "true"]
- Açıklama
- İlk pop 7'yi, yani en son eklenen öğeyi döndürür. 9, 4'ün üstüne gelir ve ondan önce çıkar; bu nedenle sonraki pop işlemleri
"9"ve"4"değerlerini döndürür ve yığın boşalır.
- Girdi
- ops = ["empty", "push", "top", "pop", "empty"]args = [0, -3, 0, 0, 0]
- Çıktı
- ["true", "null", "-3", "-3", "true"]
- Açıklama
- Yığın boş başlar, bu nedenle ilk yanıt
"true"olur. Negatif bir değer de diğerleri gibi saklanır: top ve pop ikisi de"-3"değerini döndürür ve yığın yeniden boşalır.
Ek soru
Tek bir kuyruğu koruyup işi push işleminden pop işlemine taşıyarak push işlemini O(1) yapabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir kuyruk önce en eski öğesini, bir yığınsa en yenisini verir. Bir kuyruktaki en yeni öğenin önce çıkması için nerede durması gerekir?
Öndeki öğeyi çıkarıp arkaya eklemek kuyruğu bir sıra döndürür. Tam bir tur kuyruğu olduğu gibi bırakır; daha kısa bir tur ise öğeleri önden alıp diğerlerinin arkasına taşır.
xöğesini kuyruğa ekledikten sonra, diğersize-1öğeleri teker teker önden arkaya taşı. Artıkxönde, daha eski öğeler ise en yeniden başlayarak arkasında yer alıyor; böylece pop ve top yalnızca öndeki öğeye erişiyor.
Çözüm
Bir kuyruk öğeleri en eskiden başlayarak, bir yığın ise en yeniden başlayarak çıkarır ve bir kuyruk arka öğesini hiçbir zaman göstermez. Tek aracın önden dequeue edip arkaya enqueue etmektir; bu da kuyruğu döndürür. En yeni öğeyi, okumak istediğinde ya da gelir gelmez öne getirmek için kuyruğu döndür.
İki kuyruk, pop işleminde en yeni öğeyi çıkar
Sezgi
Kuyruktaki main öğelerini geliş sırasına göre tut; böylece en yeni öğe arkada olur ve bir ekleme işlemi enqueue eder. Bir pop, tek bir öğe kalana kadar diğer tüm öğeleri ikinci bir kuyruk olan spare üzerine taşır: en yeni öğe. Bu öğeyi kuyruktan çıkar ve kuyrukları değiştir; çünkü spare artık geri kalan öğeleri özgün sıralarında tutar. Bir top, aynı dolaşımı yapar ama en yeni öğeyi spare üzerine de ekler.
Her pop veya top, depolanan her öğeyi bir kez taşır: her biri bir top ile takip edilen 500 push işlemi 1 + 2 + ... + 500, yani yaklaşık 125.000 taşıma işlemi tutar.
Algoritma
- İki kuyruk tut: öğelerin geliş sırasına göre bulunduğu
mainve boş birspare. push xiçin:x'imainkuyruğuna ekle.popvetopiçin: geriye bir öğe kalana kadar öğelerimain'denspare'e taşı ve bu öğeyi yanıt olarak kuyruktan çıkar.topiçin bu öğeyisparekuyruğuna da ekle. Kuyrukları yer değiştir.emptyiçin:main'in boş olup olmadığını bildir.
from collections import deque
class QueueStack:
def __init__(self):
self.main = deque() # the oldest item at the front, the newest at the back
self.spare = deque() # empty between operations
def push(self, x):
self.main.append(x)
def _move_all_but_newest(self):
# Pass every item except the newest to the spare queue, in order.
while len(self.main) > 1:
self.spare.append(self.main.popleft())
def pop(self):
self._move_all_but_newest()
newest = self.main.popleft()
self.main, self.spare = self.spare, self.main
return newest
def top(self):
self._move_all_but_newest()
newest = self.main.popleft()
self.spare.append(newest) # top keeps the item
self.main, self.spare = self.spare, self.main
return newest
def empty(self):
return not self.main
def stackOps(ops, args):
stack = QueueStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
result.append(str(stack.pop()))
elif op == "top":
result.append(str(stack.top()))
else:
result.append("true" if stack.empty() else "false")
return resultTek kuyruk, her eklemeden sonra döndür
Sezgi
Kuyruğu her zaman yığın düzeninde, en yeni öğe başta olacak şekilde tutun. Böylece pop bir kuyruktan çıkarma işlemidir, top baştaki öğeyi okur ve ikinci kuyruğa gerek kalmaz. Yeni bir x öğesi, zaten en yeniden eskiye sıralanmış olan eski öğelerin arkasına, kuyruğun sonuna eklenir. Baştaki öğeyi kuyruktan çıkarıp size-1 kez kuyruğun sonuna ekleyin: her adımda daha eski bir öğe x'in arkasına taşınır ve sıraları korunur; böylece x başa gelir.
İlk örnekte, [1] üzerine 2 eklemek [1, 2] sonucunu verir ve bir döndürme [2, 1] sonucunu verir. k öğe üzerine ekleme yapmak k döndürme gerektirir; bu nedenle ekleme O(n), diğer işlemler O(1) maliyetlidir.
Algoritma
- Önü her zaman yığının üst öğesi olan tek bir kuyruk tut.
push xiçin:xöğesini kuyruğa ekle, ardındansize-1kez tekrarla: öndeki öğeyi kuyruktan çıkar ve yeniden kuyruğa ekle.popiçin: öndeki öğeyi kuyruktan çıkar ve döndür.topiçin: öndeki öğeyi çıkarmadan döndür.emptyiçin: kuyruğun boş olup olmadığını bildir.
from collections import deque
class QueueStack:
def __init__(self):
self.queue = deque() # the newest item is always at the front
def push(self, x):
self.queue.append(x)
# Rotate the older items behind x, so x comes out first.
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.popleft())
def pop(self):
return self.queue.popleft()
def top(self):
return self.queue[0]
def empty(self):
return not self.queue
def stackOps(ops, args):
stack = QueueStack()
result = []
for op, arg in zip(ops, args):
if op == "push":
stack.push(arg)
result.append("null")
elif op == "pop":
result.append(str(stack.pop()))
elif op == "top":
result.append(str(stack.top()))
else:
result.append("true" if stack.empty() else "false")
return result
Tuzaklar ve uç durumlar
size-1yerinesizekez döndürmek. Tam bir tur,x'i arkada bırakır; bu yüzden sonraki pop en eski öğeyi döndürür.x'i kuyruğa eklemeden önce döndürmek. Eski öğeler daire içinde döner vexyine arkaya gelir.- İki kuyruk kullanırken öğeyi
top'a geri koymamak. Böylece sonraki pop, onun altındaki öğeyi döndürür. - İki kuyruk kullanırken bunları yer değiştirmemek. Öğeler
spare'de kalır veemptyçok erken"true"yanıtını verir. - Sayı veya boolean döndürmek. Push için
"null"da dahil olmak üzere her yanıt bir dizgedir.
Sıkça sorulan sorular3
Yığınlardan oluşturulan bir yığının zaman karmaşıklığı nedir?
Her eklemede dönen tek bir kuyrukla, ekleme O(n), çıkarma, tepeyi görme ve boşluk kontrolü O(1) olur. Her çıkarmada öğeleri taşıyan iki kuyrukla, ekleme O(1), çıkarma ve tepeyi görme O(n) olur. Her iki durumda da her öğe bir kez saklandığından, alan karmaşıklığı O(n) olur.
Kuyruklardan oluşturulan bir yığın, yığınlardan oluşturulan bir kuyruktan neden daha yavaştır?
Bir yığını diğerine dökmek sırasını tersine çevirir; bu nedenle tek bir dökme, yığın sırasını kuyruk sırasına dönüştürür ve her öğe kullanım ömrü boyunca bir kez hareket eder. Öğeleri kuyruklar arasında taşımak sıralarını korur, dolayısıyla hiçbir aktarım sırayı tersine çevirmez. Bu yüzden burada bir işlem her zaman O(n) maliyetindedir.
Masraflı işlem push mı yoksa pop mu olmalı?
Daha seyrek yapılan işlem maliyetli olsun. Yığın, büyümesinden çok daha sık top ve pop ile okunuyorsa, her okumayı O(1) yapmak için push sırasında döndür. Birkaç pop işleminden önce çok sayıda push geliyorsa, push işlemini O(1) tut ve taşıma işlemini pop sırasında yap.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def stackOps(ops, args):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
ops = ["push", "push", "top", "pop", "empty"] args = [1, 2, 0, 0, 0]
Beklenen Çıktı
["null", "null", "2", "2", "false"]