Дайте оцінку такій динамічні структури об’єктів як черги, стеки та деки.

Стеки, черги та деки призначені для тимчасового збереження та почергової обробки даних. Дійсно, ми не можемо отримати, наприклад, другий елемент черги, не змінивши її (для цього потрібно спочатку взяти перший елемент). В той же час, у багатьох задачах дані, маючи динамічний розмір, повинні багаторазово переглядатись та певним чином оброблятись. Для таких цілей використовують списки. Ми розглянемо декілька видів списків, які мають спільні властивості, але відрізняються способами реалізації та складом допустимих дій.

Стек – це такий лінійний список, який має одну точку доступу: з однієї сторони дані додаються і з тієї ж сторони дані вилучаються. Стек організований за принципом LIFO (L ast I n F irst O ut - останній ввійшов – перший вийшов).

Черга - це такий лінійний список, який має дві точки доступу: з однієї сторони дані в чергу додаються, а з іншої – вилучаються. Черга організована за принципом FIFO (F irst I n F irst O ut – перший ввійшов – перший вийшов).

Head – точка видалення, Tail – точка додавання.

Отже, черга – це асоціація об’єктів, що очікують доступу до системи обслуговування.

дек (deck) (стек із двома кінцями) -- лінійний список, у якому всі додавання й видалення (і звичайно всякий доступ) робляться на обох кінцях списку.

Дек часто називають двостороннім стеком або двосторонньою чергою. Визначимо дек:

1. Порожній дек.

2. Перший елемент; дек.

3. Дек; останній елемент.

Дек можна представити, як сукупність однотипних елементів, в якій ми маємо доступ до початку або кінця деку для додавання або взяття елементів (Рис. 10.9).

Рис. 10.13 – Дек