Відкрити головне меню

Стек (англ. stack — «стос, стіс») в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стека та був введений в стек останнім.

Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стека — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї).

Зміст

Операції зі стекомРедагувати

 
Виконання операцій push та pop.
  • push («заштовхнути елемент»): елемент додається в стек та розміщується в його верхівці. Розмір стека збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow).
  • pop («виштовхнути елемент»): отримує елемент з верхівки стека. При цьому він видаляється зі стека і його місце в верхівці стека займає наступний за ним відповідно до правила LIFO, а розмір стека зменшується на одиницю. При намаганні «виштовхнути» елемент з вже пустого стека, відбувається ситуація «незаповненість» стека (англ. stack underflow).

Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.

Додаткові операції (присутні не у всіх реалізаціях стека):

  • isEmpty: перевірка наявності елементів в стека; результат: істина (true), коли стек порожній.
  • isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
  • clear: звільнити стек (видалити усі елементи).
  • top: отримати верхній елемент (без виштовхування).
  • size: отримати розмір (кількість елементів) стека.
  • swap: поміняти два верхніх елементи місцями.

Організація в пам'яті комп'ютераРедагувати

Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стека.

Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.

Приклади застосуванняРедагувати

Калькулятори, де запис виразів організовано у вигляді інверсної польської нотації, використовують стек для збереження даних обчислень.

Існують «стеко-орієнтовані» мови програмування (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;
	}
};

Див. такожРедагувати