Лабораторная работа №14. Коллекции

  1. Стек (англ. stack — стопка; читается стэк) - абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»), элемента добавляются и удаляются только с начала - вершины стека.
    Задача: Дана строка, содержащая скобки трёх видов (круглые, квадратные и фигурные) и любые другие символы. Проверить, корректно ли в ней расставлены скобки. Например, в строке ([]{})[] скобки расставлены корректно, а в строке ([]] — нет. 
    Указание: задача решается однократным проходом по символам заданной строки слева направо; для каждой открывающей скобки в строке в стек помещается соответствующая закрывающая (используем push), каждая закрывающая скобка в строке должна соответствовать скобке из вершины стека, (для того, чтобы получить значение из вершины стека, используем top, при этом скобка с вершины стека снимается, используем pop); в конце прохода стек должен быть пуст (используем size).
  2. Двусвязная очередь (дэк, от англ. deque - double ended queue; двухсторонняя очередь, очередь с двумя концами) - структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец;
    Задача: Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5.
    Указание: идея решения состоит в использовании трёх очередей (deque), в которых хранятся числа, в 2 (3, 5) раз большие уже напечатанных, но не напечатанные; всякий раз из очередей выбирается наименьшее, расположенное в вершине одной из очередей значение (front), оно печатается и удаляется из очереди (pop_front), а в хвосты очередей добавляются соответствующие кратные ему (push_back); процесс запускается с печати числа 1.
  3. Ассоциативный массив std::map — отсортированный ассоциативный контейнер (или ассоциативный массив), который содержит пары ключ-значение с неповторяющимися ключами.
    Задача: Дана строка, содержащая слова, разделённые знаками препинания и пробелами. Создать map<string, size_t>, ключом в которой является слово, а значением - количество повторений. В функции main() вывести на консоль все элементы массива.
    Подсказка: чтобы упростить задачу, рекомендуется сперва создать функцию vector<string> toWords(string);, которая при помощи методов класса string создаёт вектор из слов. Затем можно приступить к реализации функции map<string, size_t> words(string);, которая сперва обращается к  vector<string> toWords(string);, а затем при помощи emplace формирует ассоциативный массив.
  4. Множество элементов: set

    Set это контейнер, который содержит упорядоченный набор уникальных объектов

    Найти самое повторяющееся слово в строке:

    • создаём класс
      class wordFrequency {
      public:
      	string word;
      	size_t frequency;
      	wordFrequency(string w, size_t f) :word(w), frequency(f) {}
      };
      
    • Перегружаем операцию сравнения (обратите внимание на сравнение строк в лексикографическом порядке)
      bool operator<(const wordFrequency &a, const wordFrequency &b)
      {
      	if (a.frequency == b.frequency)
      		return a.word < b.word;
      	return a.frequency > b.frequency;
      }
      
    • Создаём функцию set<wordFrequency> fDictionary(string); В функции main() вывести на консоль самое повторяющееся слово, если таковых несколько, вывести все.