§ 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.