мини|200п|десно|Једноставна репрезентација стека У рачунарству, стек је привремени апстрактни тип података и структура података, базиран на принципу ЛИФО (-{LIFO - Last In First Out}- - последњи који улази, први излази). Стекови се у великој мери користе на свим нивоима модерног рачунарског система.
Стек-машина је рачунарски систем који привремене податке складишти првенствено у стековима, уместо у хардверским регистрима.
Апстрактни тип података Као апстрактни тип података, стек се састоји од чворова, и има две основне операције: -{push}- и -{pop}-. -{Push}- ставља дати чвор на врх стека, остављајући претходне чворове испод. Pop уклања и враћа чвор који је тренутно на врху. Стек се може схватити као неколико тањира постављених један на други. Ако желимо да додамо нови тањир, стављамо га на врх, а уколико нам је потребан тањир, узимамо онај са врха. Да бисмо скинули тањир са дна, претходно морамо да скинемо све тањире који се налазе на њему. Само нам је тањир са врха доступан, док су остали прекривени. Кад се на врх дода нови тањир, он постаје врх стека. Ова метафора илуструје два важна принципа: један је принцип ЛИФО ( - последњи који улази, први излази), а други је да је само тањир са врха видљив, па да би се видео трећи тањир, први и други морају прво да се склоне.
Операције Код модерних рачунарских језика, стек се обично имплементира са додатним операцијама, а не само са "push" и "pop". Често је могуће да се дужина стека врати као параметар. Још једна помоћна операција је top-{Horowitz, Ellis: "Fundamentals of Data Structures in Pascal", page 67. Computer Science Press, 1984}- (такође позната као -{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}-Sun.com „Стек“ класу која је специјализација класе -{Vector}-„Стек“ што неки сматрају великом грешком у дизајну, јер наследна -{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}- - први који улази, први излази) је ред. На пример, промена стека у ред у алгоритму за претрагу може да промени алгоритам из претраге у дубину у претрагу у ширину.
Хардверски стекови Најчешћа употреба стекова на нивоу архитектуре је као средство за алоцирање и приступање меморији.
Основна архитектура стека мини|350п|десно|Типичан стек Типичан стек складишти локалне податке и информације о позиву за угнежђене процедуре. Овај стек расте надоле од почетка. Показивач на стек показује на тренутни врх стека. Операција -{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}-).
Стекови се обично замишљају тако што расту од дна ка врху (као у реалним примерима (на пример дискови на штапу)), или са врхом стека на фиксираној позицији (види слику), налик на оквир код пиштоља ( ), или тако што расту слева надесно, па највиши постаје најдеснији. Ове визуелизације могу бити независне од стварне имплементација стека у меморији. Ово значи да ће -{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}- је такође дизајниран око стека кога програмер директно може да види, и да њиме манипулише.
Примене Стекови се стално користе у свету рачунарства.
Израчунавање израза и парсирање синтаксе