Отваря главното меню

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

Емблема за пояснителна страница Вижте пояснителната страница за други значения на Стек.

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

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

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

Начин на работаРедактиране

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

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

ИсторияРедактиране

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

ИмплементацияРедактиране

На 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

ИзточнициРедактиране

  1. Bauer, Goos: Informatik, Eine einführende Übersicht, Erster Teil. Springer-Verlag, Berlin 1982, стр. 222.“