Будет 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.
Разобравшись с ними вы навсегда себе в голову вложите их суть, поймете как из двусторонней сделать односторонюю и наоборот.