Mis on virn programminduses kontekstis ja kuidas seda rakendatakse tarkvaraarenduses?

Programmeerimise kontekstis, virn (Stack) — see on andmetüüp, mis töötab LIFO (Last-In, First-Out, "viimases sisse, esimeses välja") põhimõttel:

Põhitegevused:

• Push: elemendi lisamine virna otsa:
• Pop: elemendi eemaldamine ja tagastamine:
• Top/Peek: elemendi tagastamine virna ülaosast ilma eemaldamata:
• IsEmpty: kas virn on tühi:

Rakendused tarkvaraarenduses:

• Funktsioonide täitmine: Call Stack kasutatakse funktsioonikutsumiste haldamiseks. Funktsiooni kutsumisel paigutatakse selle parameetrid, kohalikud muutujad ja tagastamise aadress virna. Funktsiooni lõpetamisel eemaldatakse need andmed:
• Väljendite töötlemine: Kasutatakse aritmeetiliste väljendite analüüsimiseks ja arvutamiseks, näiteks infix märgistusest postfix märgistuseni ja selle arvutamiseks:
• Tühistamine (Undo/Redo): Tekstiredaktorites ja teistes rakendustes võib virna kasutada muudatuste järjesta salvestamiseks tühistamise ja uuesti tegemise funktsioonide jaoks:
• Graafide/puu läbimine: Näiteks sügavusotsing (DFS) teostatakse, kasutades virna, et hoida külastatavaid tippe:
• Mälu haldamine: Kohalikud muutujad paiknevad tavaliselt virna mälus:
• Rekursiooni haldamine: Rekursiivsed kutsed kasutavad sisemiselt virna, et hoida iga kutsungi olekut:

Näide virna kasutamisest sulgude tasakaalu kontrollimiseks:

def is_balanced(expression):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in expression:
        if char in mapping.values():  # avamise sulg
            stack.append(char)
        elif char in mapping.keys():  # sulgemise sulg
            if not stack or mapping[char] != stack.pop(): # virn on tühi või sobimatu
                return False
    return not stack # virn peab olema tühjend lõpuks