Стек (апстрактни тип података)

У рачунарству, стек је привремени апстрактни тип података и структура података, базиран на принципу ЛИФО (LIFO - Last In First Out - последњи који улази, први излази). Стекови се у великој мери користе на свим нивоима модерног рачунарског система.

Стек-машина је рачунарски систем који привремене податке складишти првенствено у стековима, уместо у хардверским регистрима.

Апстрактни тип података

Као апстрактни тип података, стек се састоји од чворова, и има две основне операције: push и pop. Push ставља дати чвор на врх стека, остављајући претходне чворове испод. Pop уклања и враћа чвор који је тренутно на врху. Стек се може схватити као неколико тањира постављених један на други. Ако желимо да додамо нови тањир, стављамо га на врх, а уколико нам је потребан тањир, узимамо онај са врха. Да бисмо скинули тањир са дна, претходно морамо да скинемо све тањире који се налазе на њему. Само нам је тањир са врха доступан, док су остали прекривени. Кад се на врх дода нови тањир, он постаје врх стека. Ова метафора илуструје два важна принципа: један је принцип ЛИФО (енгл. Last in, first out - последњи који улази, први излази), а други је да је само тањир са врха видљив, па да би се видео трећи тањир, први и други морају прво да се склоне.

Операције

Код модерних рачунарских језика, стек се обично имплементира са додатним операцијама, а не само са "push" и "pop". Често је могуће да се дужина стека врати као параметар. Још једна помоћна операција је top^[1] (такође позната као peek и peak) може да врати тренутни елемент са врха, без уклањања са стека.

Следи псеудокод за додавање и уклањање чворова са стека, као и за функције које одређују дужину, и top функцију. У овим функцијама се користи null, да реферише на дно стека.

struktura Cvor {
    podaci; // Подаци који се чувају у чвору''
    sledeci; // показивач на следећи чвор; null за последњи чвор
};

struktura Stek {
    Cvor pokazivacNaVrh; // показује на врх стека; null за празан стек
};

funkcija push(Stek stek, Element element)
{
    // гура елемент на стек
    noviCvor = novi Cvor; // алоцира меморију за нови чвор
    noviCvor.podaci = element;
    noviCvor.sledeci = stek.pokazivacNaVrh;
    stek.pokazivacNaVrh = noviCvor;
}

funkcija pop(Stek stek)
{
    // повећава показивач на стек, и враћа чвор са врха''
    // Овде такође може да се провери да ли је stack.stackPointer null''
    // Ако је тако, може се вратити грешка''
    cvor = stek.pokazivacNaVrh;
    stek.pokazivacNaVrh = stek.sledeci;
    element = cvor.podaci;
    vrati element;
}

funkcija vrh(Stek stek)
{
    // враћа чвор са врха
    vrati stek.pokazivacNaVrh.podaci;
}

funkcija duzina(Stek stek)
{
    // враћа број чворова из стека
    duzina = 0;
    cvor = stek.pokazivacNaVrh;
    dok cvor nije null {
       duzina = duzina+1;
       cvor = cvor.next;
    }
    vrati duzina;
}

Као што се може видети, ове функције прослеђују стек и чворове као параметре и повратне вредности. Чворови у овој имплементацији користе показиваче. Стек може бити имплементиран и као линеарна секција меморије (на пример у низу), у ком случају се заглавља функција не мењају, већ само њихова унутрашњост.

Имплементација

Типична меморијска захтевност стека од n елемената је O(n). Типична верменска захтевност операција је O(1). Стек се лако користи помоћу динамичког низа, или повезане листе.

Стандардна шаблонска библиотека C++ програмског језика садржи шаблонску класу stack, која је ограничена само на push/pop операције. Јавина библиотека садржи Stack^[2] класу која је специјализација класе Vector^[3] што неки сматрају великом грешком у дизајну, јер наследна get() метода из класе Vector игнорише ЛИФО ограничења класе Stack.

Следи једноставан пример стека са описаним операцијама у програмском језику Питон. Стек нема никакав тип провере грешака.

class Stack:
    def __init__(self):
        self.stack_pointer = None
       
    def push(self, element):
        self.stack_pointer = Node(element, self.stack_pointer)
       
    def pop(self):
        (e, self.stack_pointer) = (self.stack_pointer.element, self.stack_pointer.next)
        return e

    def peek(self):
        return self.stack_pointer.element

    def __len__(self):
        i = 0
        sp = self.stack_pointer
        while sp:
            i += 1
            sp = sp.next
        return i

class Node:
    def __init__(self, element=None, next=None):
        self.element = element
        self.next = next

if __name__ == '__main__':
    # small use example
    s = Stack()
    [s.push(i) for i in xrange(10)]
    print [s.pop() for i in xrange(len(s))]

Ово иначе није потребно, јер Питон подржава pop и append функције за листе. Међутим, једноставна синтакса овог језика га чини погодним за пример.

Повезане структуре података

Апстрактни тип података и структура података типа ФИФО (FIFO - First In First Out - први који улази, први излази) је ред. На пример, промена стека у ред у алгоритму за претрагу може да промени алгоритам из претраге у дубину у претрагу у ширину.

Хардверски стекови

Најчешћа употреба стекова на нивоу архитектуре је као средство за алоцирање и приступање меморији.

Основна архитектура стека

Типичан стек складишти локалне податке и информације о позиву за угнежђене процедуре. Овај стек расте надоле од почетка. Показивач на стек показује на тренутни врх стека. Операција Push умањује показивач, и копира податке на стек; операција pop враћа податке са стека, а затим показивач показује на нови врх стека. Свака процедура позвана унутар програма складишти своје повратне информације (жуто) и локалне податке (у другим бојама) гурајући их на стек. Оваква имплементација стека је изразито честа, али је рањива на нападе прекорачења бафера. Типичан стек је део у меморији рачунара са фиксираним почетком, и променљивом величином. На почетку, величина стека је нула. Показивач на стек, обично у виду хардверског регистра, показује на последњу искоришћену адресу на стеку; када је стек величине нула, показивач показује на почетак стека.

Две операције применљиве на све стекове су:

push операција, у којој се предмет поставља на локацију на коју показује показивач на стек, а адреса у показивачу се прилагођава за величину тог предмета;
pop или pull операција: предмет на тренутној локацији на коју показује показивач се уклања, а адреса у показивачу се прилагођава за величину тог предмета

Постоји много варијација основног принципа стек операција. Сваки стек има фиксирану локацију у меморији, на којој почиње. Како се подаци додају на стек, стек показивач се помера, како би осликавао тренутно стање стека, које се шири од његовог почетка (може да се шири ка горе или ка доле, зависно од имплементације).

На пример, стек може да почне на меморијској локацији 1000, и да се шири ка нижим адресама, и у том случају се нови подаци смештају на адресама испод 1000, и показивач на стек се умањује сваки пут кад се нови податак дода. Кад се податак уклони са стека, показивач на стек се увећава.

Показивач на стек може да показује на почетак стека, или на ограничени опсег изнад или испод почетка (у зависности од тога у ком смеру сте красте); међутим, он не може да пређе почетак стека. Другим речима, ако је почетак стека на адреси 1000, и стек расте надоле (према адресама 999, 998, и тако даље), показивач на стек не сме никад да буде увећан изнад 1000 (на 1001, 1002, и тако даље). Ако pop операција доведе до тога да показивач на стек пређе преко почетка стека, долази до поткорачења стека (stack underflow). Ако push операција доведе до тога да се показивач на стек увећа или умањи преко максималне величине стека, долази до прекорачења стека (stack overflow).

Нека окружења се у великој мери ослањају на стекове могу да пружају и додате операције, на пример:

-{Dup(licate)]-: врх стека се дуплира, тако што се нови примерак тог податка постави на стек, тако да оригинал остане испод њега.
Peek: врх стека се враћа, али се показивач на стек не мења, као ни величина стека (што значи да податак остаје на стеку). Ова операције се такође често назива top.
Swap или exchange: два елемента најближа врху стека мењају место.
Rotate: n елемената стека најближих врху се премештају на стеку, тако што се ротирају. На пример, ако је n=3, подаци 1, 2, и 3 на стеку се премештају на позиције 2, 3, и 1 редом. Могуће су многе варијације ове операције, а најчешће су ротирање улево (left rotate) и ротирање удесно (right rotate).

Стекови се обично замишљају тако што расту од дна ка врху (као у реалним примерима (на пример дискови на штапу)), или са врхом стека на фиксираној позицији (види слику), налик на оквир код пиштоља ([1] Архивирано на сајту Wayback Machine (27. септембар 2007)), или тако што расту слева надесно, па највиши постаје најдеснији. Ове визуелизације могу бити независне од стварне имплементација стека у меморији. Ово значи да ће right rotate померити први елемент на трећу позицију, други елемент на прву, а трећи на другу позицију. Следе две еквивалентне визуелизације овог процеса:

јабука                                    краставац
банана                 ==right rotate==>  јабука
краставац                                 банана

јабука банана краставац  ==right rotate==>  краставац јабука банана

Стек је у рачунарима обично представљен блоком меморијских ћелија, са дном на фиксираној локацији, а показивач на стек чува адресу тренутног врха стека. Изрази врх и дно се користе невезано за стварну имплементацију стека (код које стек може да расте и надоле, и нагоре).

Гурање елемента на стек мења вредност показивача на стек за величину елемента (било умањујући, или повећавајући га, у зависности од смера у коме стек расте у меморији), тако да показује на следећу ћелију, и копира нови елемент на стек. Опет, у зависности од специфичне имплементације, на крају push операције, показивач може да показује на прву слободну локацију на стеку, или на сам врх стека. Ако показивач показује на тренутни врх, он ће бити померен пре него што се нови елемент дода на стек; ако показује на прву слободну локацију, биће померен након што се нови елемент гурне на стек.

Хардверска подршка

Многи процесори имају регистре који могу да се користе као показивачи на стек. Неки, попут Интеловог x86, имају посебне инструкције које имплицитно користе регистар посвећен томе да буде показивач на стек. Други, као што је DEC PDP-11 и Моторолина фамилија 68000 имају адресне модове који омогућавају коришћење било ког скупа регистара као показиваче на стек. Интел 80x87 серија нумеричких копроцесора има скуп регистара којима се може приступити било као показивачима на стек, било као нумерисаним регистрима. НЕки микроконтролери, на пример PIC, имају стек фиксиране дубине, коме се не може директно приступити.

Неки микропроцесори такође имплементирају стек директно у хардверу:

Computer Cowboys MuP21
Harris RTX line
Novix NC4016

Многи микропроцесори базирани на стеку су коришћени да имплементирају програмски језик Forth на нивоу микрокода. Стекови су такође коришћени као основа неких мејнфремова и минирачунара. Такве машине су називане стек машинама, а најпознатији је Burroughs B5000.

Софтверска подршка

У апликационим програмима писаним у вишим програмским језицима, стек се може ефикасно применити било помоћу низова било помоћу повезаних листаs. У језику Лисп нема потребе да се имплементира стек, јер су функције push и pop доступне за сваку листу. Adobe PostScript је такође дизајниран око стека кога програмер директно може да види, и да њиме манипулише.

Примене

Стекови се стално користе у свету рачунарства.

Израчунавање израза и парсирање синтаксе

Калкулатори који користе обрнуту пољску нотацију користе стек структуре да чувају вредности. Изрази могу бити записивани у префиксној, постфиксној или инфиксној нотацији. За конверзију из једне у другу форму израза је потребан стек. Многи компајлери користе стек за парсирање синтаксе израза, програмске блокове, и слично пре превођења у код ниског нивоа. Већина програмских језика су контекст-слободни језици што им омогућава да буду парсирани машинама базираним на стеку. Природни језици су контекст осетљиви језици, и сами стекови нису довољни да интерпретирају њихово значење.

На пример, израз: ((1 + 2) * 4) + 3 може бити записан на следећи начин у постфиксној нотацији уз предност да нису потребна правила предности и заграде:

1 2 + 4 * 3 +

Израз се израчунава слева надесно коришћењем стека:

push кад се дође до операнда
pop два операнда и њихово рачунање, кад се дође до операције праћено push резултат.

Следи илустрација описаног алгоритма за дати пример:

Улаз	Операција	Стек
1	Push операнд	1
2	Push операнд	1, 2
+	Сабирање и Pop последња два операнда и Push резултат	3
4	Push операнд	3, 4
*	Множење и Pop последња два операнда и Push резултат	12
3	Push операнд	12, 3
+	Сабирање и Pop последња два операнда и Push резултат	15

Коначни резултат, 15, стоји на врху стека након рачунања.

Извори

^ Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984
^ Sun.com „Стек“ (језик: енглески)
^ „Стек“ (језик: енглески)

Спољашње везе

[1] Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984

[2] Sun.com „Стек“ (језик: енглески)

[3] „Стек“ (језик: енглески)

[1]

[2]

[3]