Unity 개발자를 위한 C# Deque(덱) 구현

Deque(덱)은 다양한 프로그래밍 환경에서 반복적으로 등장하는 유용한 자료구조입니다. 스택(Stack)은 데이터의 삽입과 삭제가 하나의 끝(top)에서만 이루어지고, 큐(Queue)는 한쪽 끝에서 삽입(enqueue), 반대쪽 끝에서 삭제(dequeue)가 이루어집니다. 반면 Deque는 앞(front)과 뒤(back) 양쪽 끝에서 모두 삽입과 삭제가 가능하다는 점이 가장 큰 특징입니다. 즉, 하나의 구조로 스택과 큐의 동작을 모두 표현할 수 있는 유연한 자료구조입니다.

 

이번 글에서는 덱의 개념과 특징을 정리하고, C# 배열 기반 원형 버퍼를 이용해 직접 구현하는 방법을 살펴보겠습니다.

---

1. Deque 구조와 동작 방식

Deque는 다음 네 가지 연산을 지원합니다:

• 앞쪽 삽입(AddFront)
• 뒤쪽 삽입(AddBack)
• 앞쪽 제거(RemoveFront)
• 뒤쪽 제거(RemoveBack)

간단한 예시로 동작을 이해해 봅니다.

AddFront(A)
AddFront(B)
AddBack(C)
AddBack(D)
AddBack(E)

Deque 상태: [B, A, C, D, E]

RemoveFront() → B
RemoveBack()  → E
RemoveBack()  → D
RemoveFront() → A
RemoveBack()  → C

이처럼 Deque는 양방향에서 데이터를 처리할 수 있어 단방향 자료구조로는 구현하기 번거로운 특정 상황에서 유용하게 활용될 수 있습니다.

---

2. Deque가 활용되는 대표적인 사례

• Undo/Redo 시스템 (앞/뒤로 이동 가능한 기록 구조)
• 최근 입력 히스토리
• 카메라 이동 이력 저장 및 되돌리기
• 게임 AI의 양방향 탐색 버퍼

큐나, 스택처럼 사용할 수도 있고, 두 동작이 모두 필요한 복합 로직에서도 사용할 수 있습니다.

---

3. Deque가 제공하는 기능 (구현 기준)

• AddFront : 앞쪽에 요소 추가
• AddBack : 뒤쪽에 요소 추가
• RemoveFront : 앞쪽 요소 제거
• RemoveBack : 뒤쪽 요소 제거
• PeekFront : 앞쪽 요소 조회
• PeekBack : 뒤쪽 요소 조회
• Count : 전체 요소 개수
• IsEmpty : Deque가 비었는지 여부 확인

이번 구현은 원형 배열 기반 구조로, 배열 확장을 제외하면 GC가 발생하지 않는 고성능 구조입니다.

---

4. Deque 내부 동작 방식

Deque(덱)는 내부적으로 원형 배열(circular buffer) 을 사용하여 앞쪽(front)과 뒤쪽(back) 양쪽에서 데이터를 O(1)에 가깝게 삽입·삭제할 수 있는 구조입니다. 이 구조는 front, rear 인덱스와 현재 요소 개수인 count 값으로 관리됩니다.

 

배열을 단순히 앞뒤로만 사용하면 시작이나 끝에서 공간이 낭비될 수 있는데, 원형 배열을 사용하면 index가 배열 끝에 도달하더라도 자동으로 0으로 돌아가며 빈 공간을 반복적으로 재사용할 수 있습니다.

 

덱은 뒤쪽 삽입 시 rear를 증가시키고, 앞쪽 삽입 시 front를 감소시키며, 삭제할 때는 반대로 해당 방향의 인덱스를 이동시키는 방식으로 동작합니다. 중간 요소는 절대 이동시키지 않기 때문에 반복적인 추가/삭제 상황에서도 매우 효율적으로 작동합니다.

 

✔ 초기 상태

• Deque 비어 있음
• front = 0, rear = 0, count = 0

 

✔ A 추가 (AddBack)

• 현재 rear 위치(0)에 A 삽입
• rear 1 증가, count 1 증가
• front = 0, rear = 1, count = 1

 

✔ 뒤쪽에 B 추가 (AddBack)

• rear 위치(1)에 B 삽입
• rear 1 증가, count 1 증가
• front = 0, rear = 2, count = 2

 

✔ 앞쪽에 C 추가 (AddFront)

• front를 왼쪽으로 이동 → (front - 1 + 4) % 4 = 3
• index 3 위치에 C 삽입, count 1 증가
• front = 3, rear = 2, count = 3

 

✔ 뒤에서 제거 (RemoveBack)

• rear 1 감소
• 감소된 rear 자리에 있는 요소 제거, count 1 감소
• front = 3, rear = 1, count = 2

 

✔ 앞에서 제거 (RemoveFront)

• front 위치 3에 있는 C 제거
• front → (front + 1) % 4 = 0, count 1 감소
• front = 0, rear = 1, count = 1 (남은 요소: A)

 

• 앞쪽에 추가할 때는 front를 1 감소시킨 위치에 데이터를 넣고,
  뒤쪽에 추가할 때는 현재 rear 위치에 데이터를 넣은 뒤 rear를 1 증가시킵니다.
• 앞쪽에서 제거할 때는 front 위치의 데이터를 꺼낸 후 front를 1 증가시키고,
  뒤쪽에서 제거할 때는 rear를 1 감소시킨 위치에서 데이터를 꺼냅니다.

---

5. C# 배열로 Deque 직접 구현하기

using System;

namespace Daebak.Common.Collections
{
    /// <summary>
    /// 양방향 큐(Deque) 구현
    /// </summary>
    public class Deque<T>
    {
        private T[] _items;      // 내부 배열(원형 버퍼)
        private int _front;      // 가장 앞 요소의 인덱스
        private int _rear;       // 다음 요소가 들어갈 뒤쪽 인덱스
        private int _count;      // 저장된 요소 개수
        public int Count => _count;

        private const int DEFAULT_CAPACITY = 8;

        public Deque(int capacity = DEFAULT_CAPACITY)
        {
            _items = new T[capacity];
            _front = 0;
            _rear = 0;
            _count = 0;
        }

        /// <summary>
        /// 앞쪽에 요소 추가
        /// </summary>
        public void AddFront(T item)
        {
            EnsureCapacity(); // 공간 부족 시 배열 확장

            // 앞쪽 인덱스를 원형으로 한 칸 뒤로 이동
            _front = (_front - 1 + _items.Length) % _items.Length;
            _items[_front] = item;
            _count++;
        }

        /// <summary>
        /// 뒤쪽에 요소 추가
        /// </summary>
        public void AddBack(T item)
        {
            EnsureCapacity(); // 공간 부족 시 배열 확장

            _items[_rear] = item;                // 현재 rear 위치에 삽입
            _rear = (_rear + 1) % _items.Length; // rear 인덱스를 원형으로 이동
            _count++;
        }

        /// <summary>
        /// 앞쪽에서 요소 제거 및 반환
        /// </summary>
        public T RemoveFront()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("Deque가 비어 있습니다.");
            }

            T item = _items[_front];              // front 위치의 요소 가져오기
            _items[_front] = default!;            // GC를 위해 참조 제거
            _front = (_front + 1) % _items.Length; // front 인덱스 증가
            _count--;

            return item;
        }

        /// <summary>
        /// 뒤쪽에서 요소 제거 및 반환
        /// </summary>
        public T RemoveBack()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("Deque가 비어 있습니다.");
            }

            // rear는 삽입 위치를 가리키므로 제거 시 먼저 한 칸 뒤로 이동
            _rear = (_rear - 1 + _items.Length) % _items.Length;

            T item = _items[_rear];   // rear 위치의 요소 가져오기
            _items[_rear] = default!; // GC를 위해 참조 제거
            _count--;

            return item;
        }

        /// <summary>
        /// 앞쪽 요소 확인(삭제 안 함)
        /// </summary>
        public T PeekFront()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("Deque가 비어 있습니다.");
            }

            return _items[_front];
        }

        /// <summary>
        /// 뒤쪽 요소 확인(삭제 안 함)
        /// </summary>
        public T PeekBack()
        {
            if (_count == 0)
            {
                throw new InvalidOperationException("Deque가 비어 있습니다.");
            }

            // rear는 항상 '다음 삽입 위치'를 가리키므로 실제 마지막 요소는 -1 위치
            int idx = (_rear - 1 + _items.Length) % _items.Length;
            return _items[idx];
        }

        /// <summary>
        /// 비었는지 여부
        /// </summary>
        public bool IsEmpty()
        {
            return _count == 0;
        }

        /// <summary>
        /// 내부 배열 확장 (2배로 확장)
        /// </summary>
        private void EnsureCapacity()
        {
            // 아직 공간이 있다면 확장 불필요
            if (_count < _items.Length)
            {
                return;
            }

            int newSize = _items.Length * 2;
            T[] newArray = new T[newSize];

            // front 기준으로 순서대로 재배치 (원형 인덱스를 풀어줌)
            for (int i = 0; i < _count; i++)
            {
                newArray[i] = _items[(_front + i) % _items.Length];
            }

            // 새로운 배열로 교체
            _items = newArray;
            _front = 0;          // 정렬했으므로 앞은 0
            _rear = _count;      // rear는 count 위치
        }
    }
}

---

6. 유니티(Unity) 환경에서 테스트해 보기

using UnityEngine;
using Daebak.Common.Collections;

public class Test_Deque : MonoBehaviour
{
    void Start()
    {
        Deque<int> deque = new Deque<int>();

        deque.AddBack(10);
        deque.AddBack(20);
        deque.AddFront(5);
        deque.AddFront(1);

        Debug.Log("Front: " + deque.PeekFront()); // 1
        Debug.Log("Back: " + deque.PeekBack());   // 20

        Debug.Log("RemoveFront: " + deque.RemoveFront()); // 1
        Debug.Log("RemoveBack: " + deque.RemoveBack());   // 20

        Debug.Log("RemoveFront: " + deque.RemoveFront()); // 5
        Debug.Log("RemoveBack: " + deque.RemoveBack());   // 10
    }
}

실행 결과

Front: 1
Back: 20
RemoveFront: 1
RemoveBack: 20
RemoveFront: 5
RemoveBack: 10

 

---

마무리

Deque는 앞과 뒤 양쪽에서 데이터를 처리할 수 있어 매우 유연한 자료구조입니다.
큐와 스택 구조를 모두 활용할 수 있기 때문에, 단방향 자료구조로 구현하기 번거로운 특정 상황에서 유용하게 사용할 수 있습니다.

 

※ 다음 글에서는 HashSet(해시 셋) 구조를 살펴보며, 순서 기반 자료구조에서 벗어나 데이터의 중복 제거와 빠른 포함 여부 판단을 중심으로 정리합니다.