Алгоритми і структури даних
Стек — лінійний список, у якому всі операції вставки і знищення елементів виконуються лише на одному з кінців списку.
Черга (одностороння черга) — лінійний список, у якому всі операції вставки здійснюються на одному з кінців списку, а всі операції знищення — на іншому.
Абстрактні типи даних стек і черга використовують оператори, наведені в таблиці нижче.
| Стек | Черга | |
|---|---|---|
| 1. Створення порожнього списку | MakeNull | |
| 2. Визначення, чи є структура порожньою | Empty | |
| 3.Знищення елемента з поверненням його значення | Pop | DeQueue |
| 4. Вставка елемента, що передається як параметр. | Push | EnQueue |
При реалізації структур даних можливість переповнення структури не розглядається.
Опис реалізацій
1.Реалізація стека за допомогою масива
Опис структури даних
- масив el, у якому (починаючи з елемента з індексом 0), зберігаються елементи стека (не більше N);
- цілочислова змінна (вершина), що дорівнює індексу останнього елемента.
Опис алгоритмів
MakeNull
вершина надати значення 0
>
Empty
<
результат порівняння вершина == 0
>
Pop
<
повернути el[вершина]
зменшити значення вершини на 1
>
Push
збільшити значення вершини на 1
el[вершина]=параметр
>
2. Реалізація стека за допомогою покажчиків
Опис структури даних
- набір комірок, кожна з яких містить елемент стека (дані) і покажчик на наступну комірку стека (наступний);
- комірка (заголовок), яка містить покажчик на перший елемент стека (елементи стека додається перед заголовком).
Опис алгоритмів
MakeNull
виділити пам’ять для заголовку
покажчик заголовку = NULL
>
Empty
<
результат порівняння заголовок.наступний== NULL
>
Pop
<
tmp = заголовок
заголовок = заголовок.наступний
результат = заголовок.дані
звільнити tmp
>
Push
виділити пам’ять для комірки tmp
tmp.дані = параметр
tmp.наступний = заголовок
заголовок = tmp
>
3.Реалізація черги за допомогою масива
Опис структури даних
- масив el, у якому (починаючи з елемента з індексом 0) зберігаються елементи черги (не більше N);
- дві цілочислові змінні (“голова” і “хвіт”), що дорівнюють індексам першого й останнього елементів.
Опис алгоритмів
MakeNull
виділити пам’ять для голова
покажчик голови = NULL
хвіст = голова
>
Empty
<
результат порівняння хвіст == голова
>
DeQueue
<
повернути el[голова]
збільшити значення голови на 1
>
EnQueue
збільшити значення хвоста на 1
el[хвіст]=параметр
>
4. Реалізація черги за допомогою покажчиків
Опис структури даних
- набір комірок, кожна з яких містить елемент черги (дані) і покажчик на наступну комірку черги (наступний);
- комірки (голова і хвіст), які містять покажчики на перший і останній елементи черги.
Опис алгоритмів
MakeNull
відвести пам’ять для голови
голова.наступний=NULL
хвіст = голова
>
Empty
<
результат порівняння хвіст == голова
>
DeQueue
<
tmp = голова
результат = дані голови
голова = покажчик голови
звільнити tmp
>
EnQueue
виділити пам’ять для комірки tmp
покажчик хвоста = tmp
хвіст = покажчик хвоста
дані хвоста = параметр
покажчик хвоста = NULL
>
Завдання для виконання
Постановка задачі
- реалізацію основних процедур роботи зі структурою даних;
- виконання вказаних викладачем дій зі структурою даних.
Технічні умови
- кількість елементів у структурі даних не перевищує 10;
- елементи стека (черги) є цілими числами.
Хід роботи
- Скласти програму Stack.cpp, реалізувати основні функції роботи зі стеком, використовуючи вказане подання стеку:
- парні номери робочих місць — за допомогою масиву;
- непарні номери робочих місць — за допомогою покажчиків.
- Виконати в покроковому режимі вказані викладачем дії зі стеком, записавши у звіт зміни, що відбуваються у стеку.
- Скласти програму Queue.cpp, реалізувати основні функції роботи з чергою, використовуючи вказане подання черги:
- парні номери робочих місць — за допомогою покажчиків;
- непарні номери робочих місць — за допомогою масиву.
- Виконати в покроковому режимі вказані викладачем дії з чергою, записавши у звіт зміни, що відбуваються у черзі.
Запитання для самоконтролю
- Дайте означення стека і черги.
- Які основні оператори використовують абстрактні типи даних стек і черга?
- Поясніть особливості реалізації стека за допомогою масива.
- Поясніть особливості реалізації стека за допомогою покажчиків.
- Поясніть особливості реалізації черги за допомогою масива.
- Поясніть особливості реалізації черги за допомогою покажчиків.
- Головна
- 1. Оцінка ефективності алгоритмів
- 2. Пошукові алгоритми
- 3. Квадратичні алгоритми сортування
- 4. Сортування Шелла
- 5. «Швидке» сортування
- 6. Стеки й черги як структури даних
- 7. Лінійні списки як структури даних
- 8-9. Дерева і алгоритми їх обробки
- 10-11. Графи і алгоритми їх обробки
- 12-13 Хеш-таблиці й алгоритми їх обробки
Визначення стека в програмуванні
Стек — це масив або структура списку викликів функцій і параметрів, які використовуються в сучасному комп’ютерному програмуванні та архітектурі ЦП. Подібно до стопки тарілок у ресторані-буфеті чи кафетерії, елементи в стопці додаються або видаляються з верхньої частини стопки в порядку «останній прийшов, перший вийшов» або LIFO.
Процес додавання даних до стеку називається «виштовхуванням», тоді як отримання даних зі стеку називається «вискакуванням». Це відбувається у верхній частині стека. Покажчик стека вказує на розмір стека, регулюючи, коли елементи надсилаються або висуваються до стека.
Під час виклику функції адреса наступної інструкції поміщається в стек.
Коли функція завершує роботу, адреса виймається зі стеку , і виконання продовжується за цією адресою.
Дії в стеку
Існують інші дії, які можна виконувати зі стеком залежно від середовища програмування.
- Peek: дозволяє перевірити найвищий елемент у стеку без фактичного видалення елемента.
- Поміняти місцями: також називається «обміном», положення двох верхніх елементів стека міняються місцями, перший елемент стає другим, а другий — верхнім.
- Дублікат: найвищий елемент виривається зі стеку, а потім двічі повертається в стек, створюючи дублікат вихідного елемента.
- Обертання: також називається «ролом», визначає кількість елементів у стеку, які обертаються у своєму порядку. Наприклад, обертання чотирьох верхніх елементів стека перемістить найвищий елемент на четверту позицію, тоді як наступні три елементи перемістяться на одну позицію вгору.
Стек також відомий як « останній прийшов, перший вийшов (LIFO)».
Приклади: у C і C++ змінні , оголошені локально (або автоматично), зберігаються в стеку.