Stack, Queue, & Array Deque: Elegant Tools For Handling Temporary Data

Stack and Queue are simply arrays with restrictions, that make them elegant tools for handling temporary data.

The stack operation is Last In, First Out (LIFO), which means data can only be inserted(pushed), read, or removed(popped) from the end of the stack. Think of it as an actual stack of dishes, where the end of the stack is the top, while the beginning is the bottom. E.g. on pushed 1 > 1,2 > 1,2,3 and on removed 1,2,3 > 1,2 > 1.

LIFO, You always put new dishes on top and clean the dishes on the top first

As for queue operation, it’s the opposite of stack: First In, First Out (FIFO). Data can only be inserted at the end of the queue, but can only be read or removed from the front of the queue. E.g. on pushed 1 > 1,2 > 1,2,3 and on removed 1,2,3 > 2, 3 > 3. Yes, similar to the actual queue in the real world.

FIFO, first come first served

In Kotlin, we have ArrayDeque since version 1.3.70, which functions as both a queue and a stack, like Java’s java.util.Deque . It also supports both adding and removing elements from both ends of the deque efficiently with O(1) time complexity, by utilizing a circular array and carefully managing its internal structure.

• Stack LIFO: addLast(), removeLast(), and last().
• Queue FIFO: addLast(), removeFirst(), and first().

Stack Use Case

Linter uses a stack to inspect our code, such as linter for opening and closing braces, parentheses, square brackets, and so on.

1. Read each charachter from left to right, and skip if not a type of brace
2. If we find an opening brace, push it onto the stack `stack.push(braces)`
3. If we find a closing brace, check if it matches the last stack entry.
4. If matches {}, (), [], pop the stack and continue. Else syntax error
5. In the end, if stack still not empty, syntax error

// ( => ) => { => } => "Done, No Error"
// ) => closing ) without opening
// ( => } => wrong closing } for (
// ( => No closing for (
fun bracesLinter() {
    val stack = ArrayDeque<String>()
    val openingBraces = arrayOf("(", "{", "[")
    val closingBraces = arrayOf(")", "}", "]")

    val code = """
        fun main() {
            println("Hello, world!")
        }
    """.trimIndent()
    
    code.forEach {
        val char = it.toString()
        val isClosingBraces = closingBraces.contains(char)
        val closingIndex = closingBraces.indexOf(char)
        when {
            openingBraces.contains(char) -> stack.addFirst(char)
            isClosingBraces && stack.isEmpty() -> {
                throw Throwable("closing $char without opening")
            }
            isClosingBraces && 
                openingBraces[closingIndex] == stack.first() -> {
                stack.removeFirst()
            }
            isClosingBraces -> {
                throw Throwable("wrong closing $it for ${stack.first()}")
            }
        }
    }

    if (stack.isEmpty()) {
        println("Done, No Error")
    } else {
        throw Throwable("No closing for $stack")    
    } 
}

Recursion uses a stack to keep track of which functions it’s in the middle of calling, and this stack is known as the call stack. Interestingly, in the case of infinite recursion, the program will push the same function into the stack until there’s no more room in the memory, and this causes an error known as stack overflow.

fun main() {
    countdown(3)
}

fun countdown(count: Int) {
    println(count)
    if (count == 0) return
    
     countdown(count.dec())
}

// [countdown(3)]
// [countdown(3), countdown(2)] 
// [countdown(3), countdown(2), countdown(1)]
// [countdown(3), countdown(2), countdown(1), countdown(0)]
// [countdown(3), countdown(2), countdown(1)]
// [countdown(3), countdown(2)]
// [countdown(3)]
// end

Besides the 2 examples above, the stack is also used for undo/redo, deep first search (DFS) algorithm, web browser history, and so on.

Queue Use Case

Queues are common in many applications, ranging from printing jobs to background workers in web applications. For Android, it might start from

• MessageQueue on the thread
• Multithreading Synchronization, ensuring that only one thread accesses the resource at a time
• Breadth-First Search (BFS): Queues are crucial for implementing BFS, a graph traversal algorithm that explores vertices in layers, where each layer represents nodes at the same distance from the starting vertex
• Task Scheduling: Queues can be used to manage and schedule tasks or jobs in a fair and ordered manner. For example, in a printer queue or a task processing system.
• And so on.

Thanks for reading, hope it helps.

LinkedIn : https://www.linkedin.com/in/wahyu-raya/