C# 프로그래밍 기초 실습 전자책

C# / .NET 알고리즘과 퀴즈
본 알고리즘 퀴즈 문제는 C#/.NET 개발자를 위한 알고리즘 인터뷰 혹은 C# 프로그래밍을 통한
문제 해결 알고리즘을 연구해 보는데 도움이 되고자 작성되었습니다.


퀴즈 질문


예상답변/설명

Queue의 기본 메서드로 Enqueue와 Dequeue를 구현하게 되고, 입력데이타에 따라 Generic 타입 T를 받아들여 핸들링하게 된다. 아래 예제는 간단한게 데이타가 int라고 가정하였는데, 이는 쉽게 Generics로 변경할 수 있다. Enqueue()에서는 큐가 FULL로 차있는지는 체크하고, Dequeue()에서는 큐가 비어있는지 체크해야 한다. 특히 순환구조이므로 모듈라 % 연산자를 사용하여 다음 포인터가 순환 구조를 갖도록 작성해야 한다. Full인지를 체크하기 위해 rear 포인터(인덱스) + 1이 front와 같은지 검사하고, Empty Queue는 Dequeue시 front와 rear가 같은 경우 마지막 요소를 리턴하면서 front와 rear값을 초기화 즉 -1로 지정해 준다.

class CircularQueue
{
    const int DEFAULT_SIZE = 16;
    int[] Q = new int[DEFAULT_SIZE]; 
    int front = -1;
    int rear = -1;

    public void Enqueue(int val)
    {
        // Is full?
        if (rear + 1 % Q.Length == front) 
        {
            // 대안으로 큐의 크기를 2배로 늘려 복사하는 방법 사용가.
            throw new ApplicationException("Queue is full");                
        }

        if (front == -1) // Is empty?
        {
            front = rear = 0;
        }
        else // otherwise
        {
            rear = rear + 1 % Q.Length;
        }

        Q[rear] = val;
    }

    public int Dequeue()
    {
        // Is empty?
        if (front == -1)
        {
            throw new ApplicationException("Queue is empty");                
        }

        int val = Q[front];

        if (front == rear) // Is last?
        {                
            front = rear = -1;
        }
        else // otherwise
        {
            front = front + 1 % Q.Length;
        }

        return val;
    }
}