Стэк

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

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

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

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

Стэк — сховішча мультымэдыйных матэрыялаў