Стэк

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.

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

Зьмест 1 Апэрацыі 2 Рэалізацыі стэка 2.1 Праз масіў 2.2 Празь сьпіс 3 Прымяненьні стэка 4 Глядзі таксама

[рэдагаваць] Апэрацыі

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

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

[рэдагаваць] Глядзі таксама

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