Стэк
Стэк — (у праграмаваньні) структура зьвестак, што арганізаваная згодна прынцыпу 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. Зрух на адзін элемэнт не зьмяняе стэка.
Рэалізацыі стэка
[рэдагаваць | рэдагаваць крыніцу]На нізкім узроўні стэкі рэалізаваныя як шэраг пранумараваных рэгістраў або як азначаны абсяг памяці (дзе зьмешчаны элемэнты стэка) і адмысловай зьменнай (ці рэгістра) дзе захоўваецца індэкс ці адрас вяршыні стэка. На высокім узроўні рэалізацыя стэка можа быць зроблена праз масіў ці сьпіс.
Праз масіў
[рэдагаваць | рэдагаваць крыніцу]Для захаваньня элемэнтаў стэка рэзэрвуецца масіў пэўнага памеру і зьменная, дзе будзе зьмешчаны індэкс бягучага элемэнта.
![]() | Прыведзеныя тут альгарытмы і кавалкі коду напісаныя на wikicode (анг.), які прапануецца ў якасьці псэўдакоду для напісаньня артыкулаў. |
record stack { var object[1..N] data; var int pointer = 0; }
Апэрацыі push і pop зьмяняюць індэкс — павялічваюць ці зьмяншаюць.
function stack.push( object element ) { data[++pointer] = element; } function stack.pop() { return data[pointer--]; }
Прыклад ужываньня
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 (форт) цалкам пабудаваная на стэках. Шмат якія рэкурсіўныя альгарытмы могуць быць ператвораныя ў просты цыкл, пры гэтым стан ітэрацыяў звычайна захоўваецца ў стэцы.
Глядзіце таксама
[рэдагаваць | рэдагаваць крыніцу]Вонкавыя спасылкі
[рэдагаваць | рэдагаваць крыніцу] Стэк — сховішча мультымэдыйных матэрыялаў