큐 (Queue)의 개념 및 구현

큐(Queue)는 FIFO(First In, First Out) 방식으로 동작하는 대표적인 자료구조입니다.
먼저 들어온 데이터가 먼저 처리되며, 일상생활의 줄 서기와 비슷한 개념입니다.
이번 포스팅에서는 큐의 기본 개념과 특징, 주요 연산, 그리고 C#을 활용한 구현 방법을 자세히 살펴보겠습니다.

---

1. 큐 (Queue)란?

큐는 데이터를 저장하고 관리하는 선형 자료구조로, 가장 먼저 추가된 데이터가 가장 먼저 삭제됩니다.
데이터를 넣는 쪽은 후단(Rear) 또는 enqueue라고 하고, 데이터를 꺼내는 쪽은 전단(Front) 또는 dequeue라고 합니다.

큐의 구조

• Enqueue: 큐의 끝에 데이터를 추가하는 연산
• Dequeue: 큐의 앞에서 데이터를 제거하는 연산
• Peek: 현재 큐의 첫 번째 요소를 반환하되, 제거하지 않는 연산

큐는 FIFO 방식이기 때문에 먼저 들어온 데이터부터 차례로 처리되며, 배치나 요청 관리에서 자주 사용됩니다.

---

2. 큐의 주요 연산

큐에서 제공되는 주요 연산은 다음과 같습니다.

• Enqueue: 큐의 끝에 새 요소를 추가합니다.
• Dequeue: 큐의 앞에서 요소를 제거합니다. 큐가 비어있으면 제거할 수 없습니다.
• Peek: 큐의 앞에 있는 요소를 반환하지만 큐에서 제거하지 않습니다.
• IsEmpty: 큐가 비어 있는지 확인합니다.
• IsFull (고정 크기 큐의 경우): 큐가 가득 찼는지 확인합니다.

---

3. 큐의 활용 사례

큐는 데이터가 들어온 순서대로 처리되어야 하는 상황에서 유용합니다.

1. 프로세스 관리: 운영체제에서 프로세스를 일정 순서에 따라 실행하는 데 사용됩니다.
2. 프린터 대기열: 문서가 요청된 순서대로 출력됩니다.
3. 네트워크 패킷 처리: 패킷이 수신된 순서대로 처리됩니다.

---

4. 큐의 구현 - C# 코드 예제

큐를 C#에서 직접 구현할 수 있으며, List나 Queue<T> 클래스도 큐로 활용 가능합니다.
여기에서는 배열을 이용하여 기본 큐를 구현해보겠습니다.

4.1 큐 클래스 구현

배열 기반 큐에서는 front와 rear를 이용해 데이터의 출입을 관리합니다.

public class Queue
{
    private int[] elements;
    private int front;
    private int rear;
    private int maxSize;
    private int count;

    // 큐 생성자
    public Queue(int size)
    {
        maxSize = size;
        elements = new int[maxSize];
        front = 0;
        rear = -1;
        count = 0;
    }

    // Enqueue - 큐에 요소 추가
    public void Enqueue(int data)
    {
        if (IsFull())
        {
            Console.WriteLine("Queue is full.");
            return;
        }
        rear = (rear + 1) % maxSize;
        elements[rear] = data;
        count++;
    }

    // Dequeue - 큐에서 요소 제거
    public int Dequeue()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty.");
            throw new InvalidOperationException("Queue is empty.");
        }
        int data = elements[front];
        front = (front + 1) % maxSize;
        count--;
        return data;
    }

    // Peek - 큐의 앞쪽 요소 반환 (제거하지 않음)
    public int Peek()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Queue is empty.");
            throw new InvalidOperationException("Queue is empty.");
        }
        return elements[front];
    }

    // 큐가 비었는지 확인
    public bool IsEmpty()
    {
        return count == 0;
    }

    // 큐가 가득 찼는지 확인
    public bool IsFull()
    {
        return count == maxSize;
    }
}

4.2 큐의 사용 예시

위에서 구현한 큐 클래스를 사용하여 데이터를 추가하고 제거하는 예제입니다.

public class Program
{
    public static void Main()
    {
        Queue queue = new Queue(5);

        queue.Enqueue(1);
        queue.Enqueue(2);
        queue.Enqueue(3);

        Console.WriteLine("Peek: " + queue.Peek()); // 1 출력

        Console.WriteLine("Dequeue: " + queue.Dequeue()); // 1 제거
        Console.WriteLine("Dequeue: " + queue.Dequeue()); // 2 제거

        queue.Enqueue(4);
        queue.Enqueue(5);

        while (!queue.IsEmpty())
        {
            Console.WriteLine("Dequeue: " + queue.Dequeue());
        }
    }
}

코드 설명

• Enqueue: 큐의 끝에 요소를 추가합니다. rear가 순환형으로 이동하도록 설정해 배열을 재활용할 수 있습니다.
• Dequeue: 큐의 앞에서 요소를 제거합니다. front가 다음 위치로 이동하도록 설정합니다.
• Peek: 현재 front가 가리키는 요소를 반환하지만 제거하지 않습니다.
• IsEmpty, IsFull: 현재 큐 상태를 확인합니다.

---

5. 큐의 장점과 단점

장점

• 간단한 데이터 관리: FIFO 방식으로 데이터의 순서가 명확하게 유지됩니다.
• 효율적인 삽입/삭제: 데이터의 끝에서 삽입, 시작에서 삭제하는 구조로 효율적입니다.

단점

• 고정 크기 큐의 제한: 배열 기반 큐는 배열의 크기를 미리 지정해야 하므로 유연성이 떨어질 수 있습니다.
• 원형 큐(Circular Queue) 필요: 배열을 재사용하려면 원형 큐 개념이 필요합니다.

---

큐는 데이터가 입력된 순서대로 처리해야 하는 경우 유용한 자료구조입니다.
운영체제의 프로세스 스케줄링, 네트워크 패킷 관리 등 실생활에서 빈번히 사용되는 큐의 개념과 기본적인 구현을 알아보았습니다.