Подразделы

Другие разделы

Дата и время

01/04/2025 14:47:13

Авторизация

Зарегистрироваться
Восстановить пароль

Линейные АТД

Список Массив и Строка Стек Очередь Двухсторонняя очередь Очередь с приоритетами Множество Словарь

Стек

Выделяют специальные ограниченные по допустимым операциям разновидности списка, которые часто используются в алгоритмах.

Стеком называют такой список, в котором можно удалить только последний элемент, а новый элемент добавить только в его конец. Последний элемент называют вершиной стека, поскольку стек обычно изображают на рисунках как стопку книг. Принципом работы стека является "последним вошел, первым вышел" ("last-in-first-out", или LIFO), поскольку первым из стека всегда удаляется элемент, добавленный в него последним. Нельзя выдернуть книгу из середины стопки, или добавить в середину новую.

Базовые операции для стека:

Операция	Эффективность	Вызов
конструктор (пустой набор)	$O(1)$	`std::stack<int> s;`
количество и/или проверка на пустоту	$O(1)$	`auto len=s.size();` `if(s.empty())...`
добавить значение	$O(1)$	`s.push(x);`
вершина стека	$O(1)$	`auto t=s.top();`
убрать вершину	$O(1)$	`s.pop();` // void

Нет итераторов!

Варианты реализации стека: