Стеком називається такий спосіб зберігання даних, при якому елемент, записаний в сховище даних, останнім завжди витягується першим (дисципліна LIFO - «last in - first out»). Під час вилучення елемента відбувається його видалення зі стека.
Розглянемо найпростіший приклад використання стека. Припустимо, що є рядок, що складається з одних лише відкривають і закривають дужок. Потрібно визначити, чи є вона правильним Дужковий виразом (тобто для кожної відкриває дужки повинна знайтися закриває). Заведемо масив і змінну для зберігання номера останнього значимого елемента в масиві (тобто вершини стека), в який при проході по рядку будемо складати всі відкриваються дужки (зі збільшенням номера вершини на 1), а при зустрічі з закриває будемо видаляти відповідну відкриває (попросту зменшувати номер вершини стека). Якщо виявиться, що «прийшла» закриває дужка, а стек порожній (тобто номер вершини дорівнює 0), то вираз помилково. Це ж можна сказати і в разі, коли рядок закінчилася, а стік не порожній.
Очевидно, що для реалізації такого стека масив використовувати не обов'язково, досить зберігати в деякій змінній лише число відкривають дужок. При надходженні закриває дужки з цієї змінної віднімається 1. Помилка виникає, якщо значення змінної стало негативним, або при досягненні кінця рядка вона не дорівнює нулю.
Для даних більш складного виду стек можна організувати за допомогою однонаправленої некольцевого списку. Щоб покласти елемент в стек, потрібно додати його в початок списку, щоб витягти з стека - отримати дані першого елемента, після чого видалити його зі списку.
Будь-яка реалізація стека повинна містити наступні процедури і функції:
procedure InitStack - ініціалізація стека;
procedure Push (d: tData) - покласти елемент в стек;
procedure Pop (var d: tData) - витягти елемент з вершини стека;
function NotEmpty: boolean - перевірка стека на порожнечу;
Черга відрізняється від стека тим, що останній прийшов в неї елемент буде витягнуто останнім, а перший - першим ( «FIFO»). За допомогою списків її можна організувати таким чином: будемо зберігати не тільки покажчик на «голову» списку, а й на «хвіст»; додавати будемо в «хвіст», а витягувати - з «голови».
Будь-яка реалізація черги (не обов'язково за допомогою списків) повинна «уміти» виконувати такі дії:
procedure InitQueue - ініціалізація черги;
procedure AddQueue (d: tData) - поставити елемент в чергу;
procedure SubQueue (var d: tData) - витягти елемент з черги;
function NotEmpty: boolean - перевірка черзі на порожнечу;