Using queues to solve algorithmic problems (Queue

As always, first a little basic theory to understand what we are dealing with.

Queue – a one-way queue, is a data structure that is built on the FIFO (first-in-first-out) principle. In other words, the earlier an element was added to a collection, the earlier it will be removed from there.

Summary of methods:

Deque (read as “deck”) is a bidirectional queue that can work both as a regular unidirectional queue based on the FIFO principle, and as a Stack based on the LIFO (last-in-first-out) principle.

Deque is an interface that extends Queue (also an interface, obviously, heh). Accordingly, it has the same methods as Queue + its own, which work similarly to the table above, only the Last/First endings are added, so that it is clear where to insert and where to get/remove elements from – to the end of the queue or from the end (addLast, offerFirst, etc.)

Deque also contains methods similar to those of Stack:

• push(e) – adds an element to the beginning of the queue, can throw exceptions (as many as 4, see spec) – analogous to addFirst()

• E pop() – removes an element from the beginning of the queue, throws NoSuchElementException if the queue is empty. – similar to removeFirst()

• E peek() – returns the first element or null if there is none. – analogous to peekFirst().

In practice, queues are used much less frequently than other collections. But they are very convenient/effective for solving algorithmic problems.

So, let's go, the problem statement is here: https://leetcode.com/problems/valid-parentheses/description/

Briefly: given a string consisting of the characters '(', ')', '{', '}', '[‘ , ‘]'. It is necessary to determine whether it is valid. The string is valid if:

• Every opening parenthesis has a matching closing parenthesis: {) – incorrect, “{}[]()” – right

• The order of opening and closing brackets is correct: }{)( is incorrect, {(}) is also incorrect, ({}) is correct.

A bidirectional queue, Deque, is a great solution to this problem. Why? It's easier to see with a specific example. Let's say we received a string consisting of the following characters as input: “([])”. The string is valid because it satisfies the conditions that each opening parenthesis has a similar closing parenthesis and in the right sequence. It remains to prove this using Deque.

In Deque we will only add closing parentheses when we encounter the required opening parenthesis in a given string. In other words:

• if the element “(” comes, we add “)”,

• if “{” then “}”

• If “[», то «]”.

And if we encounter a closing bracket in a line, we will check whether it matches the one that was the last one in the queue.

So, in our case the first symbol is “(“, so we add “)” to the queue. Then we encounter the symbol “[», значит добавляем в очередь «]”. Next comes the symbol “]” – a closing bracket, which means we don't add anything, but get (or rather remove using the pop() method) the last element from the queue and compare it with the current one. “]” = “]”, matches. We move on to the next element in the line – this is “)”, it matches the element that remains in the queue “)”.

There are no symbols left, the queue is empty, which means our string is valid. The full algorithm looks like this:

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();

    }

I wanted to consider in this article the use of queues for solving problems with tree traversal and compare this approach with recursion. But it seems I will organize a separate article for this matter:)

By the way, I made my own telegram channel where I write approaches to solving various problems with LeetCode, there will be more analysis of specific problems than here, because an article is not always needed. In general, if you are interested – I am waiting here – t.me/crushiteasy 🙂