Стек — Вікіпедія

Ця стаття містить перелік посилань, але походження тверджень у ній залишається незрозумілим через практично повну відсутність внутрішньотекстових джерел-виносок. Будь ласка, допоможіть поліпшити цю статтю, перетворивши джерела з переліку посилань на джерела-виноски у самому тексті статті.

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

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

Операції зі стеком[ред. | ред. код]

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

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

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

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

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

Організація в пам'яті комп'ютера[ред. | ред. код]

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

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

Приклади застосування[ред. | ред. код]

Калькулятори (стекові машини^[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; 	} }; 

Див. також[ред. | ред. код]

• Черга
• Черга з пріоритетом
• Список структур даних
• Forth, PostScript — поширені стекові мови програмування.

Література[ред. | ред. код]

• Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. ISBN 978-617-684-239-2. {{cite book}}: Cite має пустий невідомий параметр: |1= (довідка)

Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її.