Kotlin ArrayDeque as a stack and a queue

Check balanced brackets with a stack and serve items in arrival order with a queue.

Kotlin

fun balanced(text: String): Boolean {
    val stack = ArrayDeque<Char>()
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    for (ch in text) {
        when (ch) {
            '(', '[', '{' -> stack.addLast(ch)
            ')', ']', '}' -> if (stack.removeLastOrNull() != pairs[ch]) return false
        }
    }
    return stack.isEmpty()
}

fun main() {
    for (test in listOf("(a[b]{c})", "(]", "((", ")(", "")) {
        println("'$test' -> ${balanced(test)}")
    }

    val queue = ArrayDeque<String>()
    queue.addLast("Ada")
    queue.addLast("Bo")
    queue.addLast("Cy")
    val served = queue.removeFirst()
    println("$served served, ${queue.size} waiting, next is ${queue.first()}")
}

Output

'(a[b]{c})' -> true
'(]' -> false
'((' -> false
')(' -> false
'' -> true
Ada served, 2 waiting, next is Bo

Explanation

kotlin.collections.ArrayDeque is a resizable circular array that supports adding and removing at both ends in amortized O(1). With addLast and removeLast it behaves as a stack (last-in, first-out). With addLast and removeFirst it behaves as a queue (first-in, first-out). removeLastOrNull and removeFirstOrNull return null instead of throwing when it is empty.

Bracket matching is the classic stack exercise. Push every opening bracket. At a closing bracket, the top of the stack must be its matching opening bracket. At the end the stack must be empty. The function below returns false as soon as a mismatch, or a closing bracket with nothing open, is found.

Explore the dry run

Guided walkthroughReady

1fun balanced(text: String): Boolean {

2 val stack = ArrayDeque<Char>()

3 val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')

4 for (ch in text) {

5 when (ch) {

6 '(', '[', '{' -> stack.addLast(ch)

7 ')', ']', '}' -> if (stack.removeLastOrNull() != pairs[ch]) return false

8 }

9 }

10 return stack.isEmpty()

11}

13fun main() {

14 for (test in listOf("(a[b]{c})", "(]", "((", ")(", "")) {

15 println("'$test' -> ${balanced(test)}")

16 }

18 val queue = ArrayDeque<String>()

19 queue.addLast("Ada")

20 queue.addLast("Bo")

21 queue.addLast("Cy")

22 val served = queue.removeFirst()

23 println("$served served, ${queue.size} waiting, next is ${queue.first()}")

24}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Opening brackets are pushed onto the stack.	`—`	—
A closing bracket pops the top. If the stack was empty or the top is not the matching opener, the text is unbalanced.	`—`	—
Leftover opening brackets mean the text is unbalanced.	`—`	—
Only the properly nested and the empty texts are balanced.	`—`	'(a[b]{c})' -> true '(]' -> false '((' -> false ')(' -> false '' -> true
The queue serves the person who arrived first.	`—`	'(a[b]{c})' -> true '(]' -> false '((' -> false ')(' -> false '' -> true
Ada leaves; Bo is now first in line.	`—`	'(a[b]{c})' -> true '(]' -> false '((' -> false ')(' -> false '' -> true Ada served, 2 waiting, next is Bo

Cost and common mistakes

O(n) time and O(n) space for the bracket check; queue operations are O(1) amortized.

removeLast and removeFirst throw NoSuchElementException on an empty deque. The OrNull versions avoid that.
Counting brackets is not enough. The text )( has equal counts but is invalid.
Do not use a MutableList and removeAt(0) as a queue. It shifts every element, so each removal is O(n).

Try it yourself

What does balanced("{[()]}") return?

Reveal answer and reasoning

true: each closing bracket matches the most recent unmatched opener.

Kotlin ArrayDeque as a stack and a queue

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading