실행 가능한 C# 문서: Queue

Q: C#에서 Queue란 무엇인가요?

System.Collections.Generic의 Queue 는 선입선출(FIFO) 컬렉션입니다. Enqueue는 뒤에 항목을 추가하고, Dequeue는 앞의 항목을 제거해 반환하며, Peek은 앞의 항목을 제거하지 않고 반환합니다. 셋 모두 상수 시간이 걸립니다.

Q: C#에서 빈 큐에 Dequeue하면 어떻게 되나요?

빈 큐에 대한 Dequeue와 Peek은 InvalidOperationException을 던집니다. 먼저 queue.Count > 0을 확인하거나, 예외 대신 false를 반환하는 TryDequeue(out var item)과 TryPeek(out var item)을 쓰세요(.NET Core 2.0부터 사용 가능).

Q: Peek과 Dequeue의 차이는 무엇인가요?

Peek은 앞의 항목을 반환하고 큐에 그대로 두므로, 두 번 호출하면 같은 항목을 반환합니다. Dequeue는 앞의 항목을 반환하고 제거하므로, 다음 호출은 그 뒤의 항목을 반환합니다.

Q: C#의 Queue 는 스레드로부터 안전한가요?

아니요. 두 스레드가 같은 Queue 에 동시에 Enqueue나 Dequeue를 호출하면 큐가 손상될 수 있습니다. Enqueue와 TryDequeue를 여러 스레드에서 안전하게 호출할 수 있는 System.Collections.Concurrent의 ConcurrentQueue 를 쓰거나, 일반 큐에 대한 모든 접근을 lock으로 감싸세요.

Q: List 대신 Queue를 쓰는 이유는 무엇인가요?

List 의 첫 항목을 RemoveAt(0)으로 제거하면 다른 모든 항목이 이동하므로 리스트가 커질수록 느려집니다. Queue 는 앞에서 상수 시간에 제거하며, API가 의도를 드러냅니다. 항목은 도착 순서대로 처리됩니다.

Queue<T>는 창구 앞의 줄처럼 동작합니다. 처음 추가된 항목이 처음으로 꺼내집니다(FIFO, 선입선출). Enqueue로 뒤에 추가하고 Dequeue로 앞에서 꺼내며, 둘 다 상수 시간입니다.

Enqueue, Dequeue, Peek

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var printJobs = new Queue<string>();
        printJobs.Enqueue("invoice.pdf");
        printJobs.Enqueue("photo.png");
        printJobs.Enqueue("report.docx");

        Console.WriteLine("Waiting: " + printJobs.Count);
        Console.WriteLine("Next up: " + printJobs.Peek()); // look, do not remove

        string job = printJobs.Dequeue();                   // remove the front
        Console.WriteLine("Printing " + job);
        Console.WriteLine("Next up: " + printJobs.Peek());

        while (printJobs.Count > 0)
        {
            Console.WriteLine("Printing " + printJobs.Dequeue());
        }
        Console.WriteLine("Waiting: " + printJobs.Count);
    }
}

출력:

Waiting: 3
Next up: invoice.pdf
Printing invoice.pdf
Next up: photo.png
Printing photo.png
Printing report.docx
Waiting: 0

Peek은 다음 항목을 확정하기 전에 무엇을 할지 정할 때 쓰고, Dequeue는 확정합니다. 빌 때까지 꺼내는 while (queue.Count > 0) 루프가 큐를 처리하는 표준 방법이며, 루프 본문이 항목을 더 넣어도 계속 동작합니다. foreach에서는 이것이 허용되지 않습니다.

빈 큐 예외와 TryDequeue

빈 큐에 대한 Dequeue와 Peek은 InvalidOperationException을 던집니다. 참조 형식이라도 "비었으면 null" 같은 동작은 없습니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tickets = new Queue<int>();

        try
        {
            tickets.Dequeue();
        }
        catch (InvalidOperationException e)
        {
            Console.WriteLine("Caught " + e.GetType().Name);
        }

        tickets.Enqueue(41);
        tickets.Enqueue(42);

        int ticket;
        while (tickets.TryDequeue(out ticket))
        {
            Console.WriteLine("Serving ticket " + ticket);
        }

        Console.WriteLine(tickets.TryPeek(out ticket)); // false: empty
    }
}

출력:

Caught InvalidOperationException
Serving ticket 41
Serving ticket 42
False

TryDequeue와 TryPeek은 항목이 있으면 true를 반환하고 out 변수를 설정하며, 큐가 비었으면 false를 반환합니다. .NET Core 2.0에서 추가되었으므로, 이전 .NET Framework 코드에서는 Dequeue를 호출하기 전에 Count > 0을 확인하세요.

큐 안을 들여다보기

큐는 아무것도 제거하지 않고 열거할 수 있습니다. foreach, ToArray, Contains는 모두 앞에서 뒤로 항목을 봅니다.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = new Queue<string>(new[] { "Ana", "Ben", "Chloe" });

        foreach (string name in line)
        {
            Console.Write(name + " ");
        }
        Console.WriteLine();

        Console.WriteLine(line.Contains("Ben"));
        string[] snapshot = line.ToArray();
        Console.WriteLine(snapshot[0] + " is first, " + snapshot.Length + " in line");
        Console.WriteLine(line.Count); // nothing was removed
    }
}

출력:

Ana Ben Chloe 
True
Ana is first, 3 in line
3

인덱스는 없습니다. line[1]은 컴파일되지 않고, 중간의 항목을 제거할 수도 없습니다. 둘 중 하나가 필요하다면 그 데이터는 사실 큐가 아니니 List<T>나 LinkedList<T>를 쓰세요. 다른 컬렉션처럼 같은 큐에 대한 foreach 안에서 넣거나 꺼내면 InvalidOperationException이 발생합니다.

큐를 이용한 너비 우선 탐색

큐의 순서는 너비 우선 탐색에 딱 필요한 것입니다. 한 단계 떨어진 모든 것을 방문하고, 그다음 두 단계 떨어진 모든 것을 방문하는 식입니다. 여기서는 작은 네트워크에서 Ana와 다른 모든 사람 사이에 몇 단계의 연결이 있는지 찾습니다:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var friends = new Dictionary<string, string[]>
        {
            ["Ana"] = new[] { "Ben", "Chloe" },
            ["Ben"] = new[] { "Ana", "Dev" },
            ["Chloe"] = new[] { "Ana", "Dev", "Eli" },
            ["Dev"] = new[] { "Ben", "Chloe", "Fay" },
            ["Eli"] = new[] { "Chloe" },
            ["Fay"] = new[] { "Dev" },
        };

        var distance = new Dictionary<string, int> { ["Ana"] = 0 };
        var queue = new Queue<string>();
        queue.Enqueue("Ana");

        while (queue.Count > 0)
        {
            string person = queue.Dequeue();
            foreach (string next in friends[person])
            {
                if (!distance.ContainsKey(next))
                {
                    distance[next] = distance[person] + 1;
                    queue.Enqueue(next);
                }
            }
        }

        foreach (var pair in distance)
        {
            Console.WriteLine(pair.Key + ": " + pair.Value + " step(s) from Ana");
        }
    }
}

출력:

Ana: 0 step(s) from Ana
Ben: 1 step(s) from Ana
Chloe: 1 step(s) from Ana
Dev: 2 step(s) from Ana
Eli: 2 step(s) from Ana
Fay: 3 step(s) from Ana

각 사람은 처음 도달했을 때 한 번만 큐에 들어가고, 큐가 발견한 순서대로 돌려주므로 처음 도달한 경로가 항상 최단 경로입니다. 큐를 Stack으로 바꾸면 같은 루프가 깊이 우선 탐색이 되며, 더 이상 최단 경로를 찾지 못합니다.

같은 모양으로 트리의 레벨 순서 순회, 격자의 영역 채우기, 링크 크롤링을 처리합니다. 큐에 항목 하나를 넣고 시작해서, 비어 있지 않은 동안 하나를 꺼내고 방문하지 않은 이웃을 넣습니다.

선입선출 작업에서 Queue와 List

Add와 RemoveAt(0)으로 List<T>를 큐처럼 쓸 수 있지만, RemoveAt(0)은 남은 모든 요소를 한 칸씩 당깁니다. 그렇게 100,000개 항목의 리스트를 비우면 요소 이동이 약 50억 번 일어나고, Queue<T>는 상수 시간 단계 100,000번이면 됩니다. 큐는 내부적으로 순환 버퍼입니다. 배열의 머리 인덱스와 꼬리 인덱스를 추적하며 가득 찼을 때만 다시 할당합니다.

연산	`Queue<T>`	큐로 쓰는 `List<T>`
뒤에 추가	`Enqueue`, O(1)	`Add`, O(1)
앞에서 제거	`Dequeue`, O(1)	`RemoveAt(0)`, O(n)
앞 항목 보기	`Peek`	`list[0]`
인덱스 접근	없음	`list[i]`

여러 스레드를 위한 ConcurrentQueue

Queue<T>는 스레드로부터 안전하지 않습니다. 여러 스레드가 항목을 넣거나 꺼낸다면 System.Collections.Concurrent의 ConcurrentQueue<T>를 쓰세요. Enqueue, TryDequeue, TryPeek은 있지만 Dequeue는 없습니다. 다른 스레드가 있으면 "Count 확인 뒤 Dequeue"가 두 호출 사이에서 실패할 수 있기 때문입니다.

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        var events = new ConcurrentQueue<int>();

        // 4 parallel iterations each add 1,000 items.
        Parallel.For(0, 4, worker =>
        {
            for (int i = 0; i < 1000; i++) events.Enqueue(i);
        });
        Console.WriteLine(events.Count);

        int total = 0;
        int item;
        while (events.TryDequeue(out item)) total++;
        Console.WriteLine(total + " processed");
    }
}

출력:

4000
4000 processed

ConcurrentQueue<T> 대신 일반 Queue<T>를 쓰면 타이밍에 따라 개수가 틀리거나 프로그램이 예외를 던집니다. 계속 돌지 않고 작업을 기다려야 하는 생산자와 소비자 스레드에는 BlockingCollection<T>(기본적으로 ConcurrentQueue<T>를 감쌉니다)나 System.Threading.Channels가 대기와 완료 기능을 더해 줍니다. 일반 컬렉션을 직접 보호하는 방법은 lock을 참고하세요.

PriorityQueue

항목이 도착 순서가 아니라 우선순위로 나가야 한다면(가장 급한 티켓 먼저, 다익스트라 알고리즘의 지금까지의 최단 경로), .NET 6 이상은 PriorityQueue<TElement, TPriority>를 제공합니다. 가장 낮은 우선순위 값이 먼저 나옵니다:

var triage = new PriorityQueue<string, int>();
triage.Enqueue("sprained ankle", 3);
triage.Enqueue("chest pain", 1);
triage.Enqueue("headache", 5);

while (triage.TryDequeue(out string patient, out int priority))
{
    Console.WriteLine($"{priority}: {patient}");
}
// 1: chest pain
// 3: sprained ankle
// 5: headache

우선순위가 같은 항목은 어떤 순서로든 나올 수 있습니다. 도착 순서로 동점을 가려야 한다면 우선순위에 일련번호를 추가하세요.

흔한 실수

확인하지 않고 꺼내기. 빈 큐는 InvalidOperationException을 던집니다. Count > 0으로 반복하거나 TryDequeue를 쓰세요.
Peek을 호출하고 항목이 사라지리라 기대하기. Dequeue만 제거합니다.
큐에 대한 foreach 안에서 넣기. 예외가 발생합니다. 대신 while 루프로 처리하세요.
스레드 간에 Queue<T> 공유하기. ConcurrentQueue<T>나 lock을 쓰세요.
큰 데이터에서 List.RemoveAt(0)을 큐로 쓰기. 호출마다 O(n)입니다.

자주 묻는 질문

C#에서 Queue란 무엇인가요?

System.Collections.Generic의 Queue<T>는 선입선출(FIFO) 컬렉션입니다. Enqueue는 뒤에 항목을 추가하고, Dequeue는 앞의 항목을 제거해 반환하며, Peek은 앞의 항목을 제거하지 않고 반환합니다. 셋 모두 상수 시간이 걸립니다.

C#에서 빈 큐에 Dequeue하면 어떻게 되나요?

빈 큐에 대한 Dequeue와 Peek은 InvalidOperationException을 던집니다. 먼저 queue.Count > 0을 확인하거나, 예외 대신 false를 반환하는 TryDequeue(out var item)과 TryPeek(out var item)을 쓰세요(.NET Core 2.0부터 사용 가능).

Peek과 Dequeue의 차이는 무엇인가요?

Peek은 앞의 항목을 반환하고 큐에 그대로 두므로, 두 번 호출하면 같은 항목을 반환합니다. Dequeue는 앞의 항목을 반환하고 제거하므로, 다음 호출은 그 뒤의 항목을 반환합니다.

C#의 Queue<T>는 스레드로부터 안전한가요?

아니요. 두 스레드가 같은 Queue<T>에 동시에 Enqueue나 Dequeue를 호출하면 큐가 손상될 수 있습니다. Enqueue와 TryDequeue를 여러 스레드에서 안전하게 호출할 수 있는 System.Collections.Concurrent의 ConcurrentQueue<T>를 쓰거나, 일반 큐에 대한 모든 접근을 lock으로 감싸세요.

List 대신 Queue를 쓰는 이유는 무엇인가요?

List<T>의 첫 항목을 RemoveAt(0)으로 제거하면 다른 모든 항목이 이동하므로 리스트가 커질수록 느려집니다. Queue<T>는 앞에서 상수 시간에 제거하며, API가 의도를 드러냅니다. 항목은 도착 순서대로 처리됩니다.