Структура даних "стек"

Стек (stack) – це послідовність, елементи якої отримують за принципом “останній увійшов, перший вийшов” (LIFO, Last In First Out). Це означає, що ми матимемо доступ тільки до останнього доданого елемента.

На відміну від списків, ми не можемо отримати доступ до довільного елемента стека. Ми можемо тільки додавати або видаляти елементи за допомогою спеціальних методів. Ми не можемо дізнатись про належність певного об'єкта до стека, як у списків. Крім того, по стеку не можна ітеруватись. Для того щоб розуміти, чому на стек накладаються такі обмеження, давайте подивимося на те, як він працює і як використовується.

Аналогія, що найчастіше зустрічається, для пояснення стека — стос тарілок. Незалежно від того, скільки тарілок у стосі, ми завжди можемо зняти верхню. Чисті тарілки так само кладуться на верх стопки, і ми завжди будемо першими брати ту тарілку, яка була покладена останньою.

Якщо ми покладемо, наприклад, червону тарілку, потім синю, а потім зелену, то спочатку потрібно буде зняти зелену, потім синю, і, нарешті, червону. Головне, що потрібно запам’ятати – тарілки завжди ставляться і на верх стопки. Коли хтось бере тарілку, він також знімає її згори. Виходить, що тарілки розбираються в порядку, зворотному тому, в якому ставилися.

Тепер, коли ми розуміємо, як працює стек, розглянемо основні операції зі стеком.

• push(item) — додати елемент item на верхівку стека
• pop() — видалити елемент з верхівки стека і повернути його
• peek() — дізнатись (повернути) елемент з верхівку стека

В Python немає спеціального типу даних або ж готової структури яка б реалізовувала стек. Але за допомогою списків можна легко реалізувати стек самостійно.

Будемо вважати останній елемент списка вершиною стека. Тоді щоб додати елемент на стек достатньо виконати:

>>> stack = []
>>> stack.append(1)
>>> stack.append(2)
>>> stack.append('top')
>>> stack
[1, 2, 'top']
>>>

Дізнатись елемент на верхівці стека:

>>> on_top = stack[-1]
>>> on_top
'top'
>>> stack
[1, 2, 'top']
>>>

Щоб видалити значення з верхівки стека скористаємось методом pop():

>>> val = stack.pop()
>>> val
'top'
>>> stack.pop()
2
>>> stack.pop()
1
>>> stack.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list
>>>