Yığın ve Kuyruğun Birbirini Simüle Etmesi
İki yığın kullanarak bir kuyruk, iki kuyruk kullanarak da bir yığın uygulayın ve her yaklaşımın itfa edilmiş maliyetini açıklayın.
Yığın ve Kuyruğun Birbirini Simüle Etmesi, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Birini Diğeriyle Neden Taklit Etmeli?
İki yığın kullanarak kuyruk ve iki kuyruk kullanarak yığın uygulamak, klasik tasarım mülakatı sorularıdır. Bu sorular, her iki veri yapısının değişmez koşullarını anlayıp bir yapının güvencesini diğer yapının temel işlemlerini kullanarak koruyabilme becerinizi sınar. Görüşmeciler bunları, amortismanlı karmaşıklığı tartışmaya geçiş noktası olarak da kullanır.
Temel fikir şudur: yığınlar LIFO, kuyruklar ise FIFO düzenindedir. Aralarında dönüşüm yapmak için sırayı tersine çevirmelisiniz; bir yığını başka bir yığına ters çevirerek aktarmak, özgün ekleme sırasını oluşturur ve bu sıra FIFO'dur.
İki Yığın Kullanarak Kuyruk (Ertelenmiş Yaklaşım)
Ertelenmiş yaklaşımda, ekleme işlemleri için bir inbox yığını ve çıkarma işlemleri için bir outbox yığını kullanılır. Kuyruktan çıkarma çağrıldığında outbox boşsa, inbox içindeki tüm öğeleri outbox'a aktarın; bu ters çevirme FIFO sırasını yeniden oluşturur. outbox boş değilse öğeyi doğrudan oradan çıkarın. Aktarmalar ertelendiği için O(n) aktarma maliyeti çok sayıda işleme dağıtılır.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3Yığınlardan Kuyruk için Amortismanlı O(1) Analizi
Her öğe inbox'tan outbox'a en fazla bir kez aktarılır. outbox'tan öğe çıkarma O(1) olduğunda ve aktarmalar yalnızca outbox boşken gerçekleştiğinde, n ekleme ve n çıkarma için toplam iş en fazla 2n yığın işlemidir; toplam karmaşıklık O(n), işlem başına amortismanlı karmaşıklık ise O(1)'dir. Bu, tek tek işlemlerin en kötü durumda O(n) olabileceği, ancak ortalamanın O(1) olduğu anlamına gelir.
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most nİki Kuyruk Kullanarak Yığın (Ertelenmiş Çıkarma)
Kuyruklar FIFO olduğundan, iki kuyrukla yığın uygulamak daha az doğaldır. Ertelenmiş çıkarma yaklaşımında bir ana kuyruk ve bir geçici kuyruk tutulur. push işleminde ana kuyruğa ekleme yapılır (O(1)). pop veya peek işleminde son öğe dışındaki tüm öğeler geçici kuyruğa alınır, son öğe kaydedilir ve ardından kuyruklar yer değiştirilir. Bu yaklaşım, her pop işlemi için O(n), her push işlemi için O(1)'dir.
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2Tek Kuyruk Kullanarak Yığın (Eklemede Döndürme)
Tek kuyrukla uygulanan zarif yaklaşım şudur: push işleminde yeni öğeyi kuyruğa ekleyin, ardından yeni öğe ön uca gelecek şekilde kuyruğu döndürün. Döndürme, push işleminden önce kuyrukta bulunan tüm öğeleri kuyruktan çıkarıp yeniden kuyruğa eklemek anlamına gelir. Ardından pop ve peek işlemleri O(1) olur (yalnızca ön uçtan çıkarma veya peek işlemi yapılır). Push işlemi O(n)'dir; bu, iki kuyruklu sürümdeki ödünleşimin tersidir.
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2Ödünleşim Özeti: Hangi Sürümü Seçmelisiniz?
İki yığından kuyruk için: push O(1), pop/peek amortismanlı olarak O(1)'dir; pop işlemlerinin sık olduğu durumlarda bunu tercih edin. İki kuyruktan yığın için: push O(1), pop O(n)'dir; push işlemlerinin pop işlemlerinden çok daha sık olduğu durumlarda bunu tercih edin. Tek kuyruktan yığın için: push O(n), pop O(1)'dir; pop işlemlerinin baskın olduğu durumlarda bunu tercih edin. Yalnızca 'çalışıyor' demenin ötesinde düşündüğünüzü göstermek için bu ödünleşimleri bir mülakatta açıkça ifade edin.
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')Tersine Çevirmek FIFO Düzenini Neden Geri Getirir?
1, 2, 3 öğeleri bir yığına (inbox) eklendiğinde, alttan üste doğru 1, 2, 3 sırasıyla dururlar. Tüm öğeleri ikinci bir yığına (outbox) aktarmak sırayı tersine çevirir: outbox'ın altında 3, üstünde 1 bulunur. outbox'tan öğe çıkarmak 1, ardından 2 ve sonra 3 değerlerini verir; bu tam olarak FIFO ekleme sırasıdır. İki ters çevirmenin (iki yığının) FIFO düzenini geri getirmesinin, tek bir yığının ise LIFO düzeni vermesinin nedeni budur.
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232: Yığınları Kullanarak Kuyruk Uygulama
LeetCode 232, doğrudan 'iki yığından kuyruk' problemidir. Beklenen çözüm, ertelenmiş outbox aktarmasıdır. Mülakatta, her öğenin inbox'tan outbox'a en fazla bir kez taşındığını ve bu nedenle tüm işlemlerin amortismanlı olarak O(1) olduğunu belirtin. Tek tek pop çağrılarının, outbox boş olduğunda en kötü durumda O(n) olabileceğini; ancak n işlem üzerindeki ortalamanın O(1) olduğunu da söyleyin.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225: Kuyrukları Kullanarak Yığın Uygulama
LeetCode 225, 'kuyruklardan yığın' problemidir. Tek kuyruğu ekleme sırasında döndüren çözüm en temiz çözümdür. x öğesini ekledikten sonra, daha önce kuyrukta bulunan tüm öğeleri x'in arkasına taşıyarak kuyruğu döndürün. Bu, her push işlemi için O(n) maliyet getirir; karşılığında top ve pop işlemleri O(1) olur. Ödünleşimi belirtin ve bunun kısıtlarla (örneğin push işlemlerinin az veya pop işlemlerinin yoğun olduğu bir iş yüküyle) uyumlu olduğunu doğrulayın.
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # FalseTek Dizide Üç Yığına Genişletme
İlgili bir tasarım sorusu: tek bir dizi kullanarak üç yığın uygulayınız. Bir yaklaşım, diziyi üç eşit ve sabit bölüme ayırır. Daha esnek bir yaklaşım, işaretçilerle iç içe depolama kullanır; her yığını kendi bölgesinden büyütür ve sınırlar çakıştığında kopyalama yapar. Bu, dinamik dizi yönetimini sınar ve kıdemli düzey mülakatlarda sorulur. Sabit bölüm yaklaşımı daha basittir, ancak yığınlar eşit olmayan biçimde büyürse alanı boşa harcar.
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30Temel Çıkarımlar: Benzetim Desenleri
Karşılıklı benzetim problemleri daha genel bir ilkeyi öğretir: yeterli ara tamponlama ve tersine çevirme kullanıldığında her veri yapısı başka bir veri yapısından oluşturulabilir. Benzetimin maliyeti, hangi işlemleri eniyilediğinize bağlıdır — push işlemini her zaman O(1) veya pop işlemini O(1) yapabilirsiniz; ancak her ikisini de O(1) yapmak için amortismanlı maliyet analizi ya da birden çok yardımcı yapı gerekir.
Bir mülakatta her zaman şunu sorunuz: "Hangi işlemler daha sık gerçekleştiriliyor?" Bu soru, uygulama çeşidinin seçimine yön verir ve işlemsel gereksinimler hakkında kıdemli düzeyde düşündüğünüzü gösterir.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayınız.
Ders Özeti
Bu derste şunları öğrendiniz: iki yığından bir kuyruk oluşturmak, öğeleri gelen kutusundan çıkış kutusuna tembelce aktararak amortismanlı O(1) pop işlemi sağlar, tek kuyruktan bir yığın oluşturmak, her push işleminde kuyruğu döndürerek O(1) pop işlemi sağlar (push maliyeti O(n)) ve hangi işlemin O(1) yapılacağının seçimi kullanım desenine bağlıdır. Sırada karma haritaların iç yapısını ve çakışmaların ele alınmasını inceleyeceğiz.
Sıkça Sorulan Sorular
“Yığın ve Kuyruğun Birbirini Simüle Etmesi” dersi ücretsiz mi?
Evet — “Yığın ve Kuyruğun Birbirini Simüle Etmesi” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Yığın ve Kuyruğun Birbirini Simüle Etmesi” dersinde ne öğreneceğim?
İki yığın kullanarak bir kuyruk, iki kuyruk kullanarak da bir yığın uygulayın ve her yaklaşımın itfa edilmiş maliyetini açıklayın. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Yığın ve Kuyruğun Birbirini Simüle Etmesi” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Yığın Uygulaması ve Kullanım Alanları
- Kuyruk Uygulaması ve Çift Uçlu Kuyruk
- Tekdüze Yığın Kalıbı
- Yığın ve Kuyruğun Birbirini Simüle Etmesi