§ 9.6. Структуры данных дек, стек, очередь и куча

Школьный курс python
Содержание

Структура данных deque (дек)

Структуры данных, которые мы рассмотрим на этом уроке, объединены тем, что создаются на основе массивов для эффективного решения определенного круга задач. В язык C++ структуры данных стек, очередь и куча можно реализовать на основе классов контейнеров vector и deque. С вектором мы познакомились ранее, настало время познакомиться с деком.
Дек, двусвязная очередь (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов массива. Это позволяет многие задачи решать непосредственно с помощью дека, абстрагируясь до нужной структуры данных.

Контейнер deque очень похож на vector. deque также является последовательным контейнером произвольного доступа, следовательно, поддерживается индексация ([], at()), методы front() и back(), а также большинство других методов класса vector. Дек имеет аналогичные итераторы, в том числе, реверсивные. Но, в отличие от vector, расширение deque происходит более эффективно, т. к. перераспределение памяти не происходит (элементы не переносятся в новую область, в случае переполнения текущей). Дек более сложная структура данных, его элементы не всегда находятся в одной области памяти. Если вектор можно сравнить с С-массивом, то дек можно представить как комплект нескольких С-массивов (один или более), используемых как единый объект.
Главное отличие deque от (как vector) в том, что он открыт с обоих концов. Вставка элементов в начало и в конец deque осуществляется очень быстро. Но обход дека с помощью итераторов, будет осуществляться медленнее, чем обход вектора. При каждой вставке и удалении не в начало или не в конец дека приведет к недействительности итераторов как начала, так и конца (в том числе, указателей и ссылок на остальные элементы). Если вставка производится в начале или в конце массива, то недействительными окажутся только итераторы, ссылки же и указатели останутся в силе.
Для контейнера deque не определены методы работы с объемом capacity() и reserve(), но метод shrink_to_fit() использовать можно. Связано это с тем, что при уменьшении размера дека, объем его не уменьшается. Этот метод необязательно выполняет операцию уменьшения capacity() до size().

Таблица 1. Методы-модификаторы контейнера deque
Метод Описание
clear Очищает контейнер (объем не будет изменен)
insert Вставляет элементы
emplace Создает элементы на месте. Не использует копирование или перемещение.
emplace_back Создает элементы на месте в конце массива
emplace_front Создает элементы на месте в начале массива
erase Удаляет элементы
push_back Добавляет элемент в конце
pop_back Удаляет последний элемент
push_front Добавляет элемент в начале
pop_front Удаляет первый элемент
resize Изменяет размер массива
assign Заменяет содержимое на новое

Решим с помощью дека следующую задачу.
Задача 1. Дан массив ar и числа m и n, определяющие позиции элементов в массиве ar (m < n). Определить на этом отрезке минимальный элемент. Задачу эту решить с помощью дека.

Программа 9.6.1
#include <iostream>
#include <deque>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int RND(int, int);
int Min(deque<int>&, int, int);

int main() {
    size_t m, n;
    cout << "m = "; cin >> m;
    cout << "n = "; cin >> n;
    deque<int> ar;
    // Заполняем и выводим исходный массив
    for (size_t i = 0; i < 50; i++) {
        ar[i] = RND(10, 99);
        cout << ar[i] << " ";
    }
    cout << '\n' << Min(ar, m, n) << endl;
    return 0;
}

// Функция получения случайного числа
int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

// Решение задачи
int Min(deque<int> &mas, int x, int y) {
    // определяем срез [first; last]
    // c помощью итераторов:
    auto first = mas.begin() + x;
    auto last  = mas.begin() + y;
    // Создаем пустой дек
    deque<int> temp;
    // помещаем в конец дека первый эл-т
    temp.push_back(first[0]);
    while (first <= last) {
        // переходим к следующему
        ++first;
        // выясняем с какой стороны
        // вставить этот элемент?
        if (*first > temp[0]) {
            temp.push_back(*first);
        } else {
            temp.push_front(*first);
        }
    }
    // минимальный находится в вершине
    return temp[0];
}

Структура данных stack (стек)

На основе дека можно моделировать структуры данных стек и очередь. Для этого в C++ используются контейнеры-адаптеры. Шаблонный класс контейнера-адаптера stack представляет собой надстройку над базовым контейнером и предоставляет только определенный набор функций, характерный для стека.
Стек - это структура данных, в которой элементы добавляются и удаляются в вершине стека. Массив элементов, организован по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Такую структуру можно представить как стопка тарелок (или книг): доступ ко второй (сверху) тарелке можно получить только после того, как будет взята первая тарелка.

В основу адаптера stack положен (по умолчанию) контейнер deque.
Для stack определены следующие методы:

Таблица 2. Методы контейнера-адаптера stack
Метод Описание
empty Возвращает true, если stack пуст
size Количество элементов в стеке
top Доступ по ссылке к верхнему элементу
push Вставляет элемент в вершину
emplace Создание элемента на месте с добавлением в вершину
pop Удаляет элемент с вершины
swap Обменивает содержимое

Помимо этих методов, поддерживаются все операции сравнения и операция присваивания.
Рассмотрим одну из задач, которую легко можно решить с помощью стека.
Задача 2. В постфиксной записи арифметического выражения операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операций для своего чтения.
Дано выражение в постфиксной записи, содержащее числа, операции +, , *. Вычислите значение выражения, записанного в постфиксной форме (называемой также обратной польской записью). Числа и символы должны разделяться одним пробелом.

Программа 9.6.2
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// Извлекает за раз два элемента из вершины
void to_extract(int&, int&, stack<int>&);
// Немного упрощенная функция, которая возвращает
// ссылку на массив слов (см. программу 9.4.6)
vector<string> &word_to_ar (vector<string>&, string &);

int main() {
    string S;
    cout << "Введите строку, изображающую"
            " арифметическое выражение:"
         << endl;
    // Получаем строку
    getline(cin, S);
    // Получаем массив слов
    vector<string> words;
    words = word_to_ar(words, S);
    // Создаем пустой стек
    stack<int> stc;
    // Идем по массиву слов
    // и выполняем операции в стеке
    for (auto &r : words) {
        if (r == "*") {
            int a, b;
            to_extract(a, b, stc);
            stc.push(a * b);
        }
        else if (r == "+") {
            int a, b;
            to_extract(a, b, stc);
            stc.push(a + b);
        }
        else if (r == "-") {
            int a, b;
            to_extract(a, b, stc);
            stc.push(a - b);
        } else {
            // Отправляем в стек
            // с преобразованием слова в целый тип
            stc.push(stoi(r));
        }
    }
    cout << stc.top() << endl;
    return 0;
}

void to_extract(int &m, int &n, stack<int> &st) {
    m = st.top();
    st.pop();
    n = st.top();
    st.pop();
}

vector<string> &word_to_ar(vector<string> &vec, string &s) {
    string word = "";
    for (size_t i = 0; i < s.size(); i++) {
        if (s[i] != ' ') {
            word += s[i];
            if (i + 1 == s.size())
                vec.push_back(word);
        } else {
            vec.push_back(word);
            word = "";
        }
    }
    return vec;
}

Ввод/вывод

Введите строку, изображающую арифметическое выражение:
5 5 4 + 10 * +
95

Структура данных queue (очередь)

Очередь — это структура данных, в которой добавление элемента возможно лишь в конец очереди, а выборка — только из начала очереди, при этом выбранный элемент из очереди удаляется. Массив элементов, организован по принципу FIFO (англ. First In — First Out, «первый пришёл — первый вышел»).

Для реализации этой структуры данных в C++ используется адаптер queue. В основу адаптера queue положен (по умолчанию) контейнер deque.
Для queue определены следующие методы:

Таблица 3. Методы контейнера-адаптера queue
Метод Описание
empty Возвращает true, если очередь пуста
size Количество элементов в очереди
front Доступ по ссылке к первому элементу
back Доступ по сылке к последнему элементу
push Вставляет элемент в конце очереди
emplace Создание элемента на месте в конце очереди
pop Удаляет первый элемент
swap Обменивает содержимое

Помимо этих методов, поддерживаются все операции сравнения и операция присваивания.
Очередь нашла свое применение в алгоритмах так называемого обхода дерева (или графа) в ширину (англ. breadth-first search, BFS). Не вдаваясь глубоко в теорию графов, рассмотрим пример такой задачи на основе задачи ЕГЭ.
Задача 3. Вася, решая задачи формата ЕГЭ, дошел до задачи об исполнителе:
«У исполнителя Калькулятор две команды:

  1. прибавь 3
  2. умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4».
graf
Далее, в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел a и b построить программу наименьшей длины получения числа b из числа a. Напишите программу, которая по заданным числам a и b вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из a число b. Общее количество команд не должно превышать 10.

Программа 9.6.3
#include <iostream>
#include <queue>
using namespace std;

int main() {
	int a, b, i = 0;
	cout << "Корень => "; cin >> a;
	cout << "Искомая вершина => "; cin >> b;
	queue<int> rob;
	bool f = false;
	// Помещаем исходную вершину в очередь
	rob.push(a);
	// Пока очередь не пуста
	while (!rob.empty()) {
		// Берем элемент из очереди (посещаем вершину)
		int p = rob.front();
		rob.pop();
		// Определяем потомков и ставим их в очередь
		rob.push(p * 4);
		rob.push(p + 3);
		i += 2;
		// Если найдена вершина с необходимым значением - выходим
		if (p * 4 == b || p + 3 == b) {
			f = true;
			break;
		}
		// Также выходим, если достигли лимита
		if (rob.size() > 1024)
			break;
	}	
	// Определяем количество команд
	if (f) {
	int j = 0;
		while (i > 1) {
			++j;
			i /= 2;
		}
		cout << "Наименьшее число команд = "
			 << j << endl;
	} else
		cout << "Алгоритм не найден" << endl;
	return 0;
}

Структура данных heap (куча). Очередь с приоритетом (priority queue)

heap

Куча (другие названия: двоичная куча, пирамида, сортирующее дерево) — это структура данных представленная в виде дерева. В классической куче нет ограничений на число потомков, но на практике их всегда два. Поэтому такую кучу называют двоичной кучей. Она удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ A ≥ ключ B. Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (максимальными кучами).
Для двоичного дерева кучи должны выполняться три условия:

  1. Значение в любой вершине не меньше, чем значения её потомков.
  2. Глубина всех листьев (расстояние до корня) отличается не более чем на 1 слой.
  3. Последний слой заполняется слева направо без «дырок».

Для реализации кучи можно взять любой последовательный контейнер или C-массив. Корневой элементA[0], а потомки элемента A[i]A[2*i+1] и A[2*i+2].

Тогда индексы, в виде дерева, можно представить следующим образом:

Куча является максимально эффективной реализацией абстрактного типа данных, который называется очередью с приоритетом (priority queue). Очередь с приоритетом применяется в программах, которые включают в себя поиск максимального (или минимального) элемента в некотором массиве данных (например, самые активные пользователи социальной сети). Но это не единственное её применение. С помощью очереди с приоритетом можно организовать планировщик задач, поиск оптимальных путей, прогнозирование событий и многие др. задачи.

Функции для работы с кучей в C++ разработаны в библиотеке algorithm (см. здесь).
priority_queue

priority_queue (наряду с очередью и стеком) является адаптером контейнеров. В основе очереди с приоритетом находится, по умолчанию, контейнер vector (это может быть изменено, как и для других адаптеров). priority_queue предупреждает случайное аннулирование кучи. Элементы очереди сортируются автоматически по убыванию (max-куча). Направление сортировки можно изменить с помощью компаратора.
Для priority_queue (заголовок - queue) определены следующие методы:

Таблица 3. Методы контейнера-адаптера priority_queue
Метод Описание
empty Проверяет пуст ли базовый контейнер
size Количество элементов в очереди
top Доступ по ссылке к вершине
push Вставляет элемент и сортирует базовый контейнер
emplace Создаёт элемент на месте и сортирует базовый контейнер
pop Удаляет элемент в вершине
swap Обменивает содержимое

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

Программа 9.6.4
#include <iostream>
#include <vector>
#include <queue> // Обратите внимание!
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int RND(int, int);

int main() {
    vector<int> ar;
    ar.reserve(50);
    for (size_t i = 0; i < 50; i++) {
        ar.push_back(RND(10, 99));
        cout << ar[i] << " ";
    }
    priority_queue<int, vector<int>, greater<int>> Q;
    cout << endl;
    for (size_t i = 0; i < ar.size(); i++)
        Q.push(ar[i]);
    while (!Q.empty()) {
        cout << Q.top() << " ";
        Q.pop();
    }
    cout << endl;
    return 0;
}

int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

В priority_queue C++ реализована max-куча. В ней, как уже было сказано, элементы упорядочены от большего к меньшему. Чтобы изменить направление сортировки, в шаблонном параметре конструктора передаётся, помимо типа элементов, еще два необязательных элемента: тип базового контейнера и компаратор, изменяющий направление сортировки на обратное (см. стр. 18 в программе 9.6.4; в качестве компаратора выступает встроенная функция сравнения или функтор - greater).

Этот способ также накладывает ограничение на использование контейнеров. Так, например, в этой программе нельзя заменить вектор на array, поскольку последний не поддерживает операцию insert.

Второй вариант основан на использовании библиотеки обобщенных алгоритмов.

Программа 9.6.5
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int RND(int, int);

int main() {
    vector<int> ar;
    ar.reserve(50);
    for (size_t i = 0; i < 50; i++) {
        ar.push_back(RND(10, 99));
        cout << ar[i] << " ";
    }
    // Создаем max-кучу на месте
    cout << "\nВыводим кучу:\n";
    make_heap(ar.begin(), ar.end());
    for (auto r : ar) cout << r << " ";
    // Производим сортировку по возрастанию
    cout << "\nВыводим отсортированный массив:\n";
    sort_heap(ar.begin(), ar.end());
    for (auto r : ar) cout << r << " ";
    cout << endl;
    return 0;
}

int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

После выполнения сортировки, массив утрачивает свойство кучи.
Решим следующую задачу.
Задача 4. В игре участвуют N игроков (N >= 3). В каждом раунде пользователи по очереди бросают кость. Результаты суммируются по каждому раунду, количество которых не ограничено. По итогам игры выявляются три участника с максимальным результатом. Абсолютным победителем является игрок, первым набравший более 20 очков.

Программа 9.6.6
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono;

int RND(int, int);
int game(vector<pair<int, int>>&);

int main() {
    size_t n;
    cout << "Введите количество игроков: ";
    cin >> n;
    // Массив игроков
    vector<pair<int, int>> gmrs;
    gmrs.reserve(n);
    // Очки
    int Sum = 0;
    // Регистрация игроков
    for (size_t i = 0; i < n; i++)
        gmrs.emplace_back(0, i);
    // Играем
    while (Sum <= 20) Sum = game(gmrs);
    // Создаем функциональный объект (компаратор)
    // как функцию сравнения. Это удобно, 
    // если одна и та же лямбда используется несколько раз
    auto cmp = [](auto &p1, auto &p2) {
        return p1.first > p2.first;
    };
    // Трансформируем массив игроков в кучу
    make_heap(gmrs.begin(), gmrs.end(), cmp);
    // Выполняем сортировку
    sort_heap(gmrs.begin(), gmrs.end(), cmp);
    for (int i = 0; i < 3; i++) {
        cout << "Игрок №"
             << gmrs[i].second + 1
             << "\nРезультат => "
             << gmrs[i].first
             << endl;
    }
    return 0;
}

int game(vector<pair<int, int>> &mas) {
    int Max = 0;
    for (auto &r : mas) {
        int S = r.first + RND(1, 6);
        r = {S, r.second};
        if (S > Max) Max = S;
    }
    return Max;
}

int RND(int a, int b) {
    int seed = system_clock::now().time_since_epoch().count();
    static default_random_engine rnd(seed);
    static uniform_int_distribution<int> uid(a, b);
    return uid(rnd);
}

Возможный вывод

Введите количество игроков: 6
Игрок №2
Результат => 24
Игрок №5
Результат => 23
Игрок №6
Результат => 18

Приложение

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.