[유니티 / C#] Deque (덱)

⭐ Deque (덱)

양쪽 모두에서 삽입과 삭제가 가능한 자료구조입니다. 큐와 스택이 합쳐진 형태입니다.

 

C# 표준 라이브러리에는 Deque(덱) 자료구조를 지원하지 않습니다.

비슷한 기능을 담당하는 자료구조를 이용하거나 직접 Deque(덱) 클래스를 구현해서 사용해야합니다.

 

 

 

커스텀 Deque 구현하기

---

● 원형 배열을 이용하여 구현

    ○ 원형 배열: 맨 앞(head)과 맨 뒤(tail)를 지칭하는 포인터를 이용해 원형처럼 취급하는 배열

        ■ 마지막 인덱스를 넘어가면 다시 0으로 되돌아옴

internal class Program
{
    static void Main(string[] args)
    {
        Deque<int> deque = new Deque<int>();


        deque.AddFirst(5);
        deque.AddFirst(7);
        deque.AddFirst(1);
        deque.AddLast(2);
        deque.AddLast(8);

        Console.WriteLine($"1. RemoveFirst: {deque.RemoveFirst()}");    //1. RemoveFirst: 1
        Console.WriteLine($"2. RemoveFirst: {deque.RemoveFirst()}");    //2. RemoveFirst: 7
        Console.WriteLine($"3. RemoveLast: {deque.RemoveLast()}");      //3. RemoveLast: 8

    }
}

public class Deque<T>
{
    private const int INITSIZE = 16;    //초기화 크기

    private T[] buffer;                 //객체를 담을 원형배열
    private int head;                   //제일 앞을 담당
    private int tail;                   //제일 뒤를 담당
    private int count;                  //현재 요소 개수
    public int Count
    {
        get { return count; }
        private set { count = value; }
    }

    public Deque()
    {
        buffer = new T[INITSIZE];
        head = 0;
        tail = 0;
        Count = 0;
    }

    public void AddFirst(T item)
    {
        Resize();
        head = (head - 1 + buffer.Length) % buffer.Length;
        buffer[head] = item;
        Count++;
    }

    public void AddLast(T item)
    {
        Resize();
        buffer[tail] = item;
        tail = (tail + 1) % buffer.Length;
        Count++;
    }

    public T RemoveFirst()
    {
        if (Count == 0)
            throw new Exception();

        var value = buffer[head];
        head = (head + 1) % buffer.Length;
        Count--;
        return value;
    }

    public T RemoveLast()
    {
        if (Count == 0)
            throw new Exception();

        tail = (tail - 1 + buffer.Length) % buffer.Length;
        var value = buffer[tail];
        Count--;
        return value;
    }

    //현재 배열의 크기보다 커져야 할 경우 새로 생성
    public void Resize()
    {
        //배열이 꽉 차면
        if(Count == buffer.Length)
        {
            var newBuf = new T[buffer.Length * 2];

            //새로 만든 버퍼에는 0부터 선형으로 담기게 함
            for (int i = 0; i < Count; i++)
            {
                newBuf[i] = buffer[(head + i) % buffer.Length];
            }
            buffer = newBuf;
            head = 0;
            tail = Count;
        }
    }
}