Шпагети стек

Шпагети стек са означеним „активним“ стеком

Шпагети стек (или кактус стек) у информатици представља Н-арно дрво (структуру података) у ком деца чвора имају показиваче на родитеља (али не и обрнуто). Када се ови показивачи прате од листа до корена стабла, структура која се добије изгледа као повезана листа. Аналогно са повезаном листом која има само један показивач, који се најчешће зове „следећи“ или „веза“, игноришући то да сваки родитељ може имати још деце (који нису доступни стално, јер не постоје показиваче на доле, од родитеља ка деци).

Шпагети стек структуре настају у ситауцијама када се динамички ставља и скида са стека у току извршавања процеса.

На пример, компајлер за језик као сто је C ствара шпагети стек јер отвара и затвара оквире које представљају простор блока. Када се отвара нови простор блока, оквир се ставља на стек. Када се наиђе на затворену витичасту заграду, простор блока се брисе и оквир се скида са стека. Али тај оквир се памти, а не уништава се. I наравно памти показивач на свог родитеља и тако даље.

Слична структура података се појављује у неповезаним стаблима.

Употреба у програмским језицима

Термин шпагети стек је уско повезан са имплементацијом програмских језика који подржавају наставак (наставак је апстрактно представљање контролног стања програма). Шпагети стек се такође користе за имплементацију стварног рун-тиме стека који садржи променљиве везе и остале особине окружења. Ако је наставак изврсавања програма подржан, онда локалне променљиве не смеју бити уништене када та функција заврши са радом, јер се очекује да након поновног уласка у ту функцију све променљиве буду сачуване заједно са стеком, који чува адресу повратка, како би функција могла да врати повратну вредност. Како би се решио овај проблем, стек оквири се могу динамички алоцирати у шпагети стек структури, и бити једноставно остављени за брисање ако више нема потребе за њиховим коришћењем.

Примери језика који користе шпагети стекове су:

• Фелиx
• Руст
• Смаллталк
• Сцхеме