This is an old revision of the document!


Шта је стек?

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

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

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

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

{{:200px-data_stack.svg.png|

Операције

Код модерних рачунарских језика, стек се обично имплементира са додатним операцијама, а не само са “push” и “pop”. Често је могуће да се дужина стека врати као параметар. Још једна помоћна операција је top 1)
може да врати тренутни елемент са врха, без да га уклони са стека.

Следи псеудокод за додавање и уклањање чворова са стека, као и за функције које одређују дужину, и 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;
}

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

Literatura:

1) такође позната као peek и peak
 
stek.struktura_podataka.1323378058.txt.gz · Last modified: 2011/12/08 22:00 by simona.vujic
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki