Стек

Из пројекта Википедија

Једноставна репрезентација стека

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

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

[уреди] Апстрактни тип података

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

[уреди] Операције

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

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

record Node {

    data // Подаци који се чувају у чвору
    next // показивач на следећи чвор; null за последњи чвор
 }

 record Stack {
     Node stackPointer   // показује на врх стека; null за празан стек
 }

 function push(Stack stack, Element element) { // гура елемент на стек
     new(newNode)            // алоцира меморију за нови чвор
     newNode.data   := element
     newNode.next   := stack.stackPointer
     stack.stackPointer := newNode
 }

 function pop(Stack stack) { // повећава показивач на стек, и враћа чвор са врха
     // Овде такође може да се провери да ли је stack.stackPointer null
     // Ако је тако, може се вратити грешка
     node := stack.stackPointer
     stack.stackPointer := node.next
     element := node.data      
     return element
 }

 function top(Stack stack) { // враћа чвор са врха
     return stack.stackPointer.data
 }

 function length(Stack stack) { // враћа количину чворова из стека
     length := 0
     node := stack.stackPointer
     while node not null {
         length := length + 1
         node := node.next
     }
     return length
 }

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

[уреди] Имплементација

Типична меморијска захтевност стека од 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 операција копира податке са стека, а затим увећава показивач. Свака процедура позвана унутар програма складишти своје повратне информације (жуто) и локалне податке (у другим бојама) гурајући их на стек. Оваква имплементација стека је изразито честа, али је рањива на нападе прекорачење бафера (buffer overflow) нападе.

Типичан стек је део у меморији рачунара са фиксираним почетком, и променљивом величином. На почетку, величина стека је нула. Показивач на стек, обично у виду хардверског регистра, показује на последу искоришћену адресу на стеку; када је стек величине нула, показивач показује на почетак стека.

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

• 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]), или тако што расту слева на десно, па највиши постаје најдеснији. Ове визуализације могу бити независне од стварне имплементација стека у меморији. Ово значи да ће 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. У језику LISP нема потребе да се имплементира стек, јер су функције push и pop доступне за сваку листу. Adobe PostScript је такође дизајниран око стека кога програмер директно може да види, и да њиме манипулише.

[уреди] Примене

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

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

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

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

1 2 + 4 * 3 +

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

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

Ко на следећи начин (Стек је исписан након што је Операција одиграна):

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

[уреди] Референце

1. ^ Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984
2. ^ http://java.sun.com/javase/6/docs/api/java/util/Stack.html
3. ^ http://java.sun.com/javase/6/docs/api/java/util/Vector.html