Лекції з інформатики - стек (stack)
Загальна інформація
Стек (stack) - це динамічна структура даних з послідовним доступом. Доступ до елементів стека здійснюється наступним чином, елементи з стека можна діставати тільки в порядку, зворотному порядку додавання їх в стек.
Прикладами стеків можуть служити:
- звичайна дитяча пірамідка: колечко, яке було надіто раніше, не можна зняти, не знявши маленьке, яке було надіто пізніше;
- залізничний тупик: вагон не можна вигнати з глухого кута, що не вигнавши попередньо вагон, який був загнаний пізніше;
- труба з одним запаяним кінцем, куди поміщають різнокольорові барила.
Останній приклад найбільшою мірою відповідає програмістському поняттю стека: заглядаючи в трубу, ми можемо бачити, що діжок в трубі немає, або бачити колір верхнього барильця, але не можемо бачити, чи є барила під верхнім, скільки їх і будь вони квітів.
Робота стека організована за принципом LIFO (Last In First Out) - останнім прийшов, першим пішов.
Елемент стека, який в даний момент можна взяти, тобто верхній, називається вершиною стека. Якщо число елементів в стеку не може перевищувати певної величини, то стек називають обмеженим. а максимальне число елементів у ньому - глибиною стека.
Реалізація стека на C ++
Наведемо приклад реалізації необмеженого стека цілих чисел заснованого на однозв'язного списку.
Реалізація шаблону "Стек"
Шаблон - це заготовка для класу, параметризрвані клас. Наш шаблон "Стек" матиме один параметр - тип даних з яких буде складатися стек. Використовуючи шаблон легко оголосити стеки абсолютно довільних типів даних:
Оскільки ми вже маємо готовий клас "стек цілих чисел", то його легко переробити в шаблон "Стек".