Стек (структура от данни)
- Вижте пояснителната страница за други значения на Стек.
Стекът е линейна структура от данни в информатиката, в която обработката на информация става само от едната страна наречена връх. Дъното не е и не трябва да е достъпно. Стековете са базирани на принципа „последен влязъл пръв излязъл“ (от английски: LIFO – Last 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
Източници редактиране
- ↑ Bauer, Goos: Informatik, Eine einführende Übersicht, Erster Teil. Springer-Verlag, Berlin 1982, стр. 222.“
