DotNet
자료구조
제네릭 컬렉션
Queue

Queue

Queue<T>는 .NET에서 제공하는 제네릭 큐 자료 구조로, FIFOFirst-In-First-Out 방식으로 데이터를 관리합니다. System.Collections.Generic 네임스페이스에 포함되어 있으며, 데이터가 입력된 순서대로 처리해야 하는 상황에서 유용하게 사용됩니다.

Queue의 기본 사용법

Queue<T>는 데이터가 먼저 들어온 데이터가 먼저 나가는 선입선출 방식의 컬렉션입니다. 다음은 Queue<int>의 기본적인 사용 예제입니다:

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);
        // 요소 출력 및 제거
        while (queue.Count > 0)
        {
            int item = queue.Dequeue();
            Console.WriteLine(item);
        }
        // 출력:
        // 1
        // 2
        // 3
    }
}

Queue<T>의 특징

  • FIFO 구조: Queue는 선입선출 방식을 사용하여, 먼저 들어온 데이터가 먼저 처리됩니다.
  • 타입 안전성: 제네릭 타입을 사용하여 타입 안전성을 보장합니다.
  • 빠른 추가 및 제거: Enqueue와 Dequeue를 사용하여 요소를 빠르게 추가하고 제거할 수 있습니다.

장점

  • 간단한 데이터 흐름 관리: 큐는 데이터가 입력된 순서대로 처리해야 하는 상황에 적합합니다. 예를 들어, 프린터 작업 큐나 이벤트 처리 시스템에서 사용됩니다.
  • 빠른 Enqueue 및 Dequeue: 큐의 양 끝에서만 삽입 및 삭제가 이루어지므로, 이러한 작업은 평균적으로 O(1)의 시간 복잡도를 가집니다.
  • 타입 안전성: 제네릭을 통해 타입을 명시함으로써, 컴파일 시 타입 오류를 방지할 수 있습니다.

단점

  • 중간 요소 접근 불가: 큐는 선입선출 방식으로 동작하기 때문에 중간의 특정 요소를 직접 접근할 수 없습니다. 이는 순차적으로 모든 요소를 탐색해야 하므로 O(n)의 시간 복잡도를 가지게 됩니다.
  • 순차 접근: 중간의 특정 요소를 검색하거나 수정하는 작업이 어렵습니다. 큐는 특정한 상황에서만 적합한 자료 구조입니다.

주요 메서드와 속성

생성자와 초기화

기본 생성자

빈 Queue를 생성합니다.

Queue<int> queue = new Queue<int>();
  • 기본 생성자로 초기화하면 내부 용량은 0이며, 첫 번째 요소 추가 시 용량이 4로 설정됩니다.

초기 용량 지정

큐의 초기 용량을 설정하여 성능을 최적화할 수 있습니다.

Queue<int> queue = new Queue<int>(capacity: 100);
  • 초기 용량 설정을 통한 최적화를 참조하세요.

요소 추가 및 제거

Enqueue

큐의 끝에 요소를 추가합니다.

queue.Enqueue(5);
  • 큐의 끝에 새로운 요소를 추가하며, 용량이 가득 찰 경우 자동으로 배열의 크기를 증가시킵니다.

Dequeue

큐의 앞에서 요소를 제거하고 반환합니다.

int item = queue.Dequeue();
  • 큐가 비어 있을 경우 InvalidOperationException이 발생합니다.

요소 탐색

Peek

큐의 앞에 있는 요소를 제거하지 않고 반환합니다.

int frontItem = queue.Peek();
  • 큐가 비어 있을 경우 InvalidOperationException이 발생합니다. Peek 메서드는 요소를 제거하지 않으므로 큐의 상태를 유지합니다.

기타 유용한 메서드와 속성

Count

큐에 포함된 요소의 개수를 반환합니다.

int count = queue.Count;
  • 현재 큐에 남아 있는 요소의 개수를 확인할 수 있습니다.

Contains

큐에 특정 요소가 있는지 확인합니다.

bool contains = queue.Contains(3);
  • 요소를 찾기 위해 큐 전체를 순차적으로 탐색하므로 O(n)의 시간 복잡도를 가집니다.

Clear

큐의 모든 요소를 제거합니다.

queue.Clear();

ToArray

큐의 요소를 배열로 복사합니다.

var array = queue.ToArray();

Queue<T>와 다른 자료 구조의 비교

  • Stack<T>: Stack은 LIFOLast-In-First-Out 방식으로 데이터를 처리하며, 가장 나중에 추가된 요소가 가장 먼저 제거됩니다. 반면 Queue는 FIFO 방식으로 데이터를 처리합니다. 따라서 데이터를 처리하는 순서에 따라 적절한 자료 구조를 선택해야 합니다.
  • LinkedList<T>: LinkedList를 사용하여 큐를 쉽게 구현할 수도 있지만, 특별한 이유가 없는 한 .NET에서 제공하는 Queue<T>를 사용하는 것이 더 효율적입니다. Queue<T>는 큐의 기능을 수행하는 데 최적화되어 있으며, 추가적인 메모리 관리나 복잡한 구현을 피할 수 있습니다.

Queue<T>의 활용

실시간 데이터 처리와 버퍼로서의 큐 사용

Queue<T>는 실시간 데이터 처리와 버퍼buffer 역할로도 자주 사용됩니다. 데이터가 생성되는 속도와 처리되는 속도가 다를 때, 큐를 사용하여 데이터를 임시로 저장하고 순차적으로 처리할 수 있습니다.

  • 네트워크 패킷 처리: 수신된 패킷을 큐에 저장하고 순차적으로 처리합니다.
  • 이벤트 처리 시스템: 발생한 이벤트를 큐에 넣고, 이벤트 핸들러가 순서대로 처리합니다.
  • 데이터 스트림 버퍼링: 입력과 처리가 비동기적으로 이루어질 때 데이터 손실을 방지합니다.
  • 생산자-소비자 문제: 생산자가 데이터를 빠르게 생성하는 반면 소비자가 느리게 처리할 때, 큐를 버퍼로 사용하여 두 작업 간의 속도 차이를 완화할 수 있습니다.
using System;
using System.Collections.Generic;
using System.Threading.Tasks;
using System.Threading;
class Program
{
    static void Main()
    {
        Queue<int> buffer = new Queue<int>();
        object lockObject = new object();
        // 생산자 스레드
        Task.Run(() =>
        {
            for (int i = 0; i < 10; i++)
            {
                lock (lockObject)
                {
                    buffer.Enqueue(i);
                    Console.WriteLine($"생산: {i}");
                }
                Thread.Sleep(100); // 생산 속도 조절
            }
        });
        // 소비자 스레드
        Task.Run(() =>
        {
            while (true)
            {
                lock (lockObject)
                {
                    if (buffer.Count > 0)
                    {
                        int item = buffer.Dequeue();
                        Console.WriteLine($"소비: {item}");
                    }
                }
                Thread.Sleep(150); // 소비 속도 조절
            }
        }).Wait();
    }
}

BFS 알고리즘

그래프나 트리 구조를 탐색할 때 BFSBreadth-First Search, 너비 우선 탐색 알고리즘을 구현하는 데 Queue가 자주 사용됩니다. BFS는 먼저 방문할 노드를 큐에 넣고, 큐에서 순서대로 노드를 꺼내면서 탐색하는 방식으로 동작하며, 경로 찾기 및 최단 거리 계산에 유용합니다.

using System;
using System.Collections.Generic;
class Graph
{
    private int vertices;
    private List<int>[] adjList;
    public Graph(int vertices)
    {
        this.vertices = vertices;
        adjList = new List<int>[vertices];
        for (int i = 0; i < vertices; i++)
        {
            adjList[i] = new List<int>();
        }
    }
    public void AddEdge(int v, int w)
    {
        adjList[v].Add(w);
    }
    public void BFS(int startVertex)
    {
        bool[] visited = new bool[vertices];
        Queue<int> queue = new Queue<int>();
        visited[startVertex] = true;
        queue.Enqueue(startVertex);
        while (queue.Count > 0)
        {
            int vertex = queue.Dequeue();
            Console.Write(vertex + " ");
            foreach (int adjacent in adjList[vertex])
            {
                if (!visited[adjacent])
                {
                    visited[adjacent] = true;
                    queue.Enqueue(adjacent);
                }
            }
        }
    }
}
class Program
{
    static void Main()
    {
        Graph graph = new Graph(4);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 2);
        graph.AddEdge(2, 0);
        graph.AddEdge(2, 3);
        graph.AddEdge(3, 3);
        Console.WriteLine("BFS starting from vertex 2:");
        graph.BFS(2);
        // 출력: 2 0 3 1
    }
}

큐를 활용한 비동기 프로그래밍

비동기 작업을 관리할 때 Queue<T>를 활용하여 작업을 순차적으로 처리하는 것이 일반적입니다.

  • 비동기 이벤트 처리: 큐를 사용해 비동기적으로 발생하는 이벤트를 순서대로 처리할 수 있습니다. 이는 이벤트가 발생한 순서를 보장하며, 각 이벤트가 처리되는 동안 다음 이벤트가 기다릴 수 있도록 합니다.

  • Task Queue 구현: 작업을 큐에 추가하고, 각 작업을 비동기로 처리하면서 순서를 유지할 수 있습니다. 이를 통해 복잡한 비동기 작업 흐름을 쉽게 관리할 수 있습니다.

using System;
using System.Collections.Generic;
using System.Threading.Tasks;
class Program
{
    static async Task Main()
    {
        Queue<Func<Task>> taskQueue = new Queue<Func<Task>>();
        taskQueue.Enqueue(() => Task.Run(() => Console.WriteLine("Task 1 실행")));
        taskQueue.Enqueue(() => Task.Run(() => Console.WriteLine("Task 2 실행")));
        taskQueue.Enqueue(() => Task.Run(() => Console.WriteLine("Task 3 실행")));
        while (taskQueue.Count > 0)
        {
            var task = taskQueue.Dequeue();
            await task();
        }
    }
}
  • 작업을 큐에 추가하고, 하나씩 비동기로 실행함으로써 작업의 순서와 비동기 처리를 동시에 유지할 수 있습니다.

TryDeque 구현

Queue<T>에서 안전하게 요소를 제거하려면, TryDequeue와 유사한 동작을 직접 구현할 수 있습니다. Dequeue 메서드는 큐가 비어 있을 때 InvalidOperationException 예외를 발생시키기 때문에, 이를 방지하려면 큐의 요소 유무를 먼저 확인한 후 Dequeue를 호출하는 방식을 사용할 수 있습니다.

public static bool TryDequeue<T>(Queue<T> queue, out T result)
{
    if (queue.Count > 0)
    {
        result = queue.Dequeue();
        return true;
    }
    else
    {
        result = default;
        return false;
    }
}
// 사용 예시
Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
if (TryDequeue(queue, out int result))
{
    Console.WriteLine($"Dequeued: {result}");
}
else
{
    Console.WriteLine("Queue is empty.");
}

스레드 안전성

Queue<T>는 스레드 안전하지 않기 때문에 동기성 문제가 발생할 수 있습니다. 여러 스레드가 동시에 Queue<T>에 접근하여 요소를 추가Enqueue하거나 제거Dequeue하려고 할 때, 예상치 못한 동작이나 데이터 손실이 발생할 수 있습니다.

private readonly Queue<int> queue = new Queue<int>();
private readonly object lockObject = new object();
public void EnqueueSafe(int item)
{
    lock (lockObject)
    {
        queue.Enqueue(item);
    }
}
public bool TryDequeueSafe(out int result)
{
    lock (lockObject)
    {
        if (queue.Count > 0)
        {
            result = queue.Dequeue();
            return true;
        }
        else
        {
            result = default;
            return false;
        }
    }
}

이 방식은 스레드 안전성을 확보할 수 있지만, lock을 사용하면 성능에 영향을 미칠 수 있고 다수의 스레드가 자주 접근할 경우 병목bottleneck이 발생할 수 있습니다.
다중 스레드 환경에서의 큐 사용은 ConcurrentQueue<T> 사용을 고려하세요.

Buy me a coffee Buy me a coffee
DictionaryStack