Pinon ja jonon vastavuoroinen simulointi
Toteuttakaa jono kahdella pinolla ja pino kahdella jonolla sekä selittäkää kummankin lähestymistavan amortisoitu kustannus.
Pinon ja jonon vastavuoroinen simulointi on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Miksi toinen toteutetaan toisen avulla
Jonon toteuttaminen kahdella pinolla ja pinon toteuttaminen kahdella jonolla ovat klassisia suunnitteluun liittyviä työhaastattelukysymyksiä. Ne testaavat, ymmärrättekö molempien tietorakenteiden invariantit ja osaatteko säilyttää yhden rakenteen ominaisuuden käyttäessänne toisen rakenteen perusoperaatioita. Haastattelijat käyttävät näitä tehtäviä myös lähtökohtana amortisoidun aikavaativuuden käsittelylle.
Keskeinen havainto on, että pinot ovat LIFO-rakenteita ja jonot FIFO-rakenteita. Rakenteesta toiseen siirtyminen edellyttää järjestyksen kääntämistä — ja kun pino käännetään toiseen pinoon, tuloksena on alkuperäinen lisäysjärjestys eli FIFO-järjestys.
Jono kahdella pinolla (laiska lähestymistapa)
Laiskassa lähestymistavassa käytetään inbox-pinoa lisäyksiin ja outbox-pinoa poistoihin. Kun dequeue kutsutaan, kaikki alkiot siirretään inbox-pinosta outbox-pinoon, jos outbox on tyhjä — tämä käännös palauttaa FIFO-järjestyksen. Jos outbox ei ole tyhjä, siitä voidaan poistaa alkio suoraan. Siirrot tehdään tarpeen mukaan, jolloin O(n):n siirtokustannus amortisoituu useiden operaatioiden kesken.
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()) # 3Pinoista muodostetun jonon amortisoitu O(1)-analyysi
Jokainen alkio siirretään inbox-pinosta outbox-pinoon enintään kerran. Kun outbox-pinosta poistaminen vie ajan O(1) ja siirrot tehdään vain outbox-pinon ollessa tyhjä, n push- ja n pop-operaation kokonaiskustannus on enintään 2n pino-operaatiota — yhteensä O(n) ja amortisoidusti O(1) operaatiota kohden. Yksittäinen operaatio voi siis pahimmassa tapauksessa viedä ajan O(n), mutta keskimääräinen aikavaativuus on O(1).
# 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 nPino kahdella jonolla (laiska poisto)
Pinon toteuttaminen kahdella jonolla on epäluontevampaa, koska jonot ovat FIFO-rakenteita. Laiskassa poistossa ylläpidetään yhtä pääjonoa ja yhtä väliaikaista jonoa. push-operaatiossa alkio lisätään pääjonon perään (O(1)). pop- tai peek-operaatiossa kaikki viimeistä alkiota lukuun ottamatta poistetaan jonosta väliaikaiseen jonoon, viimeinen alkio tallennetaan ja jonot vaihdetaan keskenään. Tämä vie aikaa O(n) jokaista pop-operaatiota kohden, mutta push-operaation kustannus on O(1).
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()) # 2Pino yhdellä jonolla (kierto push-operaatiossa)
Tyylikäs yhden jonon toteutus toimii näin: push-operaatiossa uusi alkio lisätään jonoon, minkä jälkeen jonoa kierretään niin, että uusi alkio siirtyy etupäähän. Kiertäminen tarkoittaa kaikkien ennen push-operaatiota jonossa olleiden alkioiden poistamista ja lisäämistä takaisin jonon perään. Tämän jälkeen pop- ja peek-operaatiot ovat O(1)-aikaisia, koska ne käsittelevät etupäätä. Push-operaatio vie ajan O(n), joten kustannusjakauma on päinvastainen kuin kahden jonon versiossa.
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()) # 2Kompromissien yhteenveto: mikä muunnelma kannattaa valita
Kahdesta pinosta muodostetussa jonossa push-operaatio on O(1) ja pop- sekä peek-operaatiot amortisoidusti O(1) — valitkaa tämä, kun pop-operaatioita tehdään usein. Kahdesta jonosta muodostetussa pinossa push-operaatio on O(1) ja pop-operaatio O(n) — valitkaa tämä, kun push-operaatioita tehdään paljon useammin kuin pop-operaatioita. Yhdestä jonosta muodostetussa pinossa push-operaatio on O(n) ja pop-operaatio O(1) — valitkaa tämä, kun pop-operaatiot ovat hallitsevia. Kertokaa nämä kompromissit haastattelussa selkeästi, jotta osoitatte ajattelevanne muutakin kuin sitä, että ratkaisu vain toimii.
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)')Miksi kääntäminen palauttaa FIFO-järjestyksen
Kun alkiot 1, 2 ja 3 työnnetään pinoon (inbox), ne ovat alhaalta ylöspäin järjestyksessä 1, 2, 3. Kun kaikki alkiot poistetaan ja siirretään toiseen pinoon (outbox), järjestys kääntyy: outbox-pinossa 3 on alhaalla ja 1 päällä. outbox-pinosta poistettaessa alkiot saadaan järjestyksessä 1, 2 ja 3 — täsmälleen lisäysjärjestyksessä eli FIFO-järjestyksessä. Siksi juuri kaksi käännöstä eli kaksi pinoa palauttaa FIFO-järjestyksen, kun taas yksi pino tuottaisi LIFO-järjestyksen.
# 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: jonon toteuttaminen pinojen avulla
LeetCode 232 on suora 'jonon toteuttaminen kahdella pinolla' -tehtävä. Odotettu ratkaisu on laiska outbox-siirto. Haastattelussa todetkaa, että jokainen alkio siirtyy inbox-pinosta outbox-pinoon enintään kerran, joten kaikkien operaatioiden amortisoitu aikavaativuus on O(1). Mainitkaa, että yksittäinen pop-kutsu voi pahimmassa tapauksessa viedä ajan O(n), kun outbox on tyhjä, mutta n operaation keskimääräinen aikavaativuus on O(1).
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: pinon toteuttaminen jonojen avulla
LeetCode 225 on 'pinon toteuttaminen jonojen avulla' -tehtävä. Yhden jonon kierto push-operaatiossa on selkein ratkaisu. Kun alkio x on lisätty, kiertäkää jonoa siirtämällä kaikki siinä jo olleet alkiot x:n taakse. Tämä maksaa O(n) jokaista push-operaatiota kohden, mutta tekee top- ja pop-operaatioista O(1)-aikaisia. Kertokaa kompromissi ja varmistakaa, että se sopii rajoituksiin, esimerkiksi tilanteeseen, jossa push-operaatioita on vähän tai pop-operaatioita paljon.
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()) # FalseKolmen pinon toteuttaminen yhdessä taulukossa
Aiheeseen liittyvä suunnitteluhaaste: toteuttakaa kolme pinoa yhden taulukon avulla. Yksi tapa on jakaa taulukko kolmeen yhtä suureen kiinteään osaan. Joustavammassa tavassa käytetään lomitettua tallennusta ja osoittimia: kukin pino kasvaa omalla alueellaan, ja elementit kopioidaan, kun rajat törmäävät. Tämä testaa dynaamisten taulukoiden hallintaa, ja tätä kysytään senioritason haastatteluissa. Kiinteisiin osiin jakaminen on yksinkertaisempaa, mutta se tuhlaa tilaa, jos pinot kasvavat eri tahtiin.
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 30Keskeiset opit: simulointimallit
Molemminpuolisen simuloinnin ongelmat opettavat yleisemmän periaatteen: mikä tahansa tietorakenne voidaan rakentaa toisen avulla, kun käytettävissä on riittävästi välipuskurointia ja kääntämistä. Simuloinnin kustannus riippuu siitä, mitä operaatioita optimoitte — push voidaan aina tehdä ajassa O(1) tai pop ajassa O(1), mutta molempien tekeminen ajassa O(1) edellyttää amortisointia tai useita apurakenteita.
Haastattelussa kannattaa aina kysyä: 'Mitkä operaatiot ovat yleisimpiä?' Tämä ohjaa toteutusmuunnelman valintaa ja osoittaa senioritason ymmärrystä toiminnallisista vaatimuksista.
Pikatesti
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte: kahdesta pinosta muodostettu jono saavuttaa amortisoidun O(1)-poiston siirtämällä alkioita inboxista outboxiin vasta tarvittaessa, yhdestä jonosta muodostettu pino saavuttaa O(1)-poiston kiertämällä jonoa jokaisen push-operaation yhteydessä (push O(n)) ja se, mikä operaatio kannattaa tehdä ajassa O(1), riippuu käyttötavasta. Seuraavaksi tutustutte hajautustaulujen sisäiseen toimintaan ja törmäysten käsittelyyn.
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Pinon ja jonon vastavuoroinen simulointi” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Pinon ja jonon vastavuoroinen simulointi”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Pinon ja jonon vastavuoroinen simulointi”?
Toteuttakaa jono kahdella pinolla ja pino kahdella jonolla sekä selittäkää kummankin lähestymistavan amortisoitu kustannus. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Pinon ja jonon vastavuoroinen simulointi”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä DSA Interview Prep-oppitunnilla?
Kyllä. Jokainen DSA Interview Prep-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Pinon toteutus ja sovellukset
- Jonon toteutus ja deque
- Monotonisen pinon malli
- Pinon ja jonon vastavuoroinen simulointi