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

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 :)