Лабораторна робота № 6

Тема: черги.

Мета: набути практичного досвіду та закріпити знання про представлення стека, дека, приоритетної черги та дисциплінах їх обслуговування.

Теми для попередньої роботи:

• масиви та списки;

• безприоритетні та приоритетні черги;

• дисципліни обслуговування черг.

Загальні відомості

Черга – така структура даних, що зберігає елементи і забезпечує доступ до них тільки в певному порядку, визначеному пріоритетом.

Для реалізації черг можуть бути використані масиви або лінійні списки.

Дек – послідовний набір даних, у якому включення і виключення елементів може здійснюватися із кожного з двох кінців набору. Пріоритетом є час надходження запитів. Часні випадки дека - черга LІFO або стек та черга FІFO.

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

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

Типове завдання

Розробити функції роботи з приоритетною чергою. Постановка запитів у чергу виконується підряд в кінець черги, зняття – по приоритету. Чергу реалізувати на масиві.

Текст програми

#include<iostream>

#include<stdlib.h>

#include<conio.h>

using namespace std;

int och[512]; //черга на 512 запитів

int point=0; //вказівник на чергу

int addel (int a) //додавання запиту у чергу

{ if (point<512) och[point++]=a;

else

{ cout << "enough queue\n"; //черга переповнена

return 0;

}

return 1;

}

void delel (void) //читання запиту з черги

{ if (point>0)

{ int max=och[0], nmax=0; // пошук запиту з максимальним параметром

for(int i=1; i<point; i++)

if (max<och[i])

max=och[i], nmax=i;

cout<<"read "<<max<<endl;

point--; //зсув черги

for(int i=nmax; i<point; i++)

och[i]=och[i+1];

}

}

void printoch (void) //вміст черги

{ if (point==0)

cout<<"queue empty \n";

else

{ cout<<"in queue: ";

for (int i=0;i<point;i++)

cout<<och[i]<<" ";

cout<<"\n";

}

}

void main (void)

{ system("chcp 1251 > nul"); // для роботи з кирилицею

int op,f;

do

{ op=rand() % 2; //0-запис запиту, 1- читання

cout<<"enquiry "<< op<< "\n";

if (op) delel();

else

{ f=rand() % 15; //запит

if (! addel(f)) exit(1);

}

printoch ();

getch();

} while (1);

}

Фрагмент результатів роботи програми

enquiry 0

in queue: 3

enquiry 0

in queue: 3 7

enquiry 0

in queue: 3 7 5

enquiry 1

read 7

in queue: 3 5

enquiry 1

read 5

in queue: 3

enquiry 1

read 3

7

Індивідуальні завдання

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

1. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (початку черги). Черга організована на масиві із зсувом після кожного читання та та на масиві із зсувом після досягнення границі пам’яті, що виділена для черги. Приоритет: мin значення числового параметра; при співпаданні параметрів – LIFO.

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

3. Приоритетна черга. Постановка запитів в чергу виконується підряд в кінець черги, зняття – по приоритету. Черга організована на масиві та списку. Приоритет: мin значення числового параметра; при співпаданні параметрів - LIFO.

4. Стек. Стек організований на масиві та на двоспрямованому списку.

5. Дек. Дек організований на масиві із циклічним заповненням та на двоспрямованому списку. Операції виконуються з різних кінців дека.

6. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (з початку черги). Черга організована на масиві із циклічним заповненням та із зсувом. Приоритет: мах значення числового параметра; при співпаданні параметрів – FIFO.

7. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд із старших адрес (кінця черги). Черга організована на масиві та на списку. Приоритет: мах значення числового параметра; при співпаданні параметрів – FIFO.

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

9. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (початку черги). Черга організована на масиві із циклічним заповненням та списку. Приоритет: мах значення числового параметра; при співпаданні параметрів – FIFO.

10. Дек. Дек організований на масиві із циклічним заповненням та із зсувом. Операції виконуються з різних кінців дека.

11. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (з початку черги). Черга організована на масиві із зсувом після кожного читання та на масиві із зсувом після досягнення границі пам’яті, що виділена для черги. Приоритет: мах значення числового параметра; при співпаданні параметрів – FIFO.

12. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (з початку черги). Черга організована на масиві із циклічним заповненням та із зсувом. Приоритет: мin значення числового параметра; при співпаданні параметрів – LIFO.

13. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд із старших адрес (кінця черги). Черга організована на масиві та на списку. Приоритет: мin значення числового параметра; при співпаданні параметрів – LIFO.

14. Приоритетна черга. Постановка запитів в чергу виконується по приоритету, зняття - підряд з молодших адрес (з початку черги). Черга організована на масиві із циклічним заповненням та списку. Приоритет: мin значення числового параметра; при співпаданні параметрів – LIFO.

15. Приоритетна черга. Постановка запитів в чергу виконується підряд в кінець черги, зняття – по приоритету. Черга організована на масиві та списку. Приоритет: мax значення числового параметра; при співпаданні параметрів - FIFO.

Контрольні питання

1. Що таке «черга», дайте визначення?

2. Що являє собою стек?

3. Які відомі види черг?

4. На основі яких структур даних може бути організований стек?

5. Які операції допустимі для черги?

6. Які операції допустимі для стека?

7. Який алгоритм читання запитів із стека?

8. Які властивості притаманні черзі?

9. Який недолік простої черги? Який спосіб боротьби з цим недоліком ?

10. Чим відрізняється циклічна черга від простої?

11. Чим відрізняється стек на основі масиву від стека на основі зв’язного списку ?

12. Чим відрізняється пріоритетна черга з приоритетним записом від черги з пріоритетним читанням?

13. Чим відрізняється стек на основі зв’язного списку від власне зв’язного списку ?

14. Які області застосування черг і стеків ?

15. Що являє собою дек?

16. Який алгоритм зняття запиту з пріоритетної черги, в яку запити ставляться підряд як приходять?

17. Який алгоритм постановки запита в пріоритетну чергу, в якій запити знімаються підряд?