Чергу
Це ще один тип структури даних, що підтримує той же набір опцій, що і стек, однак у нього протилежна семантика. Для опису черзі застосовується абревіатура FIFO (First In, First Out), бо спочатку витягується елемент, що був доданий раніше за всіх. Назва структури говорить за себе – принцип роботи повністю збігається з чергами, що можна побачити в магазині, супермаркеті.
Січ
Це ще один вид структури даних, який ще називають чергою з двома кінцями. Опція підтримує наступний набір операцій:
- Внести елемент на початок (Складність: O(1)O(1)).
- Витягти компонент з початку (Складність: O(1)O(1)).
- Внесення елемента в кінець (Складність: O(1)O(1)).
- Вилучення елемента з кінця (Складність: O(1)O(1)).
- Перевірка, порожній чи дек (Складність: O(1)O(1)).
Списки
Дана структура даних визначає послідовність лінійно зв’язаних компонентів, для яких можна операції додавання компонентів в будь-яке місце списку і його видалення. Лінійний список задається покажчиком на початок списку. Типові операції над списками: обхід, пошук конкретного компонента, вставка елемента, видалення компонента, об’єднання двох списків у єдине ціле, розбивка списку на пару і так далі. Варто обмовитися, що в лінійному списку, крім першого, є попередній компонент для кожного елемента, не включаючи останній. Це означає, що компоненти списку знаходяться в упорядкованому стані. Так, обробка такого списку не завжди зручна, адже немає можливості просування в протилежну сторону — від кінця списку до початку. Однак у лінійному списку можна поетапно пройтися по всім складовим.
Ще існують кільцеві списки. Це така ж структура, що і лінійний список, проте вона має додаткову зв’язок між першим і останнім компонентами. Іншими словами, наступним за останнім елементом є перший компонент.
У цьому списку елементи рівноправні. Виділення першого і останнього – це умовність.
