Лекції з інформатики - стек (stack)

Загальна інформація

Стек (stack) - це динамічна структура даних з послідовним доступом. Доступ до елементів стека здійснюється наступним чином, елементи з стека можна діставати тільки в порядку, зворотному порядку додавання їх в стек.

Прикладами стеків можуть служити:

  1. звичайна дитяча пірамідка: колечко, яке було надіто раніше, не можна зняти, не знявши маленьке, яке було надіто пізніше;
  2. залізничний тупик: вагон не можна вигнати з глухого кута, що не вигнавши попередньо вагон, який був загнаний пізніше;
  3. труба з одним запаяним кінцем, куди поміщають різнокольорові барила.

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

Робота стека організована за принципом LIFO (Last In First Out) - останнім прийшов, першим пішов.

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

Реалізація стека на C ++

Наведемо приклад реалізації необмеженого стека цілих чисел заснованого на однозв'язного списку.

Реалізація шаблону "Стек"

Шаблон - це заготовка для класу, параметризрвані клас. Наш шаблон "Стек" матиме один параметр - тип даних з яких буде складатися стек. Використовуючи шаблон легко оголосити стеки абсолютно довільних типів даних:

Оскільки ми вже маємо готовий клас "стек цілих чисел", то його легко переробити в шаблон "Стек".