Стек
З Вікіпедії, вільної енциклопедії
З Вікіпедії, вільної енциклопедії
Стек (англ. stack — «стос, стіс») в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Усі операції (наприклад, видалення елемента) в стеку можна проводити тільки з одним елементом, який міститься на верхівці стека та був уведений у стек останнім.
![]() | Ця стаття містить перелік посилань, але походження тверджень у ній залишається незрозумілим через практично повну відсутність внутрішньотекстових джерел-виносок. |
Стек можна уявити як стопку тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку. Інша назва стека — «магазин», за аналогією з принципом роботи магазина в автоматичній зброї.
Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стека.
Додаткові операції (присутні не у всіх реалізаціях стека):
Стек можна організувати як масив або множину комірок у певній ділянці пам'яті комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування елемента в стек збільшує адресу вказівника, виштовхування елемента зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз міститься верхівка стека.
Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стека, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.
Калькулятори (стекові машини[en]), де запис виразів організовано в інверсній польській нотації, використовують стек для збереження даних обчислень. Прикладом використання стекової машини є програма UNIX dc.
Існують «стеко-орієнтовані» мови програмування (Forth, PostScript), які використовують стек як базову структуру даних при виконанні багатьох операцій (арифметичних, логічних, вводу-виводу тощо).
Стеко-орієнтованими є деякі з віртуальних машин, наприклад віртуальна машина Java.
Компілятори мов програмування можуть використовувати стек для передавання параметрів у процесі виклику підпрограм, процедур та функцій (іншим поширеним способом передавання є регістри). Спеціалізований стек використовується також для збереження адрес повернення з підпрограм.
На мовах програмування високого рівня, стек можна реалізувати за допомогою масиву та додаткової змінної. Для зберігання елементів стека резервується масив S[1..n] певного розміру та додаткова змінна top[S], яка буде зберігати індекс верхівки стека.
Операції push та pop тоді можна записати так (без перевірки на переповнення та «незаповненість»):
PUSH (S, x)
1 top[S] := top[S] + 1 // збільшення індексу на 1
2 S[top[S]] := x // запис нового елемента у верхівку стека
POP (S)
1 top[S] := top[S] - 1 // зменшення індексу на 1
2 return S[top[S] + 1] // повернення колишньої верхівки стека
Приклад реалізації стека на мові C++ за допомогою масиву:
template <class T>
class StackOnArray
{
private:
int top;
int size;
T* arr;
void resizeAndCopy()
{
T* valueArr = new T[size];
for (int i = 0; i < top; ++i)
{
valueArr[i] = arr[i];
}
delete[] arr;
arr = valueArr;
}
public:
StackOnArray()
{
top = 0;
size = 10;
arr = new T[size];
}
~StackOnArray()
{
delete[] arr;
}
void push(T value)
{
if (top >= size)
{
size *= 2;
resizeAndCopy();
}
arr[top] = value;
++top;
}
public:
T pop()
{
T result = T();
if (!isEmpty())
{
--top;
result = arr[top];
if (top <= size / 3)
{
size = size * 2 / 3;
resizeAndCopy();
}
}
return result;
}
bool isEmpty()
{
return top == 0;
}
int getSize()
{
return size;
}
};