자료구조 - 큐(Queue)

 

 

큐(Queue) 이란?

 

 

큐(Queue)는 데이터를 선형 구조로 저장하는 자료구조로, FIFO(First-In-First-Out, 선입선출) 원칙을 따릅니다. 이는 처음 추가된 데이터가 처음으로 제거되는 구조를 의미합니다. 즉, 가장 먼저 저장된 요소가 가장 먼저 나오는 특징을 가지고 있습니다. 새로운 데이터는 큐의 뒷부분에 추가되고, 데이터는 큐의 앞부분에서 제거됩니다. 이로써 데이터는 일렬로 정렬되어 관리됩니다. 주로 데이터 처리 과정에서 선입선출의 원칙이 필요한 경우에 큐가 활용됩니다.

 

큐 코드 예시 (C#)

아래 코드는 C#에서 queue 활용의 예시입니다.

using System;
using System.Collections.Generic;

public class QueueExample
{
    public static void Main(string[] args)
    {
        Queue<int> queue = new Queue<int>();

        // Queue에 데이터 추가
        queue.Enqueue(1);
        PrintQueue(queue);
        queue.Enqueue(2);
        PrintQueue(queue);
        queue.Enqueue(3);
        PrintQueue(queue);

        // Queue에서 데이터 제거
        int dequeuedElement = queue.Dequeue();
        Console.WriteLine("Dequeued element: " + dequeuedElement);

        // Queue의 첫 번째 요소 확인
        int firstElement = queue.Peek();
        Console.WriteLine("First element: " + firstElement);
    }

    public static void PrintQueue(Queue<int> queue)
    {
        // Queue의 모든 요소 출력
        Console.Write("Queue elements: ");
        foreach (int item in queue)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

 

위 코드를 실행한 결과는 다음과 같습니다.

 

Queue elements: 1 
Queue elements: 1 2 
Queue elements: 1 2 3 
Dequeued element: 1
First element: 2

 

 

큐 활용 알고리즘 문제 (C#)

큐를 활용한 알고리즘 문제로는 요세푸스 문제(Josephus Problem)가 있습니다. 문제는 다음과 같습니다. N명의 사람이 원형으로 모여있고, K번째 사람이 제거되는 과정을 반복합니다. 마지막에 남는 사람을 찾는 문제입니다.

 

요구사항

• N명의 사람이 원형으로 모여있고, 1부터 N까지 번호가 매겨져 있습니다.
• 매번 K번째 사람을 제거합니다.
• 마지막에 남는 사람의 번호를 반환합니다.
  
  

using System;
using System.Collections.Generic;

public class Solution
{
    public static void Main(string[] args)
    {
        int N = 7; // 총 사람 수
        int K = 3; // 제거될 순서

        int lastSurvivor = GetLastSurvivor(N, K);
        Console.WriteLine($"Last survivor: {lastSurvivor}");
    }

    public static int GetLastSurvivor(int N, int K)
    {
        Queue<int> queue = new Queue<int>();

        // 사람들을 큐에 추가
        for (int i = 1; i <= N; i++)
        {
            queue.Enqueue(i);
        }

        while (queue.Count > 1)
        {
            // K-1번째까지의 사람을 큐의 뒤로 이동
            for (int i = 0; i < K - 1; i++)
            {
                int person = queue.Dequeue();
                queue.Enqueue(person);
            }

            // K번째 사람을 제거
            int removedPerson = queue.Dequeue();
            Console.WriteLine($"Removed person: {removedPerson}");
        }

        // 마지막에 남은 사람 반환
        return queue.Dequeue();
    }
}

 

 

출력결과 입니다.

 

Removed person: 3
Removed person: 6
Removed person: 2
Removed person: 7
Removed person: 5
Removed person: 1
Last survivor: 4

 

 

 

큐의 장단점

 

- 장점

• FIFO(선입선출) 구조를 따르기 때문에 데이터의 순서가 중요한 작업에 유용합니다.
• 데이터를 추가하거나 제거하는 동작이 매우 빠릅니다.

- 단점

• 크기가 고정되어 있거나 제한된 큐에서는 데이터를 추가할 수 없습니다.
• 큐의 요소를 탐색하거나 업데이트하는 데는 추가적인 비용이 발생할 수 있습니다.

 

큐 사용 사례

 

• 프로세스 스케줄링: 운영 체제에서 프로세스를 관리할 때 다음에 실행될 프로세스를 결정하기 위해 큐를 사용합니다.
• 네트워크 통신: 네트워크 패킷을 처리할 때 큐를 사용하여 패킷을 순서대로 처리합니다.
• 멀티스레드 환경에서의 작업 관리: 여러 작업을 처리할 때 큐를 사용하여 작업을 조정하고 실행합니다.

 

큐는 다양한 상황에서 유용하게 사용되며, 데이터를 순차적으로 처리해야 하는 많은 경우에 필수적인 자료구조입니다.