Использование очередей (Queue/Deque) для решения алгоритмических задач на Java
Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело.
Queue — однонаправленная очередь, представляет собой структуру данных, которая строится по принципу FIFO (first-in-first-out). Другими словами, чем раньше элемент был добавлен в коллекцию, тем раньше он оттуда будет удален.
Выжимка по методам:
Выбрасывает исключение | Возвращает спец.значение | |
Вставка | booelan add (e) | boolean offer (e) |
Удаление | E remove () | E poll () |
Получение | E element | E peek () |
Deque (читай как «дэк») — двунаправленная очередь, которая может работать и как обычная однонаправленная очередь по принципу FIFO, и как Stack по принципу LIFO (last-in-first-out).
Deque — интерфейс, который расширяет Queue (тоже интерфейс, очевидно, хех). Соответсвенно, у него есть те же методы, что и Queue + свои, которые работают по аналогии с табличкой выше, только добавляются окончания Last/First, чтобы было понятно, куда вставлять и откуда получать/удалять элементы — в конец очереди или из конца (addLast, offerFirst и тд)
Также Deque содержит методы, аналогичные методам Stack:
push (e) — добавляет элемент в начало очереди, может выбрасывать исключения (аж 4 штуки, см. спеку) — аналог addFirst ()
E pop () — удаляет элемент из начала очереди, выбрасывает NoSuchElementException, если очередь пустая. — аналог removeFirst ()
E peek () — возвращает первый элемент или null, если его нет. — аналог peekFirst ().
На практике очереди используются в разы реже, чем другие коллекции. Но вот для решения алгоритмических задач очень удобны/эффективны.
Итак, погнали, условие задачи здесь: https://leetcode.com/problems/valid-parentheses/description/
Кратко: дана строка, состоящая из символов '(', ')', '{', '}', '[' ,»]». Нужно определить, валидная ли она. Строка валидная, если:
Каждая открывающая скобка имеет такую же закрывающую: {)- неверно,»{}[]()» — верно
Порядок открывающих и закрывающих скобок правильный: }{)( — неверно, {(}) — тоже неверно, ({}) — верно.
Для решения этой задачки отлично подходит использование двунаправленной очереди — Deque. Почему? Проще рассмотреть на конкретном примере. Допустим, на вход мы получили строку, состоящую из следующих символов:»([])». Строка валидна, так как удовлетворяет условиям, что каждая открывающаяся скобка имеет аналогичную закрывающуюся и в нужной последовательности. Осталось это доказать при помощи Deque.
В Deque мы будем добавлять только закрывающиеся скобки, когда встречаем нужную открывающуюся в заданной строке. Другими словами:
если придет элемент »(», добавим »)»,
если »{», то »}»
если »[», то »]».
А если будем встречать закрывающуюся скобку в строке, то будем проверять, совпадает ли она с той, что последней встала в очередь.
Итак, в нашем кейсе первый символ — это »(», значит добавляем в очередь »)». Дальше встречаем символ »[», значит добавляем в очередь »]». Дальше идет символ »]» — закрывающаяся скобка, значит ничего не добавляем, а получаем (а точнее удаляем методом pop ()) последний элемент из очереди и сверяем с текущим.»]» = »]», совпадает. Переходим к следующему элементу в строке — это »)», он совпадает с тем элементом, что остался в очереди »)».
Символов не осталось, очередь пустая, а значит наша строка валидна. Полный алгоритм выглядит так:
public boolean isValid(String s) {
Deque checkDeque = new ArrayDeque();
for (char sym: s.toCharArray()) {
if (sym == '(') {
checkDeque.push(')');
} else if (sym == '{') {
checkDeque.push('}');
} else if (sym == '[') {
checkDeque.push(']');
} else if (checkDeque.isEmpty() || checkDeque.pop() != sym) {
return false;
}
}
return checkDeque.isEmpty();
} Хотела рассмотреть в этой же статье использование очередей для решения задач с обходом деревьев и сравнить этот подход с рекурсией. Но, похоже, под это дело организую отдельную статью:)
Кстати, сделала свой телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там будет больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно — жду здесь — t.me/crushiteasy:)
