Міністерство освіти І науки України
національний університет “Львівська політехніка”
Кафедра ЕОМ
Структура даних ЧЕРГА
Методичні вказівки
До лабораторної роботи № 4 з дисципліни
" Програмування. Частина III.
Структури даних та алгоритми "
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Затверджено
на засідання кафедри
“Електронні обчислювальні машини”.
Протокол № __ від ________ 2010
р. р.
Львів – 2010
Методичні вказівки до лабораторної роботи "Структура даних ЧЕРГА" з дисципліни “Програмування. Частина IIІ. Структури даних та алгоритми" для підготовки студентів напрямку 6.0915 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 12 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. Мета роботи
Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач.
2. Теоретичні відомості
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Приклад :
В послідовності 8 2 6 3 1 4 9 кожна парна цифра визначає операцію push (додавання цієї цифри в чергу), а кожна непарна цифра визначає операцію pop (вилученя з черги одного елемента).
-
Введемо такі позначення: P – покажчик початку черги, К – покажчик кінця черги
Наведемо динаміку вмісту черги під час обробки заданої послідовності:
K
P
0)
- порожня черга
P K
P K
P K
1)
8
2)
8
2
3)
8
2
6
P K
P K
P K
4)
2
6
5)
6
6)
6
4
P K
7)
4
Оскільки черга - це важлива абстракція даних, у стандартній бібліотеці С++ передбачений клас queue, для використання якого потрібно включити заголовочний файл:
# include <queue>
Набір стандартних операцій роботи з чергою показаний у таблиці:
|
Операція |
Дія |
|
push(іtem) |
Поміщає новий елемент у кінець черги |
|
pop() |
Вилучає елемент з черги, але не повертає його значення |
|
front() |
Повертає значення елемента з початку черги, але не вилучає його |
|
empty() |
Повертає true, якщо черга порожня, і false у противному випадку |
|
sіze() |
Повертає кількість елементів у черзі |
Розглянемо статичну реалізацію черги на основі масиву з фіксованим рзміром. В наведенному далі лістінгу показано заголовочний файл для шаблонного класу queue, аналогічний класу queue зі стандартної бібліотеки шаблонів STL.
// ФАЙЛ: queue1.h (частина простору імен main_savitch_8B)
#ifndef MAIN_SAVITCH_QUEUE1_H
#define MAIN_SAVITCH_QUEUE1_H
#include <cstdlib> // Provides size_t
namespace main_savitch_8B
{
template <class Item>
class queue
{
public:
// ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ
typedef std::size_t size_type;
typedef Item value_type;
static const size_type CAPACITY = 30;
// КОНСТРУКТОР
queue( );
// МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ
void pop( );
void push(const Item& entry);
// КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ
bool empty( ) const { return (count == 0); }
Item front( ) const;
size_type size( ) const { return count; }
private:
Item data[CAPACITY];
size_type first;
size_type last;
size_type count;
// ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ
size_type next_index(size_type i) const { return (i+1) % CAPACITY; }
};
}
#include "queue1.template" // Директива включення реалізації.
#endif
Файл реалізації класу queue показаний в наступному лістінгу:
#include <cassert> // Надає макрос assert.
namespace main_savitch
{
template <class Item>
const typename queue<Item>::size_type queue<Item>::CAPACITY;
template <class Item>
queue<Item>::queue( )
{
count = 0;
first = 0;
last = CAPACITY - 1;
}
template <class Item>
Item queue<Item>::front( ) const
{
assert(!empty( ));
return data[first];
}
template <class Item>
void queue<Item>::pop( )
{
assert(!empty( ));
first = next_index(first);
--count;
}
template <class Item>
void queue<Item>::push(const Item& entry)
{
assert(size( ) < CAPACITY);
last = next_index(last);
data[last] = entry;
++count;
}
}
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
-
додавання элемента справа;
-
додавання элемента слева;
-
вилучення элемента справа;
-
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.