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