C# Stack<T>와 Queue<T> 성능 비교 및 활용 사례

C#에서 Stack<T>와 Queue<T>는 각각 LIFO, FIFO 패턴을 구현하는 대표 컬렉션입니다. 두 자료구조는 핵심 연산이 상수 시간으로 매우 빠르며, 시나리오에 맞는 선택이 성능과 코드 가독성을 모두 높입니다. 본 글은 성능 특성, 올바른 활용 사례, 미세 최적화 팁, 간단한 벤치마크 예시를 다룹니다.

1. 핵심 요약

Stack<T>는 마지막에 들어온 요소를 먼저 처리(LIFO)하고, Queue<T>는 먼저 들어온 요소를 먼저 처리(FIFO)합니다. Push/Pop, Enqueue/Dequeue, Peek는 모두 평균 O(1)입니다. 초기 용량 지정과 예외 없는 Try 계열 메서드가 실무 성능에 유의미한 차이를 만듭니다.

2. 시간·공간 복잡도와 내부 동작

Stack<T>와 Queue<T>는 내부적으로 배열 기반이며 용량이 꽉 차면 보통 2배로 확장합니다. 확장 시 복사 비용이 발생하지만, 암ORTized 관점에서 Push/Pop, Enqueue/Dequeue, Peek 모두 O(1)입니다. Contains, ToArray 등 순회 연산은 O(n)입니다. 생성 시 용량을 지정하거나 EnsureCapacity, TrimExcess로 메모리 사용을 조절하면 안정적인 지연 시간과 힙 압박 감소에 도움이 됩니다.

3. 언제 Stack, 언제 Queue

Stack<T>: 되돌리기(Undo), 수식 평가, DFS, 콜스택 유사 처리처럼 최근 항목을 우선 처리할 때 적합합니다. Queue<T>: 작업 큐, 메시지 처리, BFS, 너비 우선 탐색처럼 도착 순서를 보장해야 할 때 적합합니다. 목적에 맞는 자료구조를 선택하면 불필요한 복사를 줄이고 코드 의도를 명확히 할 수 있습니다.

4. 기본 사용 예시 (Push/Pop, Enqueue/Dequeue)

using System;
using System.Collections.Generic;

class Basics
{
    static void Main()
    {
        var stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        Console.WriteLine(stack.Peek()); // 2
        Console.WriteLine(stack.Pop());  // 2

        var queue = new Queue<int>();
        queue.Enqueue(1);
        queue.Enqueue(2);
        Console.WriteLine(queue.Peek());    // 1
        Console.WriteLine(queue.Dequeue()); // 1

        // 예외 없는 Try 계열 (빈 컬렉션 대비)
        if (stack.TryPop(out var v))
            Console.WriteLine(v);
        if (queue.TryDequeue(out var w))
            Console.WriteLine(w);
    }
}

5. 실전 활용: DFS(깊이 우선) with Stack<T>

using System;
using System.Collections.Generic;

class DFS
{
    static void Run(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int>();
        var stack = new Stack<int>();
        stack.Push(start);

        while (stack.Count > 0)
        {
            int node = stack.Pop();
            if (!visited.Add(node)) continue;
            Console.WriteLine($"Visit: {node}");

            // 인접 노드를 역순으로 넣으면 작은 번호를 우선 탐색하는 등 순서 제어 가능
            var neighbors = graph.TryGetValue(node, out var list) ? list : Array.Empty<int>();
            for (int i = neighbors.Count - 1; i >= 0; i--)
                stack.Push(neighbors[i]);
        }
    }
}

6. 실전 활용: BFS(너비 우선) with Queue<T>

using System;
using System.Collections.Generic;

class BFS
{
    static void Run(Dictionary<int, List<int>> graph, int start)
    {
        var visited = new HashSet<int> { start };
        var q = new Queue<int>();
        q.Enqueue(start);

        while (q.Count > 0)
        {
            int node = q.Dequeue();
            Console.WriteLine($"Visit: {node}");

            if (!graph.TryGetValue(node, out var neighbors)) continue;
            foreach (var next in neighbors)
            {
                if (visited.Add(next))
                    q.Enqueue(next);
            }
        }
    }
}

7. 미세 최적화 팁

1) 예상 크기가 있다면 생성자에 용량을 지정하거나 EnsureCapacity를 사용합니다. 2) 빈 컬렉션에서 Pop/Dequeue는 예외가 발생하므로 TryPop, TryDequeue를 사용해 분기 예측 실패와 예외 비용을 피합니다. 3) 빈번한 Contains 호출은 O(n)이므로 필요 시 별도 HashSet과 병행합니다. 4) 컬렉션을 재사용하면 할당과 GC를 줄일 수 있습니다. 5) FIFO/LIFO 외 목적(중간 삭제/삽입)이면 다른 컬렉션(List, LinkedList 등)을 검토합니다.

8. BenchmarkDotNet으로 간단 성능 비교

아래 벤치마크는 동일한 N개 요소에 대해 Stack Push/Pop, Queue Enqueue/Dequeue를 비교합니다. 두 컬렉션 모두 평균 O(1)이므로 결과는 비슷하게 나오며, 런타임/CPU/데이터 패턴에 따라 미세한 차이가 납니다.

using System;
using System.Collections.Generic;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

[MemoryDiagnoser]
public class StackQueueBench
{
    [Params(1_000, 100_000)]
    public int N;

    private int[] data;

    [GlobalSetup]
    public void Setup()
    {
        data = new int[N];
        for (int i = 0; i < N; i++) data[i] = i;
    }

    [Benchmark]
    public int Stack_PushPop()
    {
        var s = new Stack<int>(N); // 초기 용량 지정으로 재할당 최소화
        for (int i = 0; i < N; i++) s.Push(data[i]);
        int sum = 0;
        while (s.Count > 0) sum += s.Pop();
        return sum; // 결과를 반환하여 최적화 방지
    }

    [Benchmark]
    public int Queue_EnqueueDequeue()
    {
        var q = new Queue<int>(N);
        for (int i = 0; i < N; i++) q.Enqueue(data[i]);
        int sum = 0;
        while (q.Count > 0) sum += q.Dequeue();
        return sum;
    }
}

public class Program
{
    public static void Main(string[] args)
        => BenchmarkRunner.Run<StackQueueBench>();
}

Tip: 로컬 환경에서 릴리스 빌드/64비트/서버 GC 설정으로 측정하세요. 또한 다양한 N과 데이터 패턴(랜덤, 정렬 등)으로 실험하면 편차를 파악할 수 있습니다.

9. 스레드 환경에서의 선택

Stack<T>와 Queue<T>는 스레드 안전하지 않습니다. 멀티스레드에서는 ConcurrentStack<T>와 ConcurrentQueue<T>를 사용합니다. 블로킹이 필요한 경우 Channel<T> 또는 BlockingCollection<T>(ConcurrentQueue 기반)을 고려하면 생산자-소비자 시나리오를 간단히 구현할 수 있습니다.

10. 결론

두 컬렉션은 O(1) 평균 성능과 간결한 API로 대부분의 LIFO/FIFO 문제를 빠르게 해결합니다. 올바른 선택과 간단한 최적화(용량 사전 지정, Try 메서드, 재사용)만으로도 지연 시간을 안정화하고 힙 압박을 줄일 수 있습니다. 업무 시나리오에 맞춰 Stack과 Queue를 명확히 구분해 사용하시기 바랍니다.