Стэк

**Стэк** — (у праграмаваньні) структура зьвестак, што арганізаваная згодна прынцыпу 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*[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 (форт) цалкам пабудаваная на стэках. Шмат якія рэкурсіўныя альгарытмы могуць быць ператвораныя ў просты цыкл, пры гэтым стан ітэрацыяў звычайна захоўваецца ў стэцы.

## Глядзіце таксама
* Дрэва
* Масіў
* Сьпіс
* Чарга

## Вонкавыя спасылкі

Катэгорыя:Структуры зьвестак