Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело.
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 :)
Комментарии (7)
E_Sarf
02.08.2024 16:30Разбор неплохой, но в данной задаче у класса Deque используются только те методы, которые есть у класса Stack. Получается, решается она не только через двунаправленную очередь, для решения подошёл бы и экземпляр стека, какого-то удобства одного относительно другого тут не видно. Интереснее было бы включить еще немного информации про различия и показать, когда лучше использовать Stack, а когда имплементацию Deque, раз уж на то пошло :)
akozyrenko Автор
02.08.2024 16:30Спасибо:)
Deque использовала потому, что Stack является устаревшим по спеке.
dyadyaSerezha
02.08.2024 16:30Именно так. Кроме того, неверно (неполно, по крайней мере) описано отличие Deque от Queue. Главное отличие (что отражено и в названии) - это возможность вставлять и брать элементы с обоих концов, а не то, что это и стек. Стек тут идёт до кучи, как подмножество функционала просто с общепринятыми для стека названиями методов.
akozyrenko Автор
02.08.2024 16:30Перечитала, действительно, неполно было описано отличие. Добавила, спасибо:)
Rusrst
Я так и не понял почему не стек? Это классическое решение для такой задачи, насколько я знаю.
akozyrenko Автор
Ответила ниже, но продублирую - Deque использовала потому, что Stack является устаревшим по спеке.
aleksandy
Потому что стэк - это LIFO-очередь, чем, собственно, Deque и является.
Потому что в java.util.Stack присутствует ненужная в данном случае синхронизация, что сказывается на производительности.