Стек - це спеціальний тип списку, в якому все вставки і видалення виконуються тільки на одному кінці, званому вершиною (top). Стеки також іноді називають "магазинами", а в англомовній літературі для позначення стеків ще використовується абревіатура 'LIFO (last-in-first-out - останній увійшов - перший вийшов). Інтуїтивними моделями стека можуть служити колода карт на столі при грі в покер, книги, складені в стопку, або стос тарілок на полиці буфета; у всіх цих моделях взяти можна тільки верхній предмет, а додати новий об'єкт можна, тільки поклавши його на верхній. Абстрактні типи даних сімейства STACK (Стек) зазвичай використовують наступні п'ять операторів.
1. MAKENULL (S). Робить стек S порожнім.
2. TOP (S). Повертає елемент з вершини стека S. Зазвичай вершина стека ідентифікується позицією 1, тоді TOP (S) можна записати в термінах загальних операторів списку як RETRIEVE (FIRST (S), S).
3. POP (S). Видаляє елемент з вершини стека (виштовхує з стека), в термінах операторів списку цей оператор можна записати як DELETE (FIRST (S), S).
4. PUSH (; c, S). Вставляє елемент ж в вершину стека S (заштовхує елемент в стек). Елемент, який раніше перебував у вершині стека, стає елементом, наступним за вершиною, і т.д. У термінах загальних операторів списку даний оператор можна записати як INSERT (.r, FIRST (S), S).
5. EMPTY (S). Ця функція повертає значення true (істина), якщо стек S порожній, і значення false (брехня) в іншому випадку.
Лістинг 2.7. Програма, що реалізує дії прального сімволаі символу-убійциJ
while noteolndo begin