Стек

Стек — абстрактный тип данных формализующий принцип LIFO.

Основные операции:

• push(a) — поместить a на стек.
• pop() — вернуть последние элемент из стека и удалить его из стека.
• Дополнительные операции
• top() — вернуть последний элемент из стека без удаления.
• len()— вернуть количество элементов в стеке.
• isEmpty() — возвращает True если стек пустой.

Операция pop вернёт сначала последний добавленный через push элемент, затем предпоследний и так до того как стек опустеет.

Когда стек пустой операции pop и push могут либо возвращать какое-то особое значение (например, None в Python), либо генерировать исключение. Обычно, лучше явно сообщать о проблеме или неодназначностях и генерировать исключение.

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 3. Рекурсия. Стек

Ссылки на эту заметку

• Абстрактный тип данных (Abstract data type)
• Отношение между структурами данных и абстрактными типами данных

Эта заметка на GitHub

Обсудить на форуме