02.11.2017: Структура от данни стек. Реализация на последователното и свързаното представяне на стек. Приложения на стек.
Стекът е контейнер от обекти, които биват вкарвани и изкарвани на принципа LIFO (last in first out) == FILO. Обектите могат да бъдат вкарвани и изкарвани по всяко време, но се изкарва само този, който последно е бил вкаран. Името „стек“ произлиза от идеята за диспенсер за чинии с пружина (stack of plates in a spring loaded cafeteria plate dispenser), а оттам идва и името на метода за вкарване на елемент в стек – push, т.е. push down (a plate), и pop – pop up (a plate). Поради тази причина може да срещнете стандартния стек и като pushdown стек.
Използваме масив, за най-просто може да е статичен, а може и разширяващ се.
- Проверяваме, дали има място в масива за нов елемент
- Ако не – разширяваме стека
- Добавяме новият елемент
- Увеличаваме индекса
- Проверяваме, дали стекът е празен
- Ако да – приключваме / хвърляме exception
- Връщаме стойността на най-горния елемент
- Намаляме индекса
Използва се свързан списък с клетки, структура с две полета: указател към елемент от същия тип и поле за стойност.
- Правим клетка, която да държи новата стойност
- Добавяме новата клетка към свързания списък
- Проверяваме, дали стекът е празен
- Ако да – приключваме / хвърляме exception
- Взимаме стойността от клетката на върха на стека.
- Премахваме клетката от върха на стека.
- Връщаме стойността.
По време на изпълнение на програма, runtime средата поддържа програмен стек. Обикновено намиращ се във високите адреси напаметта, стекът расте в посока към нулевия адрес за (x86). Регистър, наричащ се „стек указател“ пази върха на стека и променя състоянието си при всяко push-ване или pop-ване. Наборът от стойности push-нати за едно извикване на функция се нарича „стекова рамка“, която съдържа поне върнатата стойност това извикване. При всяко такова извикване адресът на връщане и информация за средата от където е направено се запазва на стека. Вече извиканата функция създава нова стекова рамка.
Стековият указател съдържа най-малкият възможен за елемент от стека адрес, така че валидните адреси са тези по-големи или равни на неговия. Стековото дъно е най-малкият валиден адрес на стека. Когато стекът се инициализира, стековият указател сочи дъното. Границата на стека е най-малкият валиден адрес на стека. Ако стековият указател стане по-малък от границата, тогава настъпва stack overflow, обикновено при бездънна рекурсия.
- Напишете темплейтен клас за стек използващ свързаното представяне.
- Maximum Element
- Game of two stacks
- Simple Text Editor