Стек

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(N³) и O(N²), където N е броят скоби. Оптималната сложност, обаче, е O(N) и можем да постигнем, използвайки стек.

Идеята е следната. Обхождаме низа от ляво надясно. Всеки път, когато срещнем отваряща скоба (тоест една от {'(', '{', '['}) я пъхаме в стека. Когато срещнем затваряща скоба, проверяваме каква отваряща имаме на върха на стека. Ако съвпада по тип (тоест е '(' ако сме срещнали затваряща ')', '{' ако сме срещнали '}' или '[', ако сме срещнали ']') премахваме тази от върха на стека. В противен случай казваме, че низът е невалиден. Допълнително трябва да проверим и дали след обхождане на целия низ стекът е останал празен (за да не пропуснем случаи от вида на "(("). Ако след обхождане на целия стринг стекът е празен и не сме срещнали двойка несъвпадащи скоби (например "(}"), то казваме, че низът е валиден.

Откъм сложност, всяка отваряща скоба сме добавили в стека веднъж за O(1), а с всяка затваряще сме премахнали по един елемент от върха му, отново за O(1). Така цялата сложност е O(N).

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 12218 пъти.