§ 21. Структуры даных: 21.4. Очередь

§ 21. Структуры даных

21.4. Очередь

Чарга — дынамічная лінейная структура даных, якая захоўвае паслядоўнасць элементаў, дзе дабаўленне новых элементаў адбываецца ў канец чаргі (хвост, tail), а выдаленне — з пачатку чаргі (головы, head).

Чарга арганізавана па прынцыпе FIFO (англ. first in — first out, «першым прыйшоў — першым пайшоў»).

Для очереди определены операции добавления элемента и удаления элемента (прыклад 21.13). По своей организации очередь является линейным списком, добавление в который допускается только в конец списка, а удаление только из начала.

В STL для работы со стеком определен тип данных queue, для работы с которым подключается одноименная библиотека. Описание стека:

queue <тип данных> имя переменной;

У прыкладзе 21.14 перечислены операции, доступные для работы с очередью. Большинство функций для работы с очередью имеют аналоги для типа данных list.

Прыклад 21.15. Задана строка, состоящая из прописных и строчных латинских букв. Вывести буквы парами. В каждой паре первая буква прописная, а вторая строчная. Пары образуются в том порядке, в котором следуют буквы в строке. (В реальности это могут быть, например, фамилии пациентов, ожидающих определенное лекарство, и аптеки, в которые это лекарство поступило.)

Этапы выполнения задания

I. Исходные данные: переменная s — строка, содержащая прописные и строчные буквы.

II. Результат: пары букв и набор букв, оставшийся без пары.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Будем просматривать строку слева направо.

2.1. В очередь будем заносить буквы одного регистра.
2.2. Если появляется символ в другом регистре, то достаем букву из очереди и выводим пару.
2.2.1. Для проверки того, что две буквы относятся к одному регистру, создадим логическую функцию check. Буква x является прописной, если для нее выполняется условие x >= 'A' && x <= 'Z'. Для строчной буквы должно выполняться условие: x >= 'a' && x <= 'z'.
2.2.2. Для вывода букв в нужном порядке создадим функцию vyvod.

3. Если в конце очередь не пуста, то в ней остались символы, которым не хватило пары. Для того чтобы вывести все символы из очереди, будем после вывода удалять символ, пока очередь не станет пустой.

IV. Описание переменных: s – string, q – queue<char>.

Часто используется структура дек — (англ. deque — double ended queue, «двухсторонняя очередь»). Дек можно определять как двухстороннюю очередь, или как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения. Эта структура данных одновременно работает по двум способам организации данных: FIFO и LIFO (прыклад 21.16).

Структуру даных чарга можна ўявіць сабе як чаргу да ўрача, дзе новыя пацыенты ўстаюць у канец чаргі, а прыём пацыентаў ажыццяўляецца з пачатку чаргі. На аснове чаргі арганізавана апрацоўка падзей у Windows. Калі карыстальнік аказвае якое-небудзь дзеянне на дадатак, то паведамленне пра гэта ставіцца ў чаргу, і толькі калі будуць апрацаваны паведамленні, якія прыйшлі раней, дадатак выканае неабходнае дзеянне.

Прыклад 21.13. Дабаўленне і выдаленне элемента ў чарзе:

Прыклад 21.14. Аперацыі для тыпу даных queue.

Функцыя	Дзеянне
front	Доступ да першага элемента
back	Доступ да апошняга элемента
empty	Правярае адсутнасць элементаў
size	Вяртае колькасць элементаў
push	Устаўляе элемент
pop	Выдаляе элемент

Прыклад 21.15.

Калі на ўваход пададзены радок ZHJKqwertASDyuiopQWERTYUIOPasdf, то павінны атрымацца наступныя пары: Zq Hw Je Kr At Sy Du Qi Wo Ep Ra Ts Yd Uf. Літары I O P застануцца без пары.

V. Праграма:

#include <iostream>

#include <string>

#include <queue>

using namespace std;

bool check(char x, char y)

{

bool u1 = x >= 'A' && x <= 'Z';

bool u2 = y >= 'A' && y <= 'Z';

bool u3 = x >= 'a' && x <= 'z';

bool u4 = y >= 'a' && y <= 'z';

return (u1 && u4 || u2 && u3);

}

void vyvod (char x, char y)

{

if (x < y)

cout << x << y << " ";

else

cout << y << x << " ";

}

int main()

{

string s;

cout << "s = " ;

cin >> s;

int n = s.length();

queue <char> q;

for (int i = 0; i < n; i++){

if (q.empty())

q.push(s[i]);

else

if (check(s[i], q.front())){

vyvod(s[i], q.front());

q.pop();

}

else

q.push(s[i]);

}

cout << endl;

if (q.empty())

cout << "u vseh ect para";

else{

cout << "bez pary:" << endl;

while (!q.empty()){

cout << q.front();

q.pop();

}

return 0;

}

VI. Тэсціраванне.

VII. Аналіз вынікаў. Разгледзім прыклад для радка wwerTyGJLqTT. У першым радку — бягучы сімвал, у другім — стан чаргі.

w	w	e	r	T	y	G	J	L	q	T	T
w	ww	eww	reww	rew	yrew	yre	yr	y	qy	q

Прыклад 21.16. Дабаўленне і выдаленне элемента ў дэку:

У STL для работы з дэкам вызначаны тып даных deque, для работы з якім падключаецца аднайменная бібліятэка. Функцыі для работы з дэкам можна паглядзець ў Дадатку да главы 1.1.