Стэк

Стэк – (у праграмаваньні) структура дадзеных, што арганізавана згодна прынцыпу LIFO (last in – first out): апошні прыйшоў – першы выйшаў. Прыклад такой арганізацыі: талеркі складзеныя адна на адну. Пакласьці новую на стос можна толькі зьверху, узяць таксама можна толькі зьверху - акурат апошнюю пакладзеную. Таму па-беларуску можа варта называць гэтую структуру дадзеных - стос, а ня стэк?. Элемэнт, што знаходзіцца зьверху, называецца top element – вяршыня, галоўны ці бягучы элемэнт.

Апэрацыі

Асноўныя апэрацыі са стэкам:

push: пакласьці элемэнт на верх стэка. Колькасьць элемэнтаў у стэке павялічваецца на 1. Калі памер стэка абмежаваны, гэтая апэрацыя можа выклікаць памылку stack overflow – перапаўненьне стэка.
pop: выдаліць верхні элемэнт. Колькасьць элемэнтаў памяньшаецца на 1. На вяршыні стэка апынаецца той элемэнт, які дагэтуль быў другім (калі такі быў). Калі ў стэке няма элемэнтаў, гэтая апэрацыя выклікае памылку stack underflow – спусташэньне стэка.

Дадатковыя апэрацыі (прысутнічаюць не ўва ўсіх рэалізацыях стэка):

isEmpty: праверка, ці ёсьць элемэнты ў стэке. Рэзультат: ісьціна, калі ў стэке няма элемэнтаў.
isFull: праверка, ці запоўнены стэк. Рэзультат: ісьціна, калі ў стэк больш нельга дадаць ніводнага элемэнта.
clear: ачысьціць стэк (выдаліць усе элемэнты).
top: атрымаць верхні элемэнт.
size: атрымаць памер (колькасьць элемэнтаў) стэка.
swap: памяняць два верхніх элемэнта месцамі.
rotate(N): цыклічны зрух N верхніх элемэнтаў. Магчымы правы зрух і левы зрух.

Правы зрух зьмяшчае верхні элемэнт на N-ю пазыцыю, другі - на першую, трэці - на другую і г.д. - як стрэлка гадзіньніка. Прыклад правага зруху на 4 элемэнта: аа бб бб вв вв ===> гг гг аа дд дд ... ... Левы зрух зьмяшчае верхні (першы) элемент на месца другога, другі - на месца трэцьцяга, ... а N-ы элемэнт апынаецца на вяршыне (становіцца першым) - супраць хады стрэлкі гадзіньніка. Прыклад левага зруху на 4 элемэнта: аа гг бб аа вв ===> бб гг вв дд дд ... ... Зрух на два элемэнта роўны апэрацыі swap. Зрух на адзін элемэнт не зьмяняе стэка.

Рэалізацыі стэка

На нізкім узроўні стэкі рэалізаваныя як шэраг пранумэраваных рэгістраў або як азначаны абсяг памяці (дзе зьмешчаны элемэнты стэка) і адмысловай зьменнай (ці рэгістра) дзе захоўваецца індэкс ці адрас вяршыні стэка. На высокім узроўні рэалізацыя стэка можа быць зроблена праз масіў ці сьпіс.

Праз масіў

Для захаваньня элемэнтаў стэка рэзэрвуецца масіў пэўнага памеру і зьменная, дзе будзе зьмешчаны індэкс бягучага элемэнта.

record stack { var object^* data; var int pointer = 0; }

Апэрацыі push і pop зьмяняюць індэкс - павялічваюць ці зьмяншаюць. function stack.push( object element ) { data^* = element; } function stack.pop() { return data^*; }

Прыклад ужываньня var int a; var stack st = new stack(); st.push(3); st.push(4); a = st.pop(); // a == 4

Празь сьпіс

У гэтым выпадку выкарыстоўваецца структура, што зьмяшчае элемэнт стэка і працяг стэка - спасылку на такую ж структуру. Гэта нагадвае сьпіс у мове праграмаваньня Lisp (лісп). record stack { object top; stack rest; }

Апэрацыя push стварае новы элемэнт сьпісу, які будзе новай вяршыняй, функцыя top вяртае бягучую вяршыню, pop дае спасылку на стэк бязь верхняга элемэнта: function stack.push( object element ) { var stack newStack = new stack(); newStack.top = element; newStack.rest = this; // працяг новага стэка - гэта бягучы стэк return newStack; } function stack.top() { return top; } function stack.pop() { return rest; }

Прыклад ужываньня var int a; var stack st = new stack(); st = st.push(3); st = st.push(4); a = st.top(); // a == 4 st = st.pop();

Прымяненьні стэка

Стэк ужываецца ў альгарытмах, што рэалізуюць зваротную польскую натацыю. Мовы праграмаваньня выкарыстоўваюць стэкі для захоўваньня інфармацыі аб тым, якая функцыя/працэдура была выклікана, а таксама стэкі для перадачы парамэтраў. Мова праграмаваньня Forth (форт) цалкам пабудаваная на стэках. Шмат якія рэкурсіўныя альгарытмы могуць быць пераствораны ў просты цыкл, пры гэтым стан ітэрацый звычайна захоўваецца ў стэке.

Глядзі таксама

Дрэва, Масіў, Сьпіс, Чарга