Будет 5 статей по темам:

Последовательные контейнеры
Ассоциативные контейнеры
Стеки и очереди - они же адаптеры(Вы тут)
Функциональные объекты
Основные алгоритмы - последние будут иногда проскакивать во всех статьях выше

Наполнение статьи про адаптивные контейнеры:

1) std::stack - односторонняя очередь + пример задача и ее решение с разбором

2) std::queue - двусторонняя очередь + пример задача и ее решение с разбором

3) Задачи к решению

Это будет наиболее короткая и понятная статья, на LeetCode довольно много задач, которые гораздо проще и лучше получится решать с использованием обоих этих классов, не уверен что обоих сразу, но по-отдельности получается отлично.

Статья получится очень короткой, если я просто перечислю pop, top, front поэтому добавлю по-небольшому разбору некоторых задач с LeetCode.

Почему адаптивные контейнеры?

Дело в том, что любой из этих классов довольно просто повторить при помощи любого последовательного(VECTOR, LIST, DEQUE). Из этого и термин адаптивный контейнер - он подстраивает под себя некоторый функционал классов контейнеров, что в определенной комбинации решает задачи максимально красиво и быстро.

1) Последний зашел - первый вышел - std::stack

Краткое описание: структура данных имеющая всего 2 операции pop - удаление с вершины и push - добавление на вершину. Реализует принцип LIFO (LAST IN - FIRST OUT) последним зашел - первый вышел. Представьте, что вы складываете книги в коробку - при добавлении нескольких книг, взять вы сможете только самую верхнюю.

Памятка по функциям:

pop() - удаляет элемент с вершины.
push() - добавляет элемент на вершину.
top() - позволяет получить элемент с вершины не убирая его.
кстати, top() возвращает ссылку, поэтому мы можем изменить значение элемента получаемого на верхушке - в некоторых задачах это может пригодиться stack.top() = 10;
empty() - проверка на то, пустой ли std::stack.
size() - возвращает длину std::stack.

Скорости:

push() - O(1)
pop() - O(1)

Решение задачи 20. Valid Parentheses:

Дается строка s состоящая из следующих символов '(', ')', '{', '}', '[' и ']', определить, является ли входная строка допустимой.

Входная строка действительна, если:

1) Открытые скобки должны быть закрыты однотипными скобками.

2) Открытые скобки должны быть закрыты в правильном порядке.

3) Каждой закрывающей скобке соответствует открытая скобка того же типа.

Одно из самых оптимальных решений выглядит так:

bool isValid(string s) {
  stack<char> stack;
        
        for (char c : s) {
            if(c == '(' || c == '[' || c == '{') 
                stack.push(c);
            else if(c == ')' && !stack.empty() && stack.top() == '(') 
                stack.pop();
            else if(c == ']' && !stack.empty() && stack.top() == '[') 
                stack.pop();
            else if(c == '}' && !stack.empty() && stack.top() == '{') 
                stack.pop(); 
            else
                return false; 
        }
        
        return stack.empty(); 
    }

Итак, думаю все очевидно, есть два момента которые нужно прояснить:

1) Почему бы не использовать вектор?
2) Почему мы возвращаем stack.empty()?

Первый пункт: посмотрите на функцию stack.top() - для того чтобы обработать ситуацию используя вектор - пришлось бы слишком долго париться. В то время как используя stack.top() и заранее прикрываясь !stack.empty() - мы гарантируем обращение по существующему индексу, в то время как используя вектор - мы можем легко ошибиться.

Второй пункт: он больше по задаче и не всем интересен, но если элементов будет 0, то мы вернем - true, если элемент будет всего 1, то мы вернем - false и все благодаря этой функции.

Понимаю, задача не очень интересная, но это если вы знаете про существование std::stack(), в другом случае - она вам крутанет голову.

Как вывести элементы stack:

Поскольку у вас нету доступа по индексу и итераторов begin(), end() - вывод будет чистить вашу структуру начисто:

    stack<int> stack;
    
    stack.push(1);   // Добавляем элементы в стек
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    
    // Выводим элементы стека
    while (!stack.empty()) {
        cout << stack.top() << " ";   // Выводим верхний элемент стека
        stack.pop();   // Удаляем верхний элемент стека
    }

2) Первый пришел - первый ушел - std::queue

Краткое описание: структура данных имеющая всего 2 операции pop - удаление элемента в начале и push - добавление в конец. Реализует принцип FIFO (FIRST IN - FIRST OUT) первый зашел - первый вышел. Представьте, что вы на машине заехали в очень узкий однополосный тоннель все что вы можете сделать - это заехать в него с конца и выехать с начала. **Начало и конец определены в относительно траектории вашего движения и конец - это относительно всей очереди**.

Памятка по функциям:

front() - возвращает первый элемент очереди. В очереди отсутствует begin().
back() - возвращает последний элемент очереди. В очереди отсутствует end().

push() - вставляет элемент в конец.
pop() - удаляет элемент в начале.

empty() - проверяет пустая ли очередь.
size() - возвращает размер очереди.

Скорости:

front() - O(1)
back() - O(1)

push() - O(1)
pop() - O(1)

Решение задачи 239. Sliding Window Maximum:

Вам дан массив целых чисел nums, есть скользящее окно размера k, которое перемещается из самого левого края массива в самый правый. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Вернуть максимальное скользящее окно.

Объяснение: Вам нужно перетаскивать окно из трех элементов на +1 ячейку и находить среди трех значений наибольшее число, которое добавлять в итоговый output.
Почему не получится решить эту задачу перебором? - в задаче присутствует ограничение по времени, а их там [от 1 до 10^5] включительно.

Для общего развития - эту задачу можно решить без очереди через pair<iter, number> и max(pair<>, max(pair<>, pair<>)) - но тогда вам придется решать кучу накладных проверок и решать проблемы, которые при решении через queue не появились бы.

Решение:

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> r;// сюда сохраняем результат
    deque<int> winIter;// тут будет по три итератора для окна

    // пробегаемся по всем элементам массива
    for (int i = 0; i < nums.size(); i++) {
        // проверяем, если первый элемент в очереди выходит за пределы текущего окна
        // начальный для k == 3 - i == 2 и i == 1 и i == 0 - winIter.front() == не найден
        // следующий для k == 3 - i == 3 и i == 2 и i == 1 - winIter.front() == не найден
        // следующий для k == 3 - i == 4 и i == 3 и i == 2 - winIter.front() == 4 - 3 = 1
        if(!winIter.empty() && winIter.front() == i - k) {
            winIter.pop_front(); // удаляем его из очереди
        }

        // здесь мы удаляем индексы итераторов, если число лежащее справа меньше впереди идущего
        while(!winIter.empty() && nums[winIter.back()] < nums[i]) {
            winIter.pop_back();
        }

        winIter.push_back(i); // добавляем текущий элемент в очередь

        // поскольку у нас проверка - самый верхний if
        // индекс последнего итератора всегда больше, кроме i == k, поэтому >=
        // k - 1, потому что i считается начиная с нуля, а k с единицы
        if(i >= k - 1) {
            r.push_back(nums[winIter.front()]);
        }
    }

    return r;
}

Как вывести элементы queue:

Поскольку у вас нету доступа по индексу и итераторов begin(), end() - вывод будет чистить вашу структуру начисто:


    queue<int> queue1;
    queue<int> queue2;
    // Добавляем элементы в очередь
    queue1.push(10);
    queue1.push(20);
    queue1.push(30);
    queue1.push(40);
    queue1.push(50);

    for(int i = 0; i < (int)queue1.size(); i++){
        queue1.push(queue1.front());
        cout << queue1.front() << " ";
        queue1.pop();
    }

    while (!queue1.empty()) {
        cout << queue1.front() << " "; //Выводим первый элемент
        queue1.pop(); // Удаление первого элемента
    }

    // теперь если мы захотим вывести элементы в обратном порядке
    // то у нас ничего не получится, ведь очередь пустая после операции pop
    // есть два варианта решения того, что очередь становится пустой
    
    // 1 вариант с дополнительной очередью
    while (!queue1.empty()) {
        queue2.push(queue1.front());
        cout << queue1.front() << " "; //Выводим первый элемент
        queue1.pop(); // Удаление первого элемента
    }
    // если будете использовать здесь только одну очередь - попадете в бесконечный цикл с проверкой на пустоту
    
    // 2 вариант
    for(int i = 0; i < (int)queue1.size(); i++){// знаем размер и делаем проверку на пустоту
        queue1.push(queue1.front());// добавляем элементы сначала в конец
        cout << queue1.front() << " ";
        queue1.pop();// удаляем элементы из начала.
    }

3) Задачи к решению

Попробуйте реализовать обе структуры используя противоположную, то есть:

225. Implement Stack using Queues
232. Implement Queue using Stacks.

Разобравшись с ними вы навсегда себе в голову вложите их суть, поймете как из двусторонней сделать односторонюю и наоборот.

Базовый набор для решения задач на LeetCode/Codeforces, ч.3 Адаптивные Контейнеры C++