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

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

---

Стек с функциите 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

Източници

Тази статия, свързана с информатика, все още е мъниче. Помогнете на Уикипедия, като я редактирате и разширите.