C# Coding Test Course, Stack and Queue

Introduction

Hello! In this course, we will solve algorithm problems using stacks and queues with C#.
Stacks and queues are one of the most fundamental and important data structures in computer science, widely used to solve various algorithm problems.
Through this course, I hope you will understand the basic concepts of stacks and queues and deepen your understanding of these two structures by solving problems commonly asked in actual coding tests.

Basic Concepts of Stack and Queue

A stack has a Last In First Out (LIFO) structure, where the last data added is the first to be removed.
A queue has a First In First Out (FIFO) structure, where the first data added is the first to be removed.
These two structures are important for solving various programming problems.

Problem: Parenthesis Balance Check

Problem Description: Write a function that checks whether the same type of parentheses are properly opened and closed in a given string.
Examples of valid parentheses are “()[]{}”, and examples of invalid parentheses are “(]”, “([)]”.

Input

  • String s (1 <= s.length <= 100) – Composed of lowercase and uppercase letters, numbers, and parentheses.

Output

  • Return true if all parentheses are correctly opened and closed, otherwise return false.

Example

    Input: s = "()"
    Output: true

    Input: s = "([)]"
    Output: false

Problem Solving Process

We will use the stack data structure to solve this problem. We will push the open parentheses onto the stack and compare them with the top element of the stack each time a closed parenthesis appears to check if they are valid.
The process is as follows:

  1. Create a map to store pairs of parentheses. For example, define it as { ‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘ }.
  2. Initialize the stack.
  3. Traverse the string one character at a time.
  4. If the current character is an open parenthesis, push it onto the stack.
  5. If it is a closed parenthesis, check if the stack is empty and, if it is not, check if it matches with the top element of the stack.
  6. After traversing the entire string, return true if the stack is empty, otherwise return false.

C# Code Implementation


    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public bool IsValid(string s)
        {
            // Dictionary to store pairs of parentheses
            Dictionary<char, char=""> parentheses = new Dictionary<char, char="">()
            {
                { ')', '(' },
                { ']', '[' },
                { '}', '{' }
            };

            Stack stack = new Stack(); // Initialize the stack

            foreach (char c in s)
            {
                if (parentheses.ContainsKey(c)) // Check if it is a closed parenthesis
                {
                    // Return false if the stack is empty or the top element doesn't match
                    if (stack.Count == 0 || stack.Pop() != parentheses[c])
                    {
                        return false;
                    }
                }
                else // If it is an open parenthesis
                {
                    stack.Push(c); // Push onto the stack
                }
            }

            return stack.Count == 0; // Return true if the stack is empty
        }
    }
    </char,></char,>

Code Explanation

The code above defines a function `IsValid` that takes a string `s` as input and checks the balance of parentheses.
First, it defines the pairs of parentheses and initializes the stack. Then, it traverses the input string, pushes open parentheses onto the stack, and for closed parentheses, checks if they match with the top element of the stack.
After checking all characters, if the stack is empty, it returns true, indicating all parentheses are correctly opened and closed.

Additional Examples

Example 1

    Input: s = "{[]}"
    Output: true

Explanation: It starts with ‘{‘ and ends with ‘}’, and the ‘[‘ and ‘]’ in between are correctly matched.

Example 2

    Input: s = "({[})"
    Output: false

Explanation: Since ‘]’ comes immediately after ‘(‘, it is not a valid pair.

Review Problem

In this course, we solved the parenthesis balance check problem using a stack.
I hope you now have a better understanding of stacks and queues.
Next, you might want to try the problem “Implement Queue using Stacks.”
This problem allows you to learn more deeply about the basic concepts of stacks and their applications.
I recommend you try implementing it yourself and writing the code!

Conclusion

Stacks and queues are very important data structures in algorithms and programming.
There are many types of problems that can be solved using these two data structures.
I hope this course has been helpful in solving programming problems in the future!
Keep studying the applications of stacks and queues.