6. Стеки й черги як структури даних

Перелік алгоритмів, що розглядаються

  • реалізація стека за допомогою масива;
  • реалізація стека за допомогою покажчиків;
  • реалізація черги за допомогою масива;
  • реалізація черги за допомогою покажчиків.

Короткі теоретичні відомості

Питання для повторення

  1. Особливості роботи з покажчиками.

Постановка задачі

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

  Стек Черга
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);
  • дві цілочислові змінні ("голова" і "хвіт"), що дорівнюють індексам першого й останнього елементів.
Крім обов'язкових функцій доцільно використати функцію NextPos визначення позиції, наступної за заданою позицією p. Оскільки вважається, що елемент з індексом 0 є наступним за елементом з індексом N, то NextPos (p) = p mod N +1.
Опис алгоритмів
MakeNull
{
   виділити пам'ять для голова
   покажчик голови = NULL
   хвіст = голова
}
Empty
{
   результат порівняння хвіст == голова
}
DeQueue
{
   повернути el[голова]
   збільшити значення голови на 1
}
EnQueue
{
   збільшити значення хвоста на 1
   el[хвіст]=параметр
}

4. Реалізація черги за допомогою покажчиків

Опис структури даних
  • набір комірок, кожна з яких містить елемент черги (дані) і покажчик на наступну комірку черги (наступний);
  • комірки (голова і хвіст), які містять покажчики на перший і останній елементи черги.
Опис алгоритмів
MakeNull
{
   відвести пам'ять для голови
  голова.наступний=NULL
  хвіст = голова
}
Empty
{
   результат порівняння хвіст == голова
}
DeQueue
{
   tmp = голова
   результат = дані голови
   голова = покажчик голови
   звільнити tmp
}
EnQueue
{
   виділити пам'ять для комірки tmp
   покажчик хвоста = tmp
   хвіст = покажчик хвоста
   дані хвоста = параметр
   покажчик хвоста = NULL
}

Завдання для виконання

Постановка задачі

Скласти програми, що забезпечують виконання операцій зі стеками і чергами. Програми повинні забезпечувати
  • реалізацію основних процедур роботи зі структурою даних;
  • виконання вказаних викладачем дій зі структурою даних.

Технічні умови

  • кількість елементів у структурі даних не перевищує 10;
  • елементи стека (черги) є цілими числами.

Хід роботи

  1. Скласти програму Stack.cpp, реалізувати основні функції роботи зі стеком, використовуючи вказане подання стеку:
    • парні номери робочих місць — за допомогою масиву;
    • непарні номери робочих місць — за допомогою покажчиків.
  2. Виконати в покроковому режимі вказані викладачем дії зі стеком, записавши у звіт зміни, що відбуваються у стеку.
  3. Скласти програму Queue.cpp, реалізувати основні функції роботи з чергою, використовуючи вказане подання черги:
    • парні номери робочих місць — за допомогою покажчиків;
    • непарні номери робочих місць — за допомогою масиву.
  4. Виконати в покроковому режимі вказані викладачем дії з чергою, записавши у звіт зміни, що відбуваються у черзі.

Запитання для самоконтролю

  1. Дайте означення стека і черги.
  2. Які основні оператори використовують абстрактні типи даних стек і черга?
  3. Поясніть особливості реалізації стека за допомогою масива.
  4. Поясніть особливості реалізації стека за допомогою покажчиків.
  5. Поясніть особливості реалізації черги за допомогою масива.
  6. Поясніть особливості реалізації черги за допомогою покажчиків.