Использование очередей (Queue/Deque) для решения алгоритмических задач на Java

Как всегда, сначала немного базовой теории для понимания того, с чем мы имеем дело. 

Queue — однонаправленная очередь, представляет собой структуру данных, которая строится по принципу FIFO (first-in-first-out). Другими словами, чем раньше элемент был добавлен в коллекцию, тем раньше он оттуда будет удален. 

Выжимка по методам:

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<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 🙂