2025-03-24 <C# 스택 클래스와 성능 최적화>

C# 스택 클래스와 성능 최적화에 대하여

큐(Queue)와 스택(Stack)의 성능 비교하기

큐와 스택의 차이점은 명확하다.
큐는 선입선출이고, 스택은 후입선출의 구조를 가진 자료형이다.

사실 이런 건 너무 흔히 알려진 개념이라, 굳이 블로그에까지 정리할 필요는 없을 것이다.

대신 오늘의 글에서 정리해보고 싶은 건 큐와 스택의 원리에 의해 벌어지는 성능 차이에 대한 것이다.

예를 들어보자.

큐와 스택을 구현해야 한다고 했을 때 가장 간단한 방식은 무엇일까.
아마 배열을 고르는 게 보편적일 것이다.

index : [0] [1] [2] [3] [4]
value :  4   9   2   5   0

 

여기서 Dequeue() 혹은 Pop()을 사용해본다고 상상해보자.
4번 인덱스의 0을 넣었다 빼는 건 다른 인덱스 요소에 아무런 영향도 끼치지 않지만,
0번 인덱스에서 4를 넣거나 빼는 건 다른 요소들을 한 칸씩 앞으로 당겨야하므로 성능에 영향을 끼친다.

 

즉, 큐는 배열로 구현 시 dequeue(shift)로 인한 성능 저하 우려가 있다.

그렇다면 실제 C#의 Queue<T> 클래스는 어떻게 Dequeue()를 구현하고 있을까?

C#의 Queue 내부 구조

• Queue<T> 클래스에서는 내부적으로 배열(Array)을 사용한다.
• 하지만 Enqueue와 Dequeue 시 포인터(head, tail)를 직접 이동시키는 방식을 써서, shift()처럼 모든 요소를 밀지 않는다.
• 포인터(head, tail)가 마지막 인덱스에 도달하면 다시 0번째 인덱스로 순환하므로, 원형 배열이라고 볼 수 있다.

원형 배열 방식이란?

배열 구조 예시:

[ 10 ][ 20 ][ 30 ][   ][   ]
   ↑     ↑
 head  tail

• head와 tail이라는 이름의 추가 포인터를 사용한다.
  • Enqueue → tail을 증가시키며 값 삽입
  • Dequeue → head를 증가시키며 값 제거
• 배열 끝에 도달하면 처음으로 다시 돌아오는 "순환(circular)" 구조를 이룬다.
• 배열을 밀 필요가 없어서 Dequeue의 시간 복잡도도 O(1)으로 나타낼 수 있다.
• 다만 배열이 꽉 차면 resize가 일어날 수 있다.

실제로 확인해보기

실제 Queue<T>를 살펴보자.

private T[] _array; // 내부 배열
private int _head;
private int _tail;
private int _size;

배열 크기: 5

초기 상태:
[ ][ ][ ][ ][ ]
 ↑           ↑
head        tail

• head: dequeue 위치
• tail: enqueue 위치

논리적으로 연결된 배열 + head/tail 포인터

• 기본 구조는 단순한 배열
• 처음과 끝이 연결된 것처럼 인덱스를 회전시키는 구조
• 이를 구현하기 위해 head(읽는 위치)와 tail(쓰는 위치)이라는 별도의 인덱스를 관리

작동 방식

1. Enqueue (삽입)

queue.Enqueue(10); // tail = 0
queue.Enqueue(20); // tail = 1
queue.Enqueue(30); // tail = 2

[10][20][30][ ][ ]
 ↑           ↑
head        tail

→ 삽입할 때는 tail을 증가시킨다.

public void Enqueue(T item)
{
    if (_size == _array.Length)
    {
        Grow(_size + 1);
    }

    _array[_tail] = item;
    MoveNext(ref _tail);
    _size++;
    _version++;
}

2. Dequeue (제거)

queue.Dequeue(); // head = 0 → 제거 후 head = 1

[ ][20][30][ ][ ]
     ↑     ↑
   head   tail

→ 제거할 때는 head를 증가시킨다.

public T Dequeue()
{
    if (_size == 0)
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyQueue);

    T removed = _array[_head];
    _array[_head] = default!;
    _head = (_head + 1 == _array.Length) ? 0 : _head + 1;
    _size--;
    _version++;
    return removed;
}

 

_head = (_head + 1 == _array.Length) ? 0 : _head + 1;
삼항 연산자를 통해 head 포인터를 순환시킨다.

시각적 정리

[ ][A][B][C][ ]
   ↑       ↑
 head    tail

// enqueue D
[ ][A][B][C][D]
   ↑           ↑
 head         tail

// dequeue A
[ ][ ][B][C][D]
     ↑       ↑
   head     tail

// enqueue E
[E][ ][B][C][D]
 ↑         ↑
tail     head  ← 원형으로 순환됨