Visualization: Simulate Stack and Queue Operations | Data Structures

Practice tracing Stack and Queue states through classic algorithmic problems asked in technical interviews.

Problem 1: Valid Parentheses Matching (Stack)

Specification

Given a string containing characters '(', ')', '{', '}', '[', and ']', determine if the input string has valid matching brackets.

Algorithm

Initialize an empty character stack.
Iterate through each character:
- If opening bracket ('(', '{', '['), push onto stack.
- If closing bracket (')', '}', ']'), check if stack is empty. If not, pop and verify matching pair.
String is valid if the stack is completely empty at the end.

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

Problem 2: Implement a Queue Using Two Stacks

Specification

Implement a FIFO queue using only two LIFO stacks.

Stack In:  [ 1, 2, 3 ]
Stack Out: []

To Dequeue:
If Stack Out is empty, pop EVERYTHING from Stack In and push to Stack Out!
Stack Out: [ 3, 2, 1 ] (1 is now on top!)
Pop from Stack Out -> returns 1!

class MyQueue {
    private val stackIn = ArrayDeque<Int>()
    private val stackOut = ArrayDeque<Int>()

    fun push(x: Int) {
        stackIn.addLast(x)
    }

    fun pop(): Int {
        shiftStacks()
        return stackOut.removeLast()
    }

    fun peek(): Int {
        shiftStacks()
        return stackOut.last()
    }

    fun empty(): Boolean = stackIn.isEmpty() && stackOut.isEmpty()

    private fun shiftStacks() {
        if (stackOut.isEmpty()) {
            while (stackIn.isNotEmpty()) {
                stackOut.addLast(stackIn.removeLast())
            }
        }
    }
}

Complexity:

push: O(1)
pop / peek: Amortized O(1) (each element is transferred between stacks at most once).

Summary

Stacks are the natural choice for paired bracket validation and undo buffers.
Two reversing stacks can simulate a FIFO queue with amortized O(1) efficiency.