Динамичка структура – стекови

Радио: Никола Зарић


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

Дефиниција стека

Стек (stackје структура која представља једну врсту линеарне листе са специфичном дисциплином приступа. Елемент се на стек може уметати или са њега уклањати само на једном крају линеарне структуре. Ово приступно место се зове врх (topстека, док се други крај зове дно (bottom) стека. Елемент се може увек ставити на стек, али је брисање могуће само ако стек има бар један елемент.
Уметањем елемента на стек на једином приступном крају, одмах иза претходног врха, формира се нови вршни елемент. С обзиром да се са стека уклања управо елемент са врха, а он је последњи елемент који је уметнут, за стек се каже да намеће LIFO (
Last In, First Out) дисциплину приступа – “последњи унутра, први напоље”. Према томе, елементи се уклањају са стека у обрнутом поретку од поретка њиховог уметања, па на њему најдуже остаје елемент који је први уметнут у празан стек (елемент на дну стека), а најкраће елемент на врху стека. На пример, ако се на празан стек редом стављају елементи ABCD и E, онда је на врху последњи унесени елемент E, а стање стека је приказано на слици 1a. Ако се, затим, изврше три операције брисања, елементи се уклањају у поретку ED и C, а нови врх постаје елемент B (слика 1b). Накнадне операције уметања елемената F иG дају стање као на слици 1c.

Слика 1. Стање стека
a) после пет операција уметања (
ABCD и E),
b) после три брисања и
c) после два уметања (
F и G)

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

Имплементација стека и операције са њим

Иако се стек веома често користи у рачунарским апликацијама, многи програмски језици немају стандардни уграђени тип стека. Због тога овај тип треба имплементирати симулацијом преко постојећих стандардних типова. Постоји неколико начина за имплементацију стека, а овде се разматрају секвенцијална и уланчана репрезентација.

Секвенцијална репрезентација стека

Пошто је стек линеарна структура која не захтева уметање и брисање на произвољној позицији, најприродније и најчешће се стек имплементира у виду вектора. Оваква имплементација захтева да стек буде хомогена структура. Иако концепт стека не ограничава његову величину, секвенцијална имплементација обично имплицира коначну дужину вектора, која се онда одређује по максималној очекиваној величини стека. Дно стека се веже за почетак вектора, а врх стека се динамички помера у опсегу индекса самог вектора. Неопходно је стално водити рачуна где се тренутно налази врх стека. У ту сврху се уводи показивач стека (stack pointer) где се памти индекс елемента вектора који тренутно представља врх стека реализованог овим вектором.
У неким имплементацијама дно стека је везано за почетну адресу вектора и стек расте ка вишим адресама, а у другим дно је везано за највишу адресу и стек расте надоле. У даљем разматрању секвенцијалне репрезентације претпоставља се да је стек представљен вектором 
S[1:n], да стек расте на горе и да целобројна показивач top[S] садржи индекс врха стека. У сваком тренутку стек се састоји од елемената S[1], …, S[top[S]], а top[S] представља разлику броја претходно извршених операција уметања и брисања, па тиме и тренутни број елемената стека.

Операције са стеком

Типичне операције са стеком су: креирање стека, уметање елемента, брисање елемента, читање вршног елемента без његовог уклањања и провера да ли је стек празан. Ове операције се прво приказују за имплементацију стека у виду вектора. Пошто сам вектор дозвољава произвољан приступ елементима, одговорност програмера је да успостави LIFO дисциплину приступа овако имплементираном стеку.
Операција креирања стека 
S максималне величине n, INIT-STACK(Sn), подразумева резервисање простора за низ дате величине. Како је стек на почетку празан, показивач стека се иницијализује на нулу.

INIT-STACK(ALLOCATE(S[1:n]) top[S] = 0

Пошто показивач стека показује и тренутни број елемената на стеку, испитивање да ли је стек S празан се врши позивом функције STACK-EMPTY(S) која враћа логичку вредност “true“ ако је показивач стека на нули (у почетном стању) или “false“ ако има вредност у опсегу индекса вектора. Стек је празан ако је од његовог креирања извршен једнак број уметања и брисања елемената.

STACK-EMPTY(S)if (top[S] = 0) then return true else
 return false
 end_if

Операција уметања новог елемента са вредношћу x на стек S, PUSH(Sx), прво проверава да ли је стек пун. Ако показивач стека указује да је и последња локација заузета, сигнализира се прекорачење капацитета стека и нови елемент не може да се уметне. У супротном, показивач стека се инкрементира тако да показује на прву следећу слободну локацију, па се тамо упише задата вредност x. На слици 2a је приказано стање стека са четири елемента, где је вршни елемент 1, а top = 4. На слици 2b је дато стање које је настало после извршавања две операције уметања PUSH(S, 3) и PUSH(S, 2). Врх стека сада представља последњи уметнути елемент 2, а на њега указује top = 6.

PUSH(S, x)if (top[S] = n) then ERROR(Overflow) else
 top[S] = top[S] + 1
 S[top[S]] = x
 end_if

Слика 2. Илустрација операција са стеком:
a) почетно стање,
b) стање после уметања вредности 3 и 2 и
c) стање после брисања

Функција POP(S) уклања и враћа вредност елемента са стека S, што представља инверзну операцију претходној операцији уметања. Прво се испита да ли је стек празан и ако јесте, враћа се одговарајући код. Ако стек није празан, очитава се елемент са врха стека и враћа као вредност функције, а стек се смањи декрементирањем показивача стека. Иако очитани елемент физички остаје у низу, он је логички уклоњен са стека, јер је показивач стека померен испод њега. На слици 2c је приказано стање стека пошто је примењена операција брисања POP(S) која је вратила вредност 2, а елемент 3 је изашао на врх.

POP(S) if (top[S] = 0) then return underflow else
 x = S[top[S]]
 top[S] = top[S] – 1
 return x
 end_if

Понекад је корисно очитати елемент који се налази на врху стека без његовог уклањања са стека. Ово се постиже функцијом TOP(S). За стек са слике 2c ова функција би вратила вредност 3, а стање стека би остало непромењено.

TOP(S) if (top[S] = 0) then return underflow else
 return S[top[S]]
 end_if

Ова операција се може добити и као комбинација две узастопне операције x = POP(S) и PUSH(Sx) које у збиру не мењају стање стека, а вредност вршног елемента остављају у променљивој x.

Иако појава оба случаја, “overflow“ и “underflow“, резултује неуспешним завршетком операције, постоји суштинска разлика између њих, а и реакција програма је другачија. Појава случаја “underflow“ увек представља корисну информацију за програмера да је стек празан на основу које се може усмеравати ток програма. Овај случај је логичке природе, везан за стек као апстрактни тип података и његова појава је независна од начина имплементације. Међутим, случај прекорачења капацитета стека “overflow“ је физичке природе и условљен је начином имплементације. Код векторског представљања стека, прекорачење је последица ограниченог резервисаног простора. Типична реакција на ову грешку је превремени завршетак програма са одговарајућом поруком. Уколико прекорачење стека није настало услед грешке у самом алгоритму (на пример, нека бесконачна петља у којој постоји операција уметања), ово се може решити повећањем димензије вектора S у којем је смештен стек и поновним стартовањем програма. Уколико у окружењу постоји могућност динамичке алокације и реалокације, онда је у програму могуће предвидети реакцију на овај случај чиме се избегава прекид програма.

Примене стекова

Рад са потпрограмима

Добра програмерска пракса захтева да се при пројектовању софтвера проблем разбија на модуле мање сложености – потпрограме. Они представљају логички заокружене скупове активности, а реализују се у виду процедура и функција. Размена улазних и излазних података између потпрограма и позивајуће целине врши се преко листе аргумената или глобалних променљивих. Модуларизација програма у виду потпрограма је незаменљива техника која доноси низ предности као што су: уштеда меморије, боља контрола сложености, лакше одржавање, већа разумљивост, олакшана организација и подела посла у пројектном тиму, итд.
Иако у зависности од система и имплементације постоје разлике у контролном механизму повезивања потпрограма, могу се издвојити неке уобичајене активности које се извршавају при позивању потпрограма и повратку из њега. Приликом позива потпрограма типичне су следеће акције:

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

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

Слика 3. Ток контроле при позивању потпрограма и при повратку из њих

За памћење повратне адресе се може наменити посебна локација у области самог потпрограма, где би се она сачувала пошто се пренесе као имплицитни аргумент при позиву. Тада се повратак реализује као индиректни скок преко садржаја ове локације. Међутим, овај начин намеће извесна ограничења која илуструје слика 4. Када се из главног програма позове потпрограм P1 запамти се адреса повратка a у његовој првој локацији. Ако касније потпрограм P1 позове самог себе, на истом месту се запамти адреса иза позива b чиме се уништава претходно запамћена адреса повратка у главни програм. Према томе, ова техника се не може користити код потпрогама који директно или индиректно позивају сами себе.
Са слике 3. се може закључити да се рестаурирање повратних адреса врши по обрнутом поретку њиховог памћења (адреса 
a sе прва памти, а последња рестаурира, док се адреса d последња памти, а прва рестаурира). Оваква LIFO дисциплина имплицира коришћење стека као природне структуре за памћење повратне адресе. Због тога се стек врло често и користи као најгенералнији начин који не намеће никаква ограничења на поредак позива.

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

Рекурзија

Природа многих алгоритама је таква да решавају полазни проблем тако што се парцијалним израчунавањем сложеност проблема смањи, па се опет користи исти алгоритам, али за простији проблем. Тако се кроз низ корака врши постепено свођење на проблем основне сложености за који постоји директно и коначно решење. Овакви алгоритми се називају рекурзивним алгоритмима, а имплементирају се преко потпрограма који директно или индиректно позивају сами себе – рекурзивним потпрограмима.
Рекурзивни потпрограми су врло важна и корисна техника, поготово за одређену класу проблема са инхерентно рекурзивном природом. У неким случајевима рекурзија следи директно из дефиниције као у случају факторијелне функције

n! = n*(n – 1)! za n >= 1, 0! = 1

или Фибоначијевих бројева

F(n) = F(n-1) + F(n-2) za n >= 2, F(0) = F(1) = 1 .

Типичну класу алгоритама погодну за рекурзивно решавање представљају и алгоритми типа “подели-и-победи” (divide-and-conquer), где се проблем обично дели на половину основне величине, па су потребна два рекурзивна позива. Тада се до решења долази на елегантан и разумљив начин и уз релативно мало програмерског напора. Док се за неке рекурзивне проблеме може наћи и једноставно итеративно решење (као у два горња случаја), постоје и проблеми за које је то веома тешко урадити.
Илустративан пример рекурзивног алгоритма је решење класичног проблема Ханојских кула. У овом проблему постоје три штапа A, B и C (слика 5a), а на штапу A се налази 
n различитих дискова поређаних по величини тако да је највећи на дну, а најмањи на врху. Потребно је да се дискови пребаце са штапа A на штап C користећи штап B као помоћни. Притом се са штапа може уклањати само диск са врха, а ни у једном тренутку се не дозвољава да мањи диск буде испод већег диска на било којем штапу.

Слика 5. Решавање проблема Ханојских кула

До решења се долази индуктивним путем. Ако постоји само један диск, он се одмах пребаци са A на C. У случају два диска, горњи се пребаци на B, доњи на C, а онда се диск са B пребаци на C. На основу почетних корака може да се генерализује алгоритам за произвољно n:

1. пребаци се n – 1 дискова са A на B користећи C као помоћни (слика 5b),
2. пребаци се диск n са A на C (слика 5c),
3. пребаци се n – 1 дискова са B на C користећи A као помоћни (слика 5d).

Како се решење за n дискова своди на решење за – 1 дискова одмах се закључује се да је рекурзивни алгоритам најприроднији. Притом се рекурзија завршава са n = 1. Овај врло концизан алгоритам се реализује у виду процедуре HANOI-R са четири улазна аргумента: број дискова n, ознака изворног from, одредишног to и помоћног aux штапа.

HANOI-R(n, from, to, aux)if (n = 1) then PRINT(Prenesi disk 1 sa from na to) return
 end_if
 HANOI-R(n - 1, from, aux, to)
 PRINT(Prenesi disk n sa from na to)
 HANOI-R(n - 1, aux, to, from)
 return

Рекурзивни потпрограми намећу неке специфичне захтеве при извршавању који се не јављају код нерекурзивних програма. Пошто рекурзивни потпрограм може бити позван из неког другог модула или из себе самог (једном или више пута), претходно је показано да повратна адреса мора да се чува на стеку. Поред тога, пошто сваки рекурзивни позив представља целину за себе која касније треба да буде настављена, пре наредног рекурзивног позива мора бити сачуван комплетан контекст који касније треба рестаурирати. Овај контекст чине вредности локалних и привремених променљивих, као и формалних аргумената у тренутку непосредно пре позива. Због редоследа позивања и повратка сви ови елементи, заједно са повратном адресом која одговара првој инструкцији иза позива, памте се на стеку у виду структуре која се назива активациони запис. Према томе, сваки активациони запис одговара једном позиву рекурзивног потпрограма и памти се на стеку у тренутку кад се тај позив привремено прекида због наредног рекурзивног позива. Због тога се при сваком повратку из рекурзивног потпрограма са врха стека уклања један активациони запис, користи за рестаурацију контекста претходног позива и врши скок на повратну адресу.
Међутим, употреба рекурзије поред свих погодности често има и један недостатак који се огледа у смањеној ефикасности у односу на итеративно решење истог проблема. Ово је последица режијског времена које се утроши на рекурзивне позиве и простора на стеку који је за то потребан. Типичан пример за то је рекурзивно налажење Фибоначи-јевог броја. Овај алгоритам, који је једноставан и природан јер излази из саме дефиниције, нажалост, има експоненцијалну сложеност 
O(cn) (где је c = 1.618… “златни пресек”) због огромног мултиплицирања броја позива, за разлику од итеративног решења до којег се, такође, доста једноставно долази, а има линеарну сложеност O(n).

Елиминација и симулација рекурзије

Неки програмски језици (на пример, FORTRAN, COBOL, неки асемблерски језици) не дозвољавају рекурзију. Како се многи проблеми могу веома елегантно и лако решити применом рекурзије, од интереса је познавати технику која би коректан и проверен рекурзивни алгоритам на стандардан начин превела у суштински исто, али нерекурзивно решење тако што би се рекурзија симулирала итеративним средствима.

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

Из наведених разлога очигледна је важност постојања неког стандардног поступка за конверзију рекурзивног потпрограма у нерекурзивни. На основу познавања активности које се дешавају приликом извршавања рекурзивног потпрограма на машини, може да се предложи техника која симулира ове радње. Зато се ова техника заснива на експлицитном памћењу релевантних информација на корисничком стеку пре рекурзивног позива и уклањању са њега при повратку. У случају рекурзивне процедуре овај поступак се начелно састоји од следећих корака:

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

Затим се сваки рекурзивни позив у потпрограму замени програмским сегментом који ради следеће акције:

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

Поред тога, свака инструкција повратка из потпрограма у коду (return) треба да се замени кодом који обавља следеће активности:

  • ако је стек празан, онда обавља нормалан повратак у рутину која је извршила позив,
  • ако стек није празан, врши се повратак у исти потпрограм на следећи начин:
  • уколико постоје излазни аргументи, њихове текуће вредности се придруже одговарајућим променљивима у оквиру записа на врху стека,
  • са стека се уклања идентификација повратне адресе,
  • затим се са стека уклања читав активациони запис, па се врате и ажурирају сви аргументи и локалне променљиве, чиме се враћа контекст претходног позива,
  • на основу идентификације повратне адресе врши се безуслован скок на одговарајућу лабелу која стоји непосредно иза претходног позива.

Ако је рекурзивни потпрограм функција, једине разлике у односу на процедуру су:
при повратку, израчуна се вредност функције и стави на стек, непосредно пре скока на повратну адресу,
при позиву, лабела за повратну адресу се ставља на инструкцију која повлачи вредност функције са стека, а затим се ова вредност може користити на жељени начин.
Пошто је нерекурзивна верзија задржала из рекурзивне све инструкције осим рекурзивних позива који се сада остварају експлицитним контролним механизмом, фунционалност је остала потпуно иста. Ова верзија најчешће омогућава и додатне оптимизације које зависе од конкретног случаја, а које допиносе даљем побољшању ефикасности. У неким случајевима се може чак и потпуно елиминисати потреба за стеком.
Примењујући управо ова правила рекурзивно решење за проблем Ханојских кула може се претворити у нерекурзивно уз коришћење стека довољне величине 
v. Пошто нема локалних променљивих, активациони запис ar се састоји од 5 елемената: четири аргумента (nfromtoaux) и идентификације повратне адресе ret (1- повратак иза првог позива и 2 – повратак иза другог позива). Нерекурзивна варијанта HANOI-NR1, приказана на следећој страни, има исте аргументе као и рекурзивна.

Пажљивом анализом ове нерекурзивне варијанте уочава се да се она може упростити. Од суштинског значаја је то да се други рекурзивни позив налази на самом крају процедуре. Зато, по повратку из овог позива, нема потребе за рестаурацијом контекста испред овог позива, јер се са њим ништа не ради. Због тога претходни контекст није ни потребно сачувати на стеку и касније га опет враћати, већ је довољно само припремити аргументе позива и директно скочити на почетак процедуре. Ово је стандардни поступак уклањања рекурзивног позива који се налази на самом крају потпрограма (tail recursion). Тако нестаје и потреба за повратном адресом l2. Пошто је остала само једна могућа повратна адреса, l1, није више неопходно да се она чува у активационом запису на стеку. Уместо тога, кад год се активациони запис успешно уклони са стека, може се одмах скочити на адресу иза првог позива l1, а када је стек празан врши се повратак из потпрограма. Овим се добија процедура HANOI-NR2 која је значајно упрошћена.
Могуће је и даље упрошћење кода. Инструкције од
 l1 до краја представљају изоловани сегмент који се може преместити на место одакле се скаче на њега и тиме избећи инструкција goto l1. Могу се, такође, избацити и скокови на почетну адресу (goto l) i тако боље структурирати код. На тај начин се долази до коначне нерекурзивне верзије HANOI-NR3, која је значајно упрошћена у односу на прву нерекурзивну верзију HANOI-NR1.

HANOI-NR1(n, from, to, aux)INIT-STACK(S, v)l: if (n = 1) then PRINT(Prenesi disk 1 sa from na to)
 if (STACK-EMPTY(S)) then
 return
 end_if
 ar = POP(S)
 (n, from, to, aux)  if (ar.ret = 1) then
 goto l1
 else
 goto l2
 end_if
 end_if
 ar.ret = 1
 ar  PUSH(S, ar)
 n = n – 1
 to  aux
 goto l
 l1: PRINT(Prenesi disk n sa from na to)
 ar.ret = 2
 ar  PUSH(S, ar)
 n = n – 1
 from  aux
 goto l
 l2: if (STACK-EMPTY(S)) then
 return
 end_if
 ar = POP(S)
 (n, from, to, aux)  if (ar.ret = 1) then
 goto l1
 else
 goto l2
 end_if

функција HANOI-NR2:

HANOI-NR2(nfromtoaux)INIT-STACK(S, v)lif (n = 1) thenPRINT(Prenesi disk 1 sa from na to)
if (STACK-EMPTY(S)) then
return
end_if
ar = POP(S)
(nfromtoaux) <- ar
goto l1
end_if
ar <- (nfromtoaux)
PUSH(Sar)
n = n – 1
to <-> aux
goto l
l1: PRINT(Prenesi disk n sa from na to)
n = n – 1
from <-> aux
goto l

функција HANOI-NR3:

HANOI-NR3(n, from, to, aux)INIT-STACK(S, v)loopwhile (n != 1) do // izvrsava se dok je n razlicito od 1
 ar  PUSH(S, ar)
 n = n - 1
 to  aux
 end_while
 PRINT(Prenesi disk 1 sa from na to)
 if (STACK-EMPTY(S)) then
 return
 end_if
 ar = POP(S)
 (n, from, to, aux)  PRINT(Prenesi disk n sa from na to)
 n = n – 1
 from  aux
 end_loop

Advertisements

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се / Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се / Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се / Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се / Промени )

Повезивање са %s