Стэк

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі
Перайсьці да: навігацыі, пошуку

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

Глядзіце таксама[рэдагаваць | рэдагаваць крыніцу]

Commons-logo.svg  Стэксховішча мультымэдыйных матэрыялаў