Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело.
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).
Фиксируем ключевое:
Queue - однонаправленная очередь, добавление элементов в конец, получение/удаление из начала
Deque - двунаправленная очередь, добавление, получение, удаление и в конец, и в начало
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<Character> 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 :)
