Page 35 - 6110

Лекція № 9

СТЕК, ЧЕРГА, СПИСОК

9.1 Лінійний список
Лінійний список в інформатиці та програмуванні визначається
як екземпляр абстрактного типу даних, що формалізує концепцію
впорядкованої множини елементів. Наприклад, абстрактний тип
даних для безтипових, змінних списків можна визначити із
допомогою конструктора та чотирьох операцій:
- конструктор для створення порожнього списка;
- операція визначення порожності списка;
- операція для додавання елемента в початок списка;
- операція отримання першого елемента списка (або “голови”)
списка;
- операція для визначення списка, що складається із всіх
елементів списка окрім першого (або його “хвоста”).
За визначенням, список – це послідовність з n≥0 елементів
X[1],X[2], … X[n], для якої виконується наступна умова: якщо n>0
та X[1] – перший елемент у списку, а X[n] — останній, то k-й
елемент розташований між X[k-1] та X[k+1] елементами для усіх
1<k<n.
З такими структурами даних виконуються наступні операції:
- отримання k-го елемента списку для читання чи запису в
нього нового значення;
- додавання нового елемента в будь-яку позицію в списку;
- видалення елемента списку;
- об'єднання в одному списку двох або більше лінійних списків;
- розбиття списку на два або більше фрагментів;
- створення копії списку;
- визначення кількості елементів в списку;
- сортування елементів списку;
- пошук елемента, що задовільняє певним критеріям.
Важливими окремими випадками лінійних списків, в яких
операції додавання та вилучення певних значень можуть бути
виконані лише для першого чи останнього елементу, є:
- стек – це лінійний список, в якому операції додавання та
вилучення виконуються лише на одному кінці списку (верхівці
стеку);
- черга (однобічна черга) – це лінійний список, в якому усі
операції додавання виконуються на одному кінці (в голові черги), а
операції вилучення – на іншому кінці списку (в хвості черги);
- дек або двобічна черга – це лінійний список, в якому всі
операції вставки та видалення виконуються на обох кінцях списку.
34