C# Coding Test Tutorials, Stack and Queue

Introduction

Hello! In this tutorial, we will solve algorithm problems using stacks and queues with C#.
Stacks and queues are some of the most basic and important data structures in computer science, widely used to solve various algorithm problems.
Through this tutorial, we hope you gain a solid understanding of the basic concepts of stacks and queues and deepen your understanding by solving problems frequently asked in coding tests.

Basic Concepts of Stack and Queue

A stack follows the Last In First Out (LIFO) principle, where the last entered data is the first to exit.
A queue follows the First In First Out (FIFO) principle, where the first entered data is the first to exit.
These two structures are essential for solving various programming problems.

Problem: Checking Parenthesis Balance

Problem Description: Write a function to check if the same types of parentheses in a given string are correctly opened and closed.
Examples of correct parentheses are “()[]{}”, and examples of incorrect parentheses are “(]”, “([)]”.

Input

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

Output

  • Returns true if all parentheses are correctly opened and closed; otherwise, returns false.

Examples

    Input: s = "()"
    Output: true

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

Solution Process

We will use a stack data structure to solve this problem. We will push open parentheses to the stack and, when encountering a closed parenthesis,
compare it with the top element of the stack to check if it matches correctly.
The process is as follows:

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

C# Code Implementation


    using System;
    using System.Collections.Generic;

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

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

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

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

Code Explanation

The above code defines the function `IsValid` that checks the balance of parentheses in the string `s`.
It first defines pairs of parentheses, initializes a stack, and then iterates through the input string, pushing open parentheses to the stack
and checking the top element for a match if it encounters a closing parenthesis.
If the stack is empty after checking all characters, it returns true, indicating all parentheses are correctly opened and closed.

Additional Examples

Example 1

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

Explanation: Starts with ‘{‘ and ends with ‘}’, with ‘[‘ and ‘]’ correctly matched in between.

Example 2

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

Explanation: ‘[‘ appears right after ‘(‘ without a matching pair, so it’s incorrect.

Review Problem

In this tutorial, we solved a parenthesis balance problem using a stack.
I hope you now have a better understanding of stacks and queues.
Another problem to try next is “Implementing Queue using Stack.”
This is a great way to dive deeper into the basic concepts of stacks and their applications.
I recommend implementing and writing code on your own!

Conclusion

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