c# Queue / Stack -자료구조

소프트웨어 개발에서 자료 구조는 핵심적인 역할을 수행한다.

데이터 저장, 조직화, 처리, 검색 등을 효율적으로 수행할 수 있는 방법들을 제공한다.

이를 통해 프로그램의 성능, 유지 보수성, 확장성 등 다양한 측면에서 이점을 얻을 수 있으므로 코딩을 하기 전

자료구조를 완벽하게 공부하는 것 또한 중요하다.

오늘은 C# 에서 기본적인 자료구조의 일종 Queue와 Stack을 공부해볼 예정이다. 

 

 

 

1. 큐 (Queue) 와 스택(Stack) 이란?  활용 예시

 Queue는 "대기열"이라는 뜻을 가지고 있으며, 데이터를 일시적으로 저장하는 선입선출(FIFO: First - In - First - Out) 방식의 자료구조이다. 우리 주변에서도 많은 예시를 볼 수 있는데, 가장 일반적 예시로는 은행의 창구나 대기열이 형성되어 있는 상황을 상상해 볼 수 있다. 가장 먼저 도착한 사람이 가장 먼저 처리를 받게 된다.

 

사진에서 볼 수 있듯 데이터가 뒤로 추가되고, 앞에서부터 데이터가 제거되는 데, 

이러한 특성으로 인해 Enqueue(데이터 추가)와 Dnqueue(데이터 제거)라는 두가지 주요 연산이 있다.

Queue는 다양한 상황에서 사용되는데 몇가지 예시를 들자면

1. 작업큐 : 여러 작업을 순차적으로 처리해야할 때

2. 메세지큐: 비동기적인 메세지 전달 시스템

3. 너비 우선 탐색(BFS): 그래프나 트리에서 너비 우선 탐색을 수행할 때

등 다양한 상황에서 데이터의 순서를 유지하고 처리해야 할 때 유용하다.

 

 

Stack은 데이터를 일시적으로 저장하는 후입선출(LIFO: Last - In - First - Out) 방식의 자료구조이다.

이 개념은 접시를 쌓아놓은 것을 상상해볼 수 있는데, 가장 마지막에 올려진 접시가 가장 먼저 사용되는 구조이다.

 

Stack에서는 데이터가 맨 위로 추가되고, 맨 위에서부터 데이터가 제거된다. 이러한 특성으로 인해 

Push(데이터 추가)와 Pop(데이터 제거)라는 두 가지 주요 연산이 존재한다.

 

이렇게 Queue와 Stack은 각각의 독특한 특성을 가지고 있으며, 프로그래밍에서 다양한 상황에 유용하게 활용된다.

예시를 들자면,

1. 재귀 호출: 함수가 자기 자신을 호출할때

2. 식의 계산: 후위 표기법 등을 사용하여 수식을 계산할 때

3. 브라우저의 뒤로 가기 : 뒤로 가기 버튼을 누를 때마다 방문한 웹페이지의 URL을 저장할 때

등 데이터를 역순으로 처리하거나 임시적으로 저장할 필요가 있는 상황에서 유용하다.

 

 

2. c#에서 Queue와 Stack의 사용 예시

1. Queue 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Queue<string> queue = new Queue<string>();

        // 데이터 추가
        queue.Enqueue("사과");
        queue.Enqueue("바나나");
        queue.Enqueue("딸기");

        // 데이터 제거 및 출력
        while (queue.Count > 0)
        {
            string data = queue.Dequeue();
            Console.WriteLine("Dequeued 데이터: " + data);
        }
    }
}

위 예시 코드는 Queue에 사과, 바나나, 딸기라는 문자열 데이터를 추가하고, 데이터를 제거하여 출력하는 간단한 작업을 수행한다. Enqueue 메서드와 Dequeue 메소드를 사용하여 데이터를 추가하고 제거한다.

 

2. Stack 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<string> stack = new Stack<string>();

        // 데이터 추가
        stack.Push("사과");
        stack.Push("바나나");
        stack.Push("딸기");

        // 데이터 제거 및 출력
        while (stack.Count > 0)
        {
            string data = stack.Pop();
            Console.WriteLine("Popped 데이터: " + data);
        }
    }
}

이번 예시는 stack을 활용하여 똑같이 사과, 바나나, 딸기 문자열을 추가하고 Push 메소드와 Pop메서드를 사용하여 데이터를 추가, 제거 처리합니다.

 

이제 조금 Queue와 Stack을 이해했길 바란다.

그럼 이제 조금 심화된 내용을 만들어보자

 

3. c#에서 Queue와 Stack의 심화 예제

Queue의 확장된 활용 : BFS(Breadth-First-Search)

Queue를 활용하여 BFS(Breadth-Fist Search)를 작성해 보겠다.

BFS는 그래프나 트리에서 너비 우선 탐색 알고리즘으로 queue를 보통 활용한다.

Queue에 인접한 노드를 순차적으로 추가하고, 방문한 노드를 제거하는 방식으로 탐색을 진행한다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 그래프 초기화
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            { 1, new List<int> { 2, 3 } },
            { 2, new List<int> { 4, 5 } },
            { 3, new List<int> { 6 } },
            { 4, new List<int> { } },
            { 5, new List<int> { } },
            { 6, new List<int> { } }
        };

        // BFS 탐색
        Queue<int> queue = new Queue<int>();
        HashSet<int> visited = new HashSet<int>();

        int startNode = 1; // 시작 노드 설정
        queue.Enqueue(startNode);
        visited.Add(startNode);

        while (queue.Count > 0)
        {
            int currentNode = queue.Dequeue();
            Console.WriteLine("Visited Node: " + currentNode);

            foreach (int neighbor in graph[currentNode])
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

위의 예제 코드는 주어진 그래프에서 BFS를 사용하여 노드를 방문하는 예제이다.

Queue를 사용하여 인접한 노드를 순차적으로 추가하고, 방문한 노드를 제거하여 BFS를 수행한다.

시작 노드부터 인접한 노드를 방문하고, 다음 단계에서는 그 노드에 인접한 노드를 방문하는 방식의 탐색기법이다.

 

 

Stack의 확장된 활용 : DFS(Depth-First-Search)

DFS(Depth-First Search)는 그래프나 트리의 깊이 우선 탐색 알고리즘이다. 

Stack에 인접한 노드를 순차적으로 추가하고, 방문한 노드를 제거하는 방식으로 탐색을 수행한다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // 그래프 초기화
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            { 1, new List<int> { 2, 3 } },
            { 2, new List<int> { 4, 5 } },
            { 3, new List<int> { 6 } },
            { 4, new List<int> { } },
            { 5, new List<int> { } },
            { 6, new List<int> { } }
        };

        // DFS 탐색
        Stack<int> stack = new Stack<int>();
        HashSet<int> visited = new HashSet<int>();

        int startNode = 1; // 시작 노드 설정
        stack.Push(startNode);
        visited.Add(startNode);

        while (stack.Count > 0)
        {
            int currentNode = stack.Pop();
            Console.WriteLine("Visited Node: " + currentNode);

            foreach (int neighbor in graph[currentNode])
            {
                if (!visited.Contains(neighbor))
                {
                    stack.Push(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

예제 코드는 주어진 그래프에서 DFS를 사용하여 노드를 방문하는 예제인데 Stack을 사용하여 인접한 노드를 

순차적으로 추가하고, 방문한 노드를 제거하여 DFS를 수행한다.

 

이처럼 다양한 알고리즘과 문제 해결에 적용될 수 있는 Queue와 Stack을 잘 이해하길 바란다.