Стек
Stack
В тази тема ще разгледаме абстрактната структура данни Стек (Stack) и нейна конкретна имплементация чрез свързан списък. Ще видим какви операции поддържа тя и с каква сложност се изпълнява всяка от тях. В края на темата сме предоставили пълна имплементация като шаблонен клас, както и код, с който можете да тествате ваша такава.
Стек или Stack на английски е третата от най-базовите абстрактни структури, които ще срещате отново и отново (другите две са Списък и Опашка). И тази структура има широко приложение в компютрите - тя е основна част от изпълнението на програмите (програмния стек), както и участва в различни алгоритми (например намиране на изпъкнала обвивка).
Какво е стек?
! | Такъв ред на вкарване и изкарване на елементи на английски се нарича LIFO (last in, first out). |
Понякога може да нямате нито една изпрана тениска и да се опитате да вземете такава от празния шкаф, в който ще се получи проблем (наричан stack underrun). Затова винаги, преди да бръкнете за тениска, трябва да проверявате дали има поне една такава!
Другият възможен проблем е, да станете добри състезатели и да получавате толкова много тениски от TopCoder, Google Code Jam, HackerCup, CodeIT и т.н. всяка година, че шкафчето с тениските да се препълни (познато като stack overflow). Ако помните, за това вече говорихме в темата за Рекурсия. Всъщност езиците за програмиране реализират рекурсия именно използвайки стек за менажиране на паметта, съответно проблемът при нея идва от проблема на стека, а не обратното.
Приложения
Стекът се ползва в един от юбер-популярните алгоритми в графи - Търсене в Дълбочина. Употребата му там, обаче, в повечето случаи е невидима за нас, тъй като се ползва рекурсия. В редица други алгоритми, обаче, се налага да се ползва директно стек. Пример за такъв е този за намиране на Изпъкнала Обвивка или алгоритмите за намиране на Силно-свързани Компоненти. Понякога, когато задачата има специфична структура на решенията, стек се ползва и за оптимизация на Динамично Оптимиране.Поддържани типове
Тъй като елементите се пазят в реда, в който постъпват в структурата (и в частност - не се пазят сортирани), за тях няма изискване какви да са. Могат да са стандартни типове (напримерint
или double
), STL-ски структури (например string
), дефинирани от вас структури, а също и други шаблонни класове - включително други стекове!Адаптери
! | Много често структури данни се имплементират, ползвайки други структури данни (и евентуално някаква допълнителна информация). Когато нямаме нови данни, а просто предоставяме друг интерфейс (както можем да направим в случая), новата структура данни се нарича адаптер (adaptor) на структурата данни, която ползваме. Например в STL опашката е адаптер на структурата Deque. |
O(1)
, ползвайки Динамичен Масив. Всъщност функционалностите на стека са подмножество на тези на вектора, съответно и имплементацията е по-кратка и до голяма степен сходна.Друг начин, по който може да се имплементира стек би било използвайки свързан списък - наистина, тъй като ни трябва достъп до един единствен елемент, можем да ползваме дори по-проста имплементация (едносвързан списък) и указател към "най-горния" елемент.
Тъй като имплементацията като адаптер би трябвало да е тривиална, в тази тема ще покажем как сами да менажираме данните си. Ще направим това отново чрез Свързан Списък, както направихме и в темата за Опашка. По-нататък сме показали имплементация чрез динамичен масив в темата за Двустранна Опашка, която комбинира в едно Вектор, Стек и Опашка - тя поддържа със същите сложности операциите на всяка от тях!
Имплементация
Стекът поддържа относително малко на брой фукнции, което го прави подходящ само за ограничен набор от задачи. За сметка на това той е изключително бърз в справянето с тях - всички те са константни. Тук ще покажем основните от тях.Данни
Тъй като ще ползваме Свързан Списък за да имплементираме опашката, трябва да дефинираме структурата на всяко "звено" от списъка.typedef int DataType;
struct Element {
DataType data;
Element* next;
Element(const DataType& value) {
data = value;
next = nullptr;
}
};
Структура
Самият стек се нуждае от съвсем малко неща - само брояч на елементите и указател към най-горния:struct Stack {
int size;
Element* head;
Stack() {
size = 0;
head = nullptr;
}
};
empty()
Проверката дали стекът е празен става тривиално, проверявайки дали броят елементи в него е нула:bool empty(Stack& q) {
return q.size == 0;
}
push(value)
Добавянето на нов елемент със стойност value на върха на стека става заО(1)
и може да се направи по следния начин:
void push(Stack& q, const DataType& value) {
Element* element = new Element(value);
element->next = q.head;
q.head = element;
q.size++;
}
pop()
Премахването най-горния елемент на стека става също заO(1)
по следния начин:
void pop(Stack& q) {
assert(q.size > 0);
Element* element = q.head;
q.head = q.head->next;
q.size--;
delete element;
}
top()
Достъпът до най-горния елемент на стека отново става заO(1)
, и става учудващо лесно:
DataType& top(Stack& q) {
assert(q.size > 0);
return q.head->data;
}
clear()
Изчистването на стека е еквивалентно на изчистването на свързания списък:void clear(Stack& q) {
while (q.head != nullptr) {
Element* element = q.head;
q.head = q.head->next;
delete element;
}
q.size = 0;
q.head = nullptr;
}
Цялостна имплементация
Цялостна имплементация и тестове може да намерите тук: Stack.h | StackTester.cppПримерна задача
Даден ви е низ от скоби - тоест низ, съставен от символите {'(', ')', '{', '}', '[', ']'}. Пита се дали зададеният низ е валиден низ от скоби - тоест ако се поставят числа и аритметични знаци между скобите би могло да се получи валиден аритметичен израз.
Примерни валидни скобни низове са
Примерни валидни скобни низове са
""
, "()()"
, и "({{[]([])}}())[[{}]]"
, докато невалидни са "(("
, ")("
, "([})"
, "({)}"
, и "(){}[()]]"
.Има различни наивни решения с варираща сложност: от експоненциална, до по-приемливи от сорта на
O(N3)
и O(N2)
, където N е броят скоби. Оптималната сложност, обаче, е O(N)
и можем да постигнем, използвайки стек.Идеята е следната. Обхождаме низа от ляво надясно. Всеки път, когато срещнем отваряща скоба (тоест една от {'(', '{', '['}) я пъхаме в стека. Когато срещнем затваряща скоба, проверяваме каква отваряща имаме на върха на стека. Ако съвпада по тип (тоест е '(' ако сме срещнали затваряща ')', '{' ако сме срещнали '}' или '[', ако сме срещнали ']') премахваме тази от върха на стека. В противен случай казваме, че низът е невалиден. Допълнително трябва да проверим и дали след обхождане на целия низ стекът е останал празен (за да не пропуснем случаи от вида на
"(("
). Ако след обхождане на целия стринг стекът е празен и не сме срещнали двойка несъвпадащи скоби (например "(}"
), то казваме, че низът е валиден.Откъм сложност, всяка отваряща скоба сме добавили в стека веднъж за
O(1)
, а с всяка затваряще сме премахнали по един елемент от върха му, отново за O(1)
. Така цялата сложност е O(N)
.Допълнителни материали
- Свързан Списък (www.informatika.bg)
- Опашка (www.informatika.bg)
- Двустранна Опашка (www.informatika.bg)
- Stack (abstract data type) (en.wikipedia.org)
- STL Stack (www.cplusplus.com)
За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.
натиснете Enter и изпратете Вашето предложение.
Страницата е посетена 13892 пъти.