Špageti stek

Špageti stek (ili kaktus stek) u informatici predstavlja N-arno drvo (strukturu podataka) u kom deca čvora imaju pokazivače na roditelja (ali ne i obrnuto). Kada se ovi pokazivači prate od lista do korena stabla, struktura koja se dobije izgleda kao povezana lista. Analogno sa povezanom listom koja ima samo jedan pokazivač, koji se najčešće zove „sledeći“ ili „veza“, ignorišući to da svaki roditelj može imati još dece (koji nisu dostupni stalno, jer ne postoje pokazivače na dole, od roditelja ka deci).

Špageti stek sa označenim „aktivnim“ stekom

Špageti stek strukture nastaju u sitaucijama kada se dinamički stavlja i skida sa steka u toku izvršavanja procesa.

Na primer, kompajler za jezik kao sto je C stvara špageti stek jer otvara i zatvara okvire koje predstavljaju prostor bloka. Kada se otvara novi prostor bloka, okvir se stavlja na stek. Kada se naiđe na zatvorenu vitičastu zagradu, prostor bloka se brise i okvir se skida sa steka. Ali taj okvir se pamti, a ne uništava se. I naravno pamti pokazivač na svog roditelja i tako dalje.

Slična struktura podataka se pojavljuje u nepovezanim stablima.

Upotreba u programskim jezicima

Termin špageti stek je usko povezan sa implementacijom programskih jezika koji podržavaju nastavak (nastavak je apstraktno predstavljanje kontrolnog stanja programa). Špageti stek se takođe koriste za implementaciju stvarnog run-time steka koji sadrži promenljive veze i ostale osobine okruženja. Ako je nastavak izvrsavanja programa podržan, onda lokalne promenljive ne smeju biti uništene kada ta funkcija završi sa radom, jer se očekuje da nakon ponovnog ulaska u tu funkciju sve promenljive budu sačuvane zajedno sa stekom, koji čuva adresu povratka, kako bi funkcija mogla da vrati povratnu vrednost. Kako bi se rešio ovaj problem, stek okviri se mogu dinamički alocirati u špageti stek strukturi, i biti jednostavno ostavljeni za brisanje ako više nema potrebe za njihovim korišćenjem.

Primeri jezika koji koriste špageti stekove su:

• Felix
• Rust
• Smalltalk
• Scheme