[ЗМІСТ] [Далі] [Назад] [Початок розділу]
10.3. Черга та дек
10.3.1. Черга
Черга –
ще одна рекурсивна структура даних, яку можна визначити так:
1.
Порожня
черга.
2.
Перший
елемент; черга.
Чергу можна представити, як сукупність однотипних
елементів, в якій ми маємо доступ до кінця черги при додаванні елементів та до
початку черги при взятті елементів (Рис. 10.9).
Рис. 10.9 – Черга
Операції, відношення та інструкції для черг:
1.
Почати
роботу.
2.
Чи
порожня черга?
3.
Додати
елемент до кінця черги.
4.
Взяти
елемент з початку черги.
Дії 1,
3, 4 – інструкції; 2 – відношення.
“Почати
роботу” означає створити порожню чергу.
“Додати
елемент до кінця черги” – додати до черги один елемент, який стає останнім у
черзі.
“Взяти
елемент” – взяти та повернути значення першого елемента. Першим стає попередній
елемент черги або черга стає порожньою. Для порожньої черги ця інструкція
повинна давати відмову.
Можлива
реалізація черги з використанням вказівників зображена на Рис. 10.10. Елементи
черги – це записи з двох полів: поле даних та вказівник на наступний елемент.
За допомогою вказівника елементи черги з’єднані у ланцюг. У останньому елементі
вказівник на наступний елемент дорівнює nil. Саму чергу реалізовано, як запис з двох
вказівників: на початок черги та на кінець черги. Вказівник на кінець черги потрібний для того, щоб
при додаванні елементів не проходити всю чергу від початку до кінця. Якщо черга порожня, то елементів немає, а
обидва вказівники дорівнюють nil.
Рис. 10.10 – Реалізація черги
Розглянемо модуль реалізації черги цілих
чисел у Паскалі, IntQueue.
Тут qref – вказівник на елементи черги; qelem – елемент черги; queue – черга; поле bg –
вказівник на початок черги, а en – вказівник на кінець черги.
unit IntQueue;
interface
type qref = ^qelem; { Вказівник на елемент черги }
qelem = record { Елемент черги }
d: integer;
next: qref
end;
queue = record { Черга }
bg, en: qref
end;
procedure Init(var q: queue); { Почати роботу }
function Empty (q: queue): boolean; { Чи порожня черга?}
procedure Add (var q: queue; n: integer); { Додати елемент до кінця черги }
procedure Take (var q: queue; var n: integer); {
Взяти елемент з початку черги }
implementation
.................
procedure Add (var q: queue; n: integer);
var p:
qref;
begin
new(p);
p^.d := n; p^.next := nil;
if
q.bg=nil then q.bg := p
else
q.en^.next:=p;
q.en := p
end;
procedure Take (var q: queue; var n: integer);
var p:
qref;
begin
if q.bg =
nil then begin
writeln(' Take: Черга порожня'); halt
end;
p:=q.bg;
n:=q.bg^.d;
q.bg:=q.bg^.next;
if
q.bg=nil then q.en:=nil;
dispose(p)
end;
end.
Підпрограми
Init та Empty є дуже простими та майже не відрізняються
від аналогічних підпрограм для стеку. Тому їх реалізація залишається для самостійної
роботи. Розглянемо більш докладно додавання та взяття елемента черги.
Зміни
черги під час дії „додати елемент” (процедура Add) зображені на Рис. 10.11. На відміну від стеків, для черг треба
окремо розглядати випадок додавання елемента до непорожньої черги (Рис. 10.11
а)-в) ) та порожньої черги (Рис. 10.11 г)-е) ). Після new(p) (Рис. 10.11
а), г) ) виділяється пам’ять під новий елемент черги. Ланцюг p^.d:=n; p^.next:=nil (Рис. 10.11
б), д) ) забезпечує запис числа n у поле
даних та значення nil у
поле вказівника на наступний елемент черги. Якщо черга порожня (q.bg=nil), то доданий
елемент буде також першим елементом черги (q.bg:=p), інакше треба
зв’язати останній елемент, на який вказує q.en, з
новим елементом черги (q.en^.next:=p). Нарешті, треба
змінити вказівник на кінець черги (q.en:=p). Останні дії
зображено на Рис. 10.11 в), е).
Рис. 10.11 – Додавання елемента до кінця черги
Зміни
черги під час дії „взяти елемент” (процедура Take) зображені на Рис. 10.12. Якщо черга порожня, то виводиться
повідомлення про помилку, а програма аварійно завершує роботу. Якщо ж черга не
порожня, то треба окремо розглядати два випадки: черга складається більше, ніж
з одного елемента (Рис. 10.12 а)-в) ), та черга складається з одного елемента
(Рис. 10.12 г)-е) ). Після p:=q.bg; n:=q.bg^.d (Рис. 10.12
а), г) ) запам’ятовуємо вказівник на перший елемент черги та читаємо дані з
цього елемента. Присвоєння q.bg:=q.bg^.next
у першому випадку переміщує вказівник q.bg на другий елемент
черги (Рис. 10.12 б) ), а у другому – присвоює йому значення nil (Рис. 10.12 д) ). Якщо тепер q.bg=nil, тобто черга
складалась з 1 елемента, треба q.en:=nil, бо черга стає порожньою. Нарешті, в
обох випадках потрібно звільнити пам’ять, яку займав перший елемент черги (dispose(p)). Останні дії зображено на Рис. 10.12 в), е).
Рис. 10.12 – Взяття елемента з початку черги
Як
приклад роботи з чергою розглянемо задачу присвоєння черзі q1 значення черги q2, використовуючи тільки дії над чергами. Виконати
це присвоєння просто для записів (q1:=q2) некоректно, оскільки
подальші зміни кожної з черг q1 або q2 будуть впливати на іншу. Тому треба
скопіювати всі елементи q2, створивши нову чергу q1. Відповідна програма QueueTst наведена нижче. Зверніть увагу на
параметри процедури SetQueue. q1 та q2 описано як параметри-змінні тому, що запис
q2 змінюється у процедурі. Справа в тому, що склад
дій над чергою не дозволяє скопіювати чергу, не знищивши її. Для відновлення
черги q2 використовується допоміжна черга q3. Після відновлення вказівники на початок та кінець черги у q2 будуть вказувати можливо на іншу область пам’яті, ніж перед викликом
процедури. Але сама черга буде складатись з тих самих елементів у тій самій
послідовності, що і до виклику. Процедура ShowQueue показує чергу, знищуючи її. Ми використовуємо цю
процедуру, щоб продемонструвати, що присвоєнння правильно копіює елементи черги
q2 у q1, не знищуючи чергу q2.
Program QueueTst;
uses IntQueue;
{q1:=q2}
procedure SetQueue(var q1, q2: queue);
var q3: queue;
n:
integer;
begin
Init(q3);
while
not Empty(q2) do begin
Take(q2,n);
Add(q1,n); Add(q3,n);
end;
while
not Empty(q3) do begin
Take(q3,n);
Add(q2,n);
end;
end;
{Показати чергу}
procedure ShowQueue(var q: queue);
var n: integer;
begin
while
not Empty(q) do begin
Take(q,n);
write(n,' ')
end;
writeln
end;
var q1,q2: queue;
n:
integer;
i,m:
word;
begin
Init(q2);
writeln('Кількість
елементів черги');
readln(m);
for
i:=1 to m do begin
write('Елемент ',i,' = ');
readln(n);
Add(q2,n)
end;
SetQueue(q1,q2);
write('q2 = ');
ShowQueue(q2);
write('q1 = ');
ShowQueue(q1);
end.
Завершуючи
розгляд черг, наведемо вигляд файлу заголовку модуля реалізації черг у мові Сі queue.h.
/* queue.h */
typedef struct qelem *qref; /* Вказівник на елемент черги */
struct qelem { /* Елемент черги */
int d;
qref next;
};
typedef struct { /* Черга */
qref bg, en;
} queue;
extern void init(queue *pq); /* Почати роботу */
extern int empty(queue q); /* Чи порожня черга?
*/
extern void add(queue *pq, int n); /* Додати елемент до кінця черги */
extern void take(queue *pq, int *pn); /* Взяти елемент з початку черги */
10.3.2. Дек
Дек
часто називають двостороннім стеком або двосторонньою чергою. Визначимо дек:
1.
Порожній
дек.
2.
Перший
елемент; дек.
3.
Дек;
останній елемент.
Дек можна представити, як сукупність однотипних
елементів, в якій ми маємо доступ до початку або кінця деку для додавання або
взяття елементів (Рис. 10.9).
Рис. 10.13 – Дек
Операції, відношення та інструкції для деків:
1.
Почати
роботу.
2.
Чи
порожній дек?
3.
Додати
елемент до початку деку.
4.
Взяти
елемент з початку деку.
5.
Додати
елемент до кінця деку.
6.
Взяти
елемент з кінця деку.
Дії 1,
3, 4, 5, 6 – інструкції; 2 – відношення.
“Почати
роботу” означає створити порожній дек.
“Додати
елемент до початку деку” – додати до деку один елемент, який стає першим у
деку.
“Взяти
елемент з початку деку” – взяти та повернути значення першого елемента. Першим
стає наступний елемент деку або дек стає порожнім. Для порожнього деку ця
інструкція повинна давати відмову.
“Додати
елемент до кінця деку” – додати до деку один елемент, який стає останнім у
деку.
“Взяти
елемент з кінця деку” – взяти та повернути значення останнього елемента. Першим
стає попередній елемент деку або дек стає порожнім. Для порожнього деку ця
інструкція повинна давати відмову.
Можлива
реалізація деку з використанням вказівників зображена на Рис. 10.14. Елементи
деку – це записи з трьох полів: поле даних та вказівники на наступний та
попередній елементи. За допомогою вказівників елементи деку з’єднані у ланцюг.
У останньому елементі вказівник на наступний елемент дорівнює nil, а у першому елементі вказівник на
попередній елемент дорівнює nil. Сам дек реалізовано, як запис з двох вказівників: на початок деку та на
кінець деку. Якщо дек порожній, то елементів немає, а обидва вказівники
дорівнюють nil.
Рис. 10.14 – Реалізація деку
Для деків більш докладно розглянемо їх
реалізацію у мові Сі, а у Паскалі обмежимось інтерфейсною частиною модуля.
unit IntDeque;
interface
type dref = ^delem; {Вказівник на
елемент деку}
delem
= record {Елемент
деку}
d: integer;
next, prev: dref
end;
deque
= record {Дек}
bg, en: dref
end;
procedure Init(var d: deque); {Почати роботу}
function Empty (d: deque): boolean; {Чи
порожній дек?}
procedure PutBg (var d: deque; n:
integer); {Додати елемент до початку
деку}
procedure GetBg (var d: deque; var n: integer);
{Взяти елемент з початку деку}
procedure PutEn (var d: deque; n:
integer); {Додати елемент до кінця
деку}
procedure GetEn (var d: deque; var n: integer);
{Взяти елемент з кінця деку}
implementation
.................
end.
Модуль
роботи з деком у Сі складається з файлів deque.h та deque.c. Реалізація функцій init, empty, put_en, get_en залишається на самостійну роботу. Функції init та empty дуже прості. Що ж стосується put_en та get_en, то простий шлях їх реалізації ми розглянемо нижче.
/* deque.h */
typedef struct delem *dref; /* Вказівник на елемент деку */
struct delem { /* Елемент деку */
int
d;
dref next, prev;
};
typedef struct { /* Дек */
dref
bg, en;
}
deque;
extern void init(deque *pd); /* Почати роботу */
extern int empty(deque d); /* Чи порожній дек? */
extern void put_bg(deque *pd, int n); /* Додати елемент до початку деку */
extern void get_bg(deque *pd, int *pn); /* Взяти елемент з початку деку */
extern void put_en(deque *pd, int n); /* Додати елемент до кінця деку */
extern void get_en(deque *pd, int *pn); /* Взяти елемент з кінця деку */
/*
deque.c*/
#include
<stdio.h>
#include
<stdlib.h>
#include
"deque.h"
.................
void put_bg(deque
*pd, int n)
{
dref p;
p = (dref) malloc(sizeof(struct delem));
p -> d = n;
p -> prev = NULL;
p -> next = pd -> bg;
if (pd -> bg == NULL) pd -> en = p;
else pd -> bg -> prev = p;
pd -> bg = p;
}
void
get_bg(deque *pd, int *pn)
{
dref p;
if (pd -> bg ==NULL)
{
printf("get_bg: Дек порожнiй\n");
exit(1);
}
p = pd -> bg;
*pn = p -> d;
pd -> bg = pd -> bg -> next;
if (pd -> bg == NULL) pd -> en = NULL;
else pd -> bg -> prev = NULL;
free(p);
}
.................
Зміни
деку під час дії „додати елемент до початку деку” (функція put_bg) зображені на Рис. 10.15. Для деків, як і для черг, треба окремо
розглядати випадок додавання елемента до непорожнього деку (Рис. 10.15 а)-б) )
та порожнього деку (Рис. 10.15 в)-г) ). Ланцюг p = (dref) malloc(sizeof(struct delem)); p -> d = n; p -> prev = NULL; p -> next = pd -> bg; (Рис. 10.15
а), в) ) виділяє пам’ять під новий елемент деку, забезпечує запис числа n у поле даних,
значення NULL у поле
вказівника на попередній елемент деку а також вказівника на перший елемент деку
(або NULL) у
поле вказівника на наступний елемент деку. Якщо дек порожній (pd -> bg == NULL), то доданий
елемент буде також останнім елементом деку (pd -> en = p;), інакше
треба зв’язати перший елемент, на який вказує pd -> bg, з
новим елементом деку (pd -> bg -> prev = p;). Нарешті,
треба змінити вказівник на початок деку (pd -> bg = p;).
Останні дії зображено на Рис. 10.15 б), г).
Рис. 10.15 – Додавання елемента до початку деку
Зміни
деку під час дії „взяти елемент з початку деку” (процедура get_bg) зображені на Рис. 10.16. Якщо дек порожній, то виводиться
повідомлення про помилку, а програма аварійно завершує роботу. Якщо ж дек не
порожній, то треба окремо розглядати два випадки: дек складається більше, ніж з
одного елемента (Рис. 10.16 а)-б) ), та дек складається з одного елемента (Рис.
10.16 в)-г) ). Після p = pd -> bg; *pn = p -> d; pd -> bg = pd -> bg -> next; (Рис. 10.16
а), в) ) запам’ятовуємо вказівник на перший елемент деку, читаємо дані з цього
елемента, переміщуємо
вказівник pd -> bg на другий елемент деку або – присвоюємо
йому значення NULL. Якщо
тепер pd -> bg == NULL, тобто дек складався з 1 елемента, треба
вказівнику на останній елемент (pd -> en) присвоїти
значення NULL;, бо дек стає порожнім. Якщо ж дек
складався більш, ніж з 1 елемента, то вказівнику на попередній елемент у новому
першому елементі деку (pd -> bg -> prev) треба
присвоїти значення NULL. Нарешті, в обох випадках потрібно
звільнити пам’ять, яку займав перший елемент деку (free(p)). Останні дії зображено на Рис. 10.16 б), г).
Оскільки
дек є повністю симетричною структурою даних, можна легко отримати функції put_en та get_en. Для цього потрібно у тексті функцій put_bg та get_bg паралельно та одночасно замінити next на prev, prev на next, bg на en та en на bg.
Рис. 10.16 – Взяття елемента з початку деку
Роботу
з деком продемонструємо на прикладі. Нехай вводиться послідовність натуральних
чисел. Треба впорядкувати цю послідовність у порядку зростання. Для розв’язання
цієї задачі скористаємость деком. Будемо зберігати елементи так, щоб найменший
був на початку, а найбільший – у кінці деку. Після введення кожного числа
будемо вставляти його на своє місце у послідовності, таким чином підтримуючи її
впорядкованість. Вставляє елемент у дек функція put_to_deque. Окрім вказівника
на дек pd та числа n параметром цієї підпрограми є поточна
довжина деку k.
/*
dqtst.c */
#include
<stdio.h>
#include
"deque.h"
#define
FALSE 0
put_to_deque(deque
*pd, unsigned k, int n)
{
unsigned j, i=0;
int m, b=FALSE;
while (i<k && !b)
{
i++;
get_bg(pd,&m);
b = m >= n;
if (!b) put_en(pd,m);
else
{
put_bg(pd,m); i--;
}
}
put_bg(pd,n);
for (j=1; j<=i; j++)
{
get_en(pd,&m);
put_bg(pd,m);
}
}
main()
{
deque d;
int n;
unsigned k=0;
init(&d);
printf"Введiть послiдовнiсть додатнiх чисел до <=0\n");
while(1)
{
scanf("%d",&n);
if (n<=0) break;
put_to_deque(&d,k,n);
k++;
}
printf"Впорядкована
послiдовнiсть\n");
while(!empty(d))
{
get_bg(&d,&n);
printf("%d\n",n);
}
}
[ЗМІСТ] [Далі] [Назад] [Початок розділу]