Virn (andmestruktuur) — LIFO definitsioon, toimimine ja näited

Virn (LIFO) selgelt ja praktiliselt: definitsioon, push/pop toimimine, koodinäited ja rakendused — õpi virna toimimist samm-sammult.

Virn on üks tähtsamaid andmestruktuure arvutiteaduses. Et mõista, kuidas virn töötab, mõelge mängukaartide kaardipakile, mis on näoga allapoole. Me saame hõlpsasti ligipääsu ainult peal olevale kaardile. Kui me tahame vaadata ülemist kaarti, saame seda kas piiluda (jätta virna) või eemaldada (võtta virnast maha). Kui me popime ülemise objekti maha, siis võtame selle virnast välja. Kui me tahame lisada veel ühe kaardi virna tippu, siis me lükkame seda sinna — toiming, mida nimetatakse push.

Virna on tavaliselt kirjeldatud kui LIFO (last-in, first-out) kogumit: viimasena lisatud element on esimene, mis eemaldatakse. Näiteks kui viimane kaart, mille panime oma kaardihunnikusse, oli äss, siis esimene kaart, mille tõmbame ülalt, on seesama äss.

Põhilised operatsioonid

• push(x) — lisa element x virna tippu.
• pop() — eemalda ja tagasta virna ülemine element; tavaliselt eeldatakse, et virn ei ole tühi (või tagastatakse erind/väärtus tühi-korras).
• peek() või top() — vaata virna ülemist elementi, ilma seda eemaldamata.
• isEmpty() — kontrolli, kas virn on tühi.
• size() — tagasta virnas olevate elementide arv.

Tõhusus ja keerukus

• Push ja pop on tavaliselt O(1) aja keerukusega (amortiseeritult ka dünaamilise massiivi puhul).
• Mälu kasutus on O(n), kus n on virna elementide arv.
• Juurdepääs keskmisele või alumisele elemendile ei ole tavaliselt otse võimalik ilma elemente eemaldamata.

Rakendused ja näited

Virnu kasutatakse paljudes olukordades:

• Funktsioonide kõnepinud (call stack) — iga funktsiooni väljakutse salvestatakse virna, tagastused toimuvad LIFO põhimõttel.
• Algoritmid: sügavusjärgne otsing (DFS), tagasijälgimine (backtracking), hulga või puu rekursiivne töötlemine.
• Tekstiredaktorite undo-funktsioon — viimased tegevused tühistatakse vastupidises järjekorras.
• Avaldiste hindamine ja sulgude tasakaalu kontrollimine — virn salvestab avatavaid sulgusid ja kontrollib, kas need sulguvad õiges järjekorras.
• Veebilehitsejate tagasi-nupu ajalugu (lihtsustatud mudel).

Juhtuminäide: sulgude tasakaal

Lihtne algoritm sulgude kontrollimiseks:

 for each char in string:   if char is opening bracket:     push(char)   else if char is closing bracket:     if isEmpty(): return false     top = pop()     if top doesn't match char: return false return isEmpty() 

Kui lõpus on virn tühi, on kõik sulud õigesti paaritatud.

Rakenduse variandid ja implementatsioon

• Massiivi-põhine virn — lihtne ja kiire; sobib, kui maksimaalne suurus on teada või saab kasutada dünaamilist massiivi (ArrayList, std::vector), mis kasvab vajadusel.
• Lingitud nimekirja-põhine virn — iga element viitab eelmisele, push/pop on samuti O(1) ja ei vaja ümberpaigutamist; kasulik, kui ei tea eelnevalt elementide arvu.

Lihtne koodinäide (Python-laadne)

 stack = []  def push(x):   stack.append(x)  def pop():   if not stack:     raise IndexError("pop from empty stack")   return stack.pop()  def peek():   if not stack:     return None   return stack[-1] 

Virn on lihtne, ent väga kasulik andmestruktuur — selle LIFO käitumine teeb selle asendamatuks paljudes algoritmilistes ja praktilistes probleemides.

Otsing