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

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

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

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

Стек произлиза от английската дума 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.“