3.1 Элементарные структуры: список, стек, очередь, дек

Стеки и очереди – это динамические множества, в которых элемент, удаляе­мый из множества операцией Delete, не задаётся произвольно, а определяется структурой множества. Именно, из стека (stack) можно удалить только тот элемент, который был в него добавлен последним: стек работает по принципу «последним пришёл – первым ушёл» (last-in, first-out – сокращенно LIFO). Из очереди (queue), напротив, можно удалить только тот элемент, который на­ходился в очереди дольше всего: работает принцип «первым пришёл – первым ушёл» (first-in, first-out — сокращенно FIFO). Существует несколько способов эф­фективно реализовать стеки и очереди, причем в основе эффективных реализаций этих структур лежат списки, потому что это наиболее простой способ организовать структуру данных, состоящее из некоторого множества элементов.