C# - 덱 (Deque : Double Ended Queue)

덱 (Deque : Double Ended Queue)

디큐? 데큐? 이런 식으로 읽는 줄 알았는데 덱이라고 읽는게 맞다고 한다.

어? 혹시 카드덱? 이라 생각할 수도 있지만 사실은 무관하다고 한다.

 

Deque는 임의 접근이 가능한 시퀀스 컨테이너로, 양 끝에서 삽입/삭제가 가능하다.

 

즉, 일반적인 Queue는 앞에서 꺼내고 뒤에서 넣는 구조(FIFO)지만, Deque는 앞/뒤 모두에서 자유롭게 삽입 및 삭제가 가능하다.

Stack + Queue의 기능을 모두 가졌다고 보면 된다.

 

표준 C 언어에서는 별도의 컨테이너 라이브러리가 없어 덱을 사용하려면 직접 구현하거나 외부 라이브러리를 써야 한다고 한다.

C++ 은 STL(Standard Template Library)에 std::deque 클래스를 제공한다고 한다.

Java에도 java.util.Deque 인터페이스가 존재하며,

Phython에도 collections 모듈에 deque 클래스를 제공한다.

 

그런데 왜 C#에는 없는 것인가...

 

---

 

Deque 구현하기

Deque를 직접 구현해보는 과제를 수행해자.

• 다음의 조건을 충족하는 Mydeque<T> 클래스를 구현하시오
  • 제네릭 컬렉션의 사용을 금지하며, 배열을 사용해 구현한다.
  • 클래스의 인스턴스 생성 시 최초 10의 크기를 가진다.
  • 배열의 크기를 넘어서 데이터를 추가할 경우, 배열에 빈 자리가 없다면 현재 배열의 크기의 2배만큼 재할당해야 한다.
  • 아래 필수 구현 메서드 외 내부 동작을 위한 필드 및 메서드 추가는 허용한다.
  • 구현 메서드
    • PushFront(T element) : 배열의 맨 앞에 데이터를 추가한다.
    • PushBack(T element) : 배열의 맨 뒤에 데이터를 추가한다.
    • PopFront() : 배열의 가장 앞의 데이터를 반환하고, 내부 배열에서 삭제한다.
    • PopBack() : 배열의 가장 뒤의 데이터를 반환하고, 내부 배열에서 삭제한다.
    • Clear() : 배열 내의 모든 데이터를 삭제한다.

 

음... 제네릭 컬렉션 금지...

과제 이름만 보고 쉽게 구현할 아이디어가 생각났었는데 바로 무산이 됐다.

가이드라인을 따라 작성해보자.

 

 

1. 제네릭 컬렉션 사용을 금지하며, 배열을 사용해 구현한다.

2. 클래스 인스턴스 생성시 최초 10의 크기를 가진다.

 

우선 이 두가지를 충족하는 MyDeque<T>의 필드, 프로퍼티, 생성자를 작성해보자

 

public class MyDeque<T>
{
    private T[] _array;
    private int _count;
    private int _size;

    public int Count { get { return _count; } }

    public MyDeque()
    {
        _count = 0;
        _size = 10;
        _array = new T[_size];
    }
}

 

MyDeque 클래스에는 제네릭 타입의 배열을 만들고,

그 배열의 크기값인 _size와, 실제 값이 들어가있는 인덱스의 수를 표시하는 _count로 관리할 거다.

 

생성자로 시작시

_count = 0;

_size = 10;

으로 초기화하고, _array를 초기 _size값으로 인스턴스 생성한다.

 

 

다음은 메서드들을 작성해 볼 것이다.

 

• 배열의 크기를 넘어서 데이터를 추가할 경우, 배열에 빈 자리가 없다면 현재 배열의 크기의 2배만큼 재할당해야 한다.
  • PushFront(T element) : 배열의 맨 앞에 데이터를 추가한다.
  • PushBack(T element) : 배열의 맨 뒤에 데이터를 추가한다.
  • PopFront() : 배열의 가장 앞의 데이터를 반환하고, 내부 배열에서 삭제한다.
  • PopBack() : 배열의 가장 뒤의 데이터를 반환하고, 내부 배열에서 삭제한다.
  • Clear() : 배열 내의 모든 데이터를 삭제한다.

 

이렇게 총 5개의 메서드를 작성해야하며, _count 크기에 따라 _size가 늘어나게 구현해야 한다.

또한 배열의 추가/삭제가 일어날 때에 인덱스가 뒤로 밀리거나 당겨지는 동작이 필요하기에

기존의 배열을 임시값에 복사한 뒤에 적용하는 방식으로 구현했다.

 

구현한 MyDeque 클래스 코드는 아래와 같다.

public class MyDeque<T>
{
    // 제네릭 컬렉션 사용 금지, 배열을 사용해 구현
    private T[] _array;
    private int _count;
    private int _size;

    public int Count { get { return _count; } }

    public MyDeque()
    {
        // 생성시 최초 10의 크기
        _count = 0;
        _size = 10;
        _array = new T[_size];
    }

    // 테스르를 위한 인덱서
    public T this[int index]
    {
        get
        {
            if (index < 0 || index >= _count)
                throw new IndexOutOfRangeException();
            return _array[index];
        }
    }

    // 배열의 크기를 넘어서 데이터를 추가할 경우, 배열의 빈자리가 없다면 현재 배열의 크기의 2배만큼 재할당
    public void PushFront(T el) // 배열의 맨 앞에 데이터를 추가한다
    {
        if (_count >= _size)
        {
            _size *= 2;
            T[] tempArr = _array;
            _array = new T[_size];
            _array[0] = el;

            for (int i = 0; i < _count; i++)
            {
                _array[i + 1] = tempArr[i];
            }
            Console.WriteLine("PushFront - size * 2배 ->");
        }
        else
        {
            for (int i = _count - 1; i >= 0; i--)
            {
                _array[i + 1] = _array[i];
            }
            _array[0] = el;
        }

        _count++;
        Console.WriteLine($"PushFront / count: {_count}");
    }

    public void PushBack(T el) // 배열의 맨 뒤에 데이터를 추가한다
    {
        if (_count >= _size)
        {
            _size *= 2;
            T[] tempArr = _array;
            _array = new T[_size];

            for (int i = 0; i < _count; i++)
            {
                _array[i] = tempArr[i];
            }
            _array[_count] = el;
            Console.WriteLine("PushBack - size * 2배 ->");
        }
        else
        {
            _array[_count] = el;
        }

        _count++;
        Console.WriteLine($"PushBack / count: {_count}");
    }

    public T PopFront() // 배열의 가장 앞의 데이터를 반환하고, 내부 배열에서 삭제
    {
        T fArr = _array[0];

        for (int i = 0; i < _count - 1; i++)
        {
            _array[i] = _array[i + 1];
        }
        _count--;
        Console.WriteLine($"PopFront {_count} 반환 : {fArr}");
        return fArr;
    }

    public T PopBack() // 배열의 가장 뒤 데이터를 반환하고 삭제
    {
        T lArr = _array[_count - 1];
        _count--;
        Console.WriteLine($"PopBack {_count} 반환 : {lArr}");
        return lArr;
    }

    public void Clear() // 클리어!
    {
        _size = 10;
        _array = new T[_size];
        _count = 0;
        Console.WriteLine("클리어!!!!");
    }
}

 

실제 출력을 위해 요구사항 외에 인덱서도 추가했으며,

_count 범위 밖을 조회하려고 하면 에러를 출력하도록 구성했다.

실제로 잘 작동하는지 돌려보자

 

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

        deque.PushBack(1);
        deque.PushBack(2);
        deque.PushBack(3);
        deque.PushBack(4);
        deque.PushBack(5);
        deque.PushBack(6);
        deque.PushBack(7);
        deque.PushBack(8);
        deque.PushBack(9);
        deque.PushBack(10);
        deque.PushBack(11);
        deque.PushBack(12);
        deque.PushBack(13);
        deque.PushBack(14);

        for (int i = 0; i < deque.Count; i++)
        {
            Console.Write(deque[i] + " ");
        }
        Console.WriteLine();
        Console.WriteLine("현재 count: " + deque.Count);

        Console.WriteLine(deque.PopBack());
        Console.WriteLine(deque.PopBack());
        Console.WriteLine(deque.PopBack());
        Console.WriteLine(deque.PopFront());
        Console.WriteLine(deque.PopFront());
        Console.WriteLine(deque.PopFront());

        for (int i = 0; i < deque.Count; i++)
        {
            Console.Write(deque[i] + " ");
        }

        Console.WriteLine();
        deque.Clear();

        deque.PushFront(1);
        deque.PushFront(2);
        deque.PushFront(3);

        for (int i = 0; i < deque.Count; i++)
        {
            Console.Write(deque[i] + " ");
        }
    }
}

 

 

 

잘 작동한다.

Deque를 실제로 구현해보는 것으로 실제 Queue의 내부 구현 방식을 한번 더 확인해볼 수 있었다.