Programming Test Course in Kotlin, Stack and Queue

1. Introduction

Coding tests are one of the important processes for finding modern programming jobs. As technology advances and the importance of data structures and algorithms comes to the fore, these skills have become a major criteria for evaluating a programmer’s capabilities. In this course, we will understand the concepts of Stack and Queue using Kotlin and solve algorithmic problems based on these concepts.

2. Basic Concepts of Stack and Queue

2.1. Stack

A stack is a data structure that stores data and operates on a Last In First Out (LIFO) basis. That is, the most recently added data is the first to be removed. Stacks are commonly used in function call stacks, browser back buttons, and string parentheses validation algorithms.

2.2. Queue

A queue is another data structure that stores data and operates on a First In First Out (FIFO) basis. That is, the data that enters first is the data that exits first. Queues are primarily used in printer job management, process scheduling, and breadth-first search (BFS) algorithms.

3. Problem Description

Now let’s solve a problem using stacks and queues. Let’s take a look at the following problem:

Problem: Parentheses Validity Check

Write a function to determine whether a given string consists of valid parentheses. Valid parentheses mean that every open parenthesis must be closed, and every closed parenthesis must form a pair with its corresponding open parenthesis.

For example, the string “{[()]}” is valid, but “{[(])}” is not valid.

4. Problem Analysis

To solve this problem, it is advisable to follow these steps:

  1. Traverse the string and store open parentheses in a stack.
  2. When encountering a closed parenthesis, check if it pairs with the most recently stored open parenthesis from the stack.
  3. If the stack is not empty after processing all characters, the string is invalid.

5. Algorithm Design

Therefore, we can design an algorithm as follows:

  1. Initialize the stack.
  2. Iterate through each character of the string.
  3. If the character is an open parenthesis, add it to the stack.
  4. If it is a closed parenthesis, pop from the stack and check if it matches the corresponding open parenthesis.
  5. If the stack is not empty, the string is invalid, and return false.
  6. After processing all characters, return true if the stack is empty.

6. Kotlin Implementation

Now, let’s implement the algorithm described above in Kotlin.

fun isValidParentheses(s: String): Boolean {
    val stack = mutableListOf()
    val mapping = mapOf('(' to ')', '{' to '}', '[' to ']')

    for (char in s) {
        if (mapping.containsKey(char)) {
            stack.add(char)
        } else if (stack.isNotEmpty() && mapping[stack.last()] == char) {
            stack.removeAt(stack.size - 1)
        } else {
            return false
        }
    }
    return stack.isEmpty()
}

7. Code Explanation

Each part of the code has the following roles:

  • val stack = mutableListOf(): Initializes the stack.
  • val mapping = mapOf('(' to ')', '{' to '}', '[' to ']'): Stores the mapping of open and closed parentheses.
  • for (char in s): Iterates through each character of the string.
  • if (mapping.containsKey(char)): Adds the character to the stack if it is an open parenthesis.
  • else if (stack.isNotEmpty() && mapping[stack.last()] == char): If it is a closed parenthesis, check if the matching open parenthesis is on top of the stack, and remove it if it matches.
  • After processing the string, return true if the stack is empty, otherwise return false.

8. Complexity Analysis

The time complexity of this algorithm is O(n), where n is the length of the string. This is because each character is processed only once. The space complexity is also O(n) since, in the worst case, all open parentheses may be stored in the stack.

9. Test Cases

You can use the following test cases to verify that the implementation is correct.

fun main() {
    println(isValidParentheses("{[()]}")) // true
    println(isValidParentheses("{[(])}")) // false
    println(isValidParentheses("{{[[(())]]}}")) // true
    println(isValidParentheses("{")) // false
    println(isValidParentheses("}")) // false
}

10. Conclusion

In this course, we explored the basic concepts of stacks and queues, along with solving the problem of validating parentheses using a stack. This approach is a common type of question in coding tests, so it is important to practice sufficiently to become familiar with the use of stacks and queues.

11. References

  • LeetCode: Valid Parentheses
  • GeeksforGeeks: Stack Data Structure
  • Wikipedia: Stack (abstract data type)

Now, readers, you can understand the concepts of stack and queue using Kotlin and try solving various problems.