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

Стеки, очереди и деки – реализация на базе списков и массивов

Цели работы:

– Усвоить понятия «стек», «очередь», «дек».

– Получить практические навыки по реализации абстрактных структур данных стеков, очередей и деков на базе массивов и списков.

– Создать проект в системе Qt Creator, в котором осуществляется работа с одной из изучаемых структур данных и выполняется вывод на экран отображения содержимого этой структуры.

–

6.1 теоретические сведения

Стеком (stack, магазин) называют упорядоченный набор элементов, в котором занесение (добавление) новых элементов и удаление (выборка) существующих производятся только с одного его конца, называемого вершиной стека.

Стеки обслуживают дисциплину «последним пришел, первым ушел» (LIFO – Last in, first out).

Очередь (queue) – это упорядоченный набор элементов, в котором занесение (добавление) новых элементов осуществляется с одного его конца, называемого «концом очереди», а удаление (выборка) существующих производится из другого его конца, называемого началом очереди.

Очереди обслуживают дисциплину «первым пришел, первым ушел» (FIFO – First in, first out).

Дек это список, у которого обе позиции (начало и конец) доступны для добавления и взятия элемента. Таким образом, дек может быть и стеком, и очередью, и комбинацией этих структур. Наиболее часто дек представляется структурой с ограничением на вход или выход: дек с ограниченным входом (только одна позиция доступна для добавления элемента) и дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека).

ТЕКСТ ПРОГРАММЫ

bool priorityInsert(TQueue & que, TElQ newEl) {

if (isOverflow(que.PBQ, que.PEQ))

return false;

if ((newEl % 10) < (que.storage[que.PBQ] % 10))

INSERT(que, newEl);

else {

if (que.PBQ == 0) {

que.PBQ = QUEUE_SIZE - 1;

que.storage[0] = newEl;

}

else {

que.PBQ--;

que.storage[que.PBQ + 1] = newEl;

}

return true;

}

}

void showQueue(TQueue que) {

for (int i = que.PBQ; i! = que.PEQ; i++) {

if (i == QUEUE_SIZE - 1)

i = -1;

cout < < que.storage[i + 1] < < " ";

}

cout < < " \nТекущая позиция начала очереди " < < que.PBQ < < endl;

cout < < " Текущая позиция окончания очереди " < < que.PEQ < < endl;

}

РЕЗУЛЬТАТЫ ТЕСТИРОВАНИЯ ПРОЕКТА

В таблице 6.1 приведены значения элементов очереди

Таблица 6.1 – значения элементов очереди

Изначально заполняем позиции очереди стандартным методом числами 67, 67, 12, 44, 8. После заполняем очередь, используя добавление с учетом приоритета, вводя числа 11, 11, 9, 8. Итоговый результат будет таков:

9 8 67 67 12 44 8 11 11

На рисунке 6.1 изображен результат работы функции добавления элемента в очередь с учетом приоритета.

Рисунок 6.1 – результат добавления элемента в очередь с учетом приоритета

ВЫВОД

Во время лабораторной работы мы усвоили понятия «стек», «очередь», «дек», получили практические навыки по реализации абстрактных структур данных стеков, очередей и деков на базе массивов и списков и создали проект, в котором осуществляется работа с одной из изучаемых структур данных и выполняется вывод на экран отображения содержимого этой структуры.