РівеньІІІ

Способи зображення графів в пам‘яті комп‘ютера.

Які способи зображення дерев в пам‘яті комп‘ютера є оптимальними?

В якому випадку не потрібно зберігати інформацію про ребра?

Метод сортування на деревах - метод вибірки з дерева. Записати складність алгоритму.

Алгоритм побудови бінарного дерева згортання.. Записати складність алгоритму

Тема 8. Лінійні структури даних. Стеки, черги, деки. Організація стеків, черг і деків. Види черг. Представлення лінійнихї структур в комп‘ютері. Операції додавання та видалення елементів з лінійних структур.

Рівень І

Стек – це…

Деки – це…

Дисципліна обслуговування LIFO – це…

Черга – це…

Дисципліна обслуговування FIFO - це…

Лінійна черга це…

Пріоритетна черга це…

Циклічна черга це …

Рівень ІІ

Перевагою стека перед іншими організаціями даних є…

Зобразити операцію додавання елемента у стек.

Зобразити операцію додавання елемента у чергу.

Зобразити операцію видалення елемента з деку.

Рівень ІІІ

Способи зображення черг в пам‘яті комп‘ютера.

Способи зображення деків в пам‘яті комп‘ютера.

Галузі застосування стеків.

Операції над лінійними структурами даних. Їх реалізація.

ЛЕКЦІЯ 7. ЛІНІЙНІ СТРУКТУРИ ДАНИХ.

СТЕКИ, ЧЕРГИ І ДЕКИ.

Стеки, черги і деки - це однотипні лінійні структури. Їх називають динамічними лінійними структурами даних у зв ' язку з тим, що вибірка елемента із цих послідовностей зводиться до операції виключення, тобто ліквідації його у послідовностях. Відрізняються ці структури одна від одної порядком виконання операцій включення і виключення елементів.

До основних операцій над цими структурами відносять [2]:

а) створення нової структури даних;

б) запис або включення елемента у вже існуючу структуру даних;

в) виключення елемента зі структури;

г) перевірка умови існування структури.

Стеки

Стек - це впорядкована лінійна динамічно змінювана послідовність елементів, в якій виконуються наступні умови:

1) новий елемент приєднуєть­ся завжди до одного і того ж боку послідовності;

2) доступ до елемента здійснюється завжди з того боку послідовності, до якого приєднується елемент;

3) елемент зберігається в послідовності до моменту його виклику.

Прикладом стеку є стопка тарілок, а також магазин патронів у рушниці. За аналогією з останнім прикладом стек ще часто називають магазинною пам ' яттю.

Операцію включення елемента у стек називають "проштовхуванням", а операцію виключення із послідовності - "виштовхуванням". Найбільш і найменш доступні елементи стека навивають відповідно верхом і низом стека. Операції включення і виключення зі стека виконують в одному і тому ж боку послідовності, але виключаються елементи зі стека в порядку, зворотному до того, в якому вони потрапили в послідовність. В кожний момент часу зі стека можна забрати лише один елемент. Дисципліну обслуговування стека часто називають дисципліною LIFO - "останній прийшов, перший пішов".

Стек можна зобразити у вигляді послідовності A=A₁,...,A_n-1,A_n, де A_n - елемент, що вказує на вхід-вихід у послідовність; A₁, A_n - відповідно низ і верх стека. Щоб прочитати елемент A_j, необхідно вибрати зі стека елементи A_n,..., A_j+1.

Також стек можна представити у вигляді трубки з підпруженим дном, що розміщена вертикально. Верхній кінець трубки відкритий, у нього можна включати, або заштовхувати елементи. Новий елемент, що додається, проштовхує елементи, включені в стек раніше, на одну позицію вниз. При виключенні елементів зі стека вони виштовхуються нагору.

Незалежно від того, як реалізований стек, процедури, що працюють із ним, повинні вміти поміщати елементи в стек, вибирати елементи зі стеку й перевіряти, не чи порожній стек. Для того щоб можна було працювати з новим типом даних, необхідні спеціальні операції, наприклад:

NEW (стек) створення порожнього стека

PUSH (стек, елемент даних) розміщення елемента в стек

POP (стек) вибірка елемента з вершини стека

EMPTY (стік) перевірка, чи порожній стек; результатом є значення "істина", якщо стек порожній, і "хибно " в протилежному випадку.

NEW і PUSH - базові операції, використовувані при роботі зі стеком. Перша створює стек, а друга поміщає в нього елементи. POP - процедура, характерна тільки для роботи зі стеком. Вона може бути визначено за допомогою двох базових проміжних операцій ТОР і REMOVE, які дозволяють виділити дві основні функції, реалізовані POP, але не визначають способів організації доступу до структури з інших модулів:

Відповідно наведеним вище визначенням, POP вибирає вершину стека й видаляє її зі стека. Вершина стека описується в такий спосіб: якщо стек не порожній, вершина являє собою останній розміщений у стек елемент; а якщо ні, то стек не має вершини. Операція REMOVE дає в результаті стек без елемента, розміщеного в нього останнім. До тільки що створеного стеку операцію REMOVE застосовувати не можна. Для визначення порожнього стека використовується поняття нового (або тільки що створеного) стека: порожній стек не містить жодного елемента.

Будь-яка реалізація стека повинна задовольняти цим визначенням. Важливо, що стек визначається як спосіб зберігання даних, які підпорядковуються певним правилам, що діють при звертанні до даних, а не як масив з вказівниками, які пересуваються за певними правилами.

Основною перевагою стека перед іншими організаціями даних є те, що у ньому не потрібна адресація елементів. Для обслуговування стека потрібно лише дві команди: PUSH - "проштовхнути" iPOP - "виштовхнути". Зі стеком пов ' язаний завжди один вказівник, який вказує на верхній елемент у стеку. На початку такий вказівник дорівнює нулю.

Найпростішим прикладом вдалого застосування стека може служити задача перепису вектора у зворотному порядну. На практиці стекова структура даних найчастіше застосовується в рекурсивних алгоритмах, при трансляції, а також при обробці переривань програм.