Стек (структура от данни)

Стек с функциите Push (добави) и Pop (извади)

Стекът е линейна структура от данни в информатиката, в която обработката на информация става само от едната страна наречена връх. Дъното не е и не трябва да е достъпно. Стековете са базирани на принципа „последен влязъл пръв излязъл“ (от английски: LIFO – Last In First Out)

Стек произлиза от английската дума Stack означаваща куп, купчина, накуп и т.н.

Начин на работа

Стекът теоретично може да събере безкраен брой обекти, но на практика само краен брой, ограничен от количеството памет. Обектите могат да се поставят и да се четат (вадят) единствено от горната страна на стека. Стекът има три операции:

• push (добавяне) – поставя нов обект върху стека
• pop или pull (изваждане/изтегляне) – вади най-горния (последно добавения) елемент от стека
• peek (надникване) – показва най-горния елемент от стека без да го изважда

История

Тази структура за първи път е предложена през 1955 и патентована през 1957 от немския компютърен специалист Фридрих Лудвиг Бауер и Клаус Самелсон

Имплементация

На C++:

#include <stdexcept>
 
// Modelliert einen Stapel fixer Größe, der Elemente des Typs T enthält.
// Diese Implementierung ist jener in Mikroprozessoren ähnlich, jedoch für
// dynamisch wachsende Stapel speicherineffizient - verwende besser deque<T>.
template<typename T>
class Stack {
    int size;       // големина на стека
    int top;        // позиция на пойнтъра към стека
    T* values;      // масив със стойности
 
public:
    Stack(int size)
        : size(size), top(0), values( new T[size] ) {
    }
    ~Stack() {
        delete [] values;
    }
 
    void push(T value) {    // записва нов елемент в стека
        if (top >= size)
            throw std::overflow_error("Стекът е пълен");
        values[top] = value;
        ++top;
    }
 
    T pop() {               // вади най-горния елемент от стека
        if (top == 0)
            throw std::underflow_error("Стекът е празен");
        --top;
        return values[top];
    }
};

В повечето API-та стековете са имплементирани като свързани списъци. Стандартната библиотека на C++ предлага темплейта deque<T> с методите push_back() и pop_back(). В Java тази функционалност се предоставя от класа java.util.LinkedList