[C#] 선형자료구조 실습하기 3 - Heap

[확인문제]

 

1. Queue가 무엇인지 알고있나요? 어떤 방식으로 작동하는지 설명할 수 있을까요?

FIFO(First In First Out 선입선출) 방식으로 작동하는 자료구조로 다음과 같은 방식으로 작동한다.

 

Enqueue : Queue의 맨 뒤에 데이터를 삽입

Dequeue : Queue의 맨 앞에 있는 데이터를 제거하고 반환

Peek : Queue의 맨 앞에 있는 데이터를 확인(제거하지 않고 확인만)

IsEmpty : Queue가 비어있는지 확인

 

2. Queue를 직접 구현해본 경험이 있을까요? 없다면 직접 구현해봅시다.

클래스 및 주요 멤버 변수

• data
  • 타입: T[] (제네릭 타입 배열)
  • 역할: 큐의 요소를 저장하는 배열입니다. 큐의 최대 크기는 이 배열의 크기로 제한됩니다. 배열의 초기 크기는 1000으로 설정되어 있습니다.
• head
  • 타입: int
  • 역할: 큐의 첫 번째 요소의 인덱스를 가리킵니다. 큐가 비어있을 때는 0입니다.
  • 초기값: 0
  • 동작:
    • 요소가 제거될 때마다 (Dequeue 연산) head의 값이 1씩 증가합니다.
• tail
  • 타입: int
  • 역할: 큐의 마지막 요소의 인덱스를 가리킵니다. 큐가 비어있을 때는 1입니다.
  • 초기값: 1
  • 동작:
    • 새로운 요소가 추가될 때마다 (Enqueue 연산) tail의 값이 1씩 증가합니다.

함수 명세

1. IsEmpty
   • 기능: 큐가 비어있는지 확인하는 함수입니다.
   • 입력: 없음.
   • 출력: bool 값. 큐가 비어있으면 true, 아니면 false.
   • 동작:
     • head가 tail보다 큰지 또는 같은지 확인합니다.
     • 만약 head가 tail보다 크거나 같으면, 큐가 비어있다고 판단하여 true를 반환합니다.
     • 그렇지 않으면 false를 반환합니다.
2. Enqueue
   • 기능: 큐의 맨 뒤에 새로운 요소를 추가하는 함수입니다.
   • 입력: 추가할 요소 item (제네릭 타입 T).
   • 출력: 없음.
   • 동작:
     • 먼저, 큐가 가득 찼는지 확인합니다. (tail이 data 배열의 길이보다 크거나 같으면 예외를 발생시킵니다)
     • tail 변수를 1 증가시킵니다.
     • data 배열의 tail 위치에 item을 저장합니다.
3. Dequeue
   • 기능: 큐의 맨 앞에 있는 요소를 제거하고 그 값을 반환하는 함수입니다.
   • 입력: 없음.
   • 출력: 제거된 요소 item (제네릭 타입 T).
   • 동작:
     • 먼저, 큐가 비어있는지 확인합니다. (IsEmpty 함수를 호출하여 비어있으면 예외를 발생시킵니다)
     • data 배열의 head 위치에 있는 값을 임시로 저장합니다.
     • head 변수를 1 증가시킵니다.
     • 임시로 저장한 값을 반환합니다.
4. Count
   • 기능: 큐에 있는 요소의 개수를 반환하는 함수입니다.
   • 입력: 없음.
   • 출력: 큐에 있는 요소의 개수 (int 값).
   • 동작:
     • tail의 값에서 head의 값을 뺀 후 1을 더한 값을 반환합니다.
     • 요소 개수는 (tail - head + 1)입니다. </aside>

public class My_Queue<T>
{
    private T[] data = new T[1000];
    private int head;
    private int tail;

    public bool IsEmpty()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }

    public void Enqueue(T item)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public T Dequeue()
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******

        // ***********************
    }
}

// 구현 확인을 위한 코드입니다.
class Program
{
    static void Main(string[] args)
    {
        Queue<int> q = new Queue<int>();
        My_Queue<int> q_new = new My_Queue<int>();

        for (int i = 0; i < 10; ++i)
        {
            q.Enqueue(i);
            q_new.Enqueue(i);
        }

        while (q.Count > 0)
        {
            Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
            Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count}");
            Console.WriteLine("------------------------------------------------------");
        }
    }
}

 public bool IsEmpty()
    {
        return head == tail;
    }

    public void Enqueue(T item)
    {
        if (tail == data.Length)
        {
            throw new Exception("Queue is full.");
        }

        data[tail] = item;
        tail++;
    }

    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new Exception("Queue is empty.");
        }

        T item = data[head];
        head++;
        return item;
    }

    public int Count()
    {
        return tail - head;
    }

 

 

[설명문제]

 

1. Queue의 특성을 설명해주세요.

FIFO 방식으로 먼저 들어온 요소가 먼저 나가는 자료구조로, Enqueue는 요소를 큐의 끝에 추가, Dequeue는 요소를 큐의 앞에서 제거한다.

 

2. Queue는 언제 사용하면 좋은 자료구조인가요? 반대로 언제 사용하기 불리할까요?

Queue는 순차적으로 처리해야 하는 작업에서 좋다.

1. 데이저 처리 순서가 중요하고, 먼저 들어온 데이터가 가장 먼저 처리되어야 하는 프린트 대기열, 네트워크 패킷 라우팅, BFS탐색 등에서 효과적이다.

2. 비동기 작업 처리 : 비동기 작업을 순서대로 처리하고 콜백함수를 관리하는 데 Queue를 활용할 수 있다.

3. 메시지 큐 : 분산 시스템에서 메시지들을 전달하고 처리하는 메시지 큐 시스템을 구현할 때 Queue를 사용한다.

 

반면,

1. 데이터의 순서가 중요하지 않고, 특정 데이터에 빠르게 접근해야 하는 경우에는 해시테이블과 트리와 같은 자료구조를 사용하는 것이 더 효율적이다.

2. Queue는 데이터 삽입/삭제 시 O(n)의 시간 복잡도를 가지고 있어 자주 삽입 및 삭제가 발생하는 경우에는 비효율적이다.

 

3. Queue를 본인의 프로젝트에 적용해본 경험을 말해주세요.

 예시

• 비동기 작업 처리: 웹 애플리케이션에서 여러 비동기 작업을 처리할 때, Queue를 사용하여 작업들을 순서대로 처리하고 콜백 함수를 관리했습니다. 예를 들어, 사용자가 버튼을 클릭하면 데이터를 로드하고 그 결과를 바탕으로 화면을 업데이트하는 작업을 비동기적으로 수행하는 데 Queue를 사용했습니다.
• 메시지 큐: 분산 시스템에서 메시지들을 전달하고 처리하는 메시지 큐 시스템을 구현할 때 Queue를 사용했습니다. 각 서비스는 메시지를 Queue에 전달하고, 워커 프로세스는 Queue에서 메시지를 가져와 처리하는 방식으로 구현했습니다.
• 프린트 대기열 관리: 프린터 시스템에서 여러 사용자의 프린트 요청을 순서대로 처리하고 프린터 오류 상황을 관리하는 프린트 대기열 기능을 구현할 때 Queue를 사용했습니다. 사용자가 프린트 요청을 하면 Queue에 요청 정보를 저장하고, 프린터가 준비되면 Queue에서 요청 정보를 하나씩 가져와 프린팅 작업을 수행했습니다.

 

 

[실습문제]

 

💡 [Stack으로 Queue 만들기]

Stack 두 개를 이용하여 Queue를 만들어봅시다.

Stack의 특성만을 이용하여 선입선출(FIFO; First-In First-Out)의 특성을 만족하는 Queue를 만들어야 합니다.

public class Queue_new<T>
{
    Stack<T> stack1 = new Stack<T>();
    Stack<T> stack2 = new Stack<T>();

    public bool IsEmpty()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }

    public void Enqueue(T item)
    {
        // ****** CODE HERE ******

        // ***********************
    }

    public T Dequeue()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }

    public int Count()
    {
        // ****** CODE HERE ******
        
        // ***********************
    }
}

// 구현 확인을 위한 코드입니다.
class Program
{
    static void Main(string[] args)
    {
        Queue<int> q = new Queue<int>();
        Queue_new<int> q_new = new Queue_new<int>();

        for (int i = 0; i < 10; ++i)
        {
            q.Enqueue(i);
            q_new.Enqueue(i);
        }

        while (q.Count > 0)
        {
            Console.WriteLine($"q => {q.Dequeue()} | q_new => {q_new.Dequeue()}");
            Console.WriteLine($"size of q : {q.Count} | size of q_new : {q_new.Count}");
            Console.WriteLine("------------------------------------------------------");
        }
    }
}

 public bool IsEmpty()
    {
        return stack1.Count == 0 && stack2.Count == 0;
    }

    public void Enqueue(T item)
    {
        stack1.Push(item);
    }

    public T Dequeue()
    {
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        if (stack2.Count == 0)
        {
            while (stack1.Count > 0)
            {
                stack2.Push(stack1.Pop());
            }
        }
        return stack2.Pop();
    }

    public int Count()
    {
        return stack1.Count + stack2.Count;
    }

 

Queue_new 클래스는 원소를 저장하는 stack1과 원소를 반대 순서로 재정렬하는 stack2를 사용한다. Enqueue 메서드는 stack1에 원소를 추가하고, Dequeue 메서드는 stack2에서 원소를 제거한다. stack2가 비어있으면 stack1에서 원소를 모두 꺼내 stack2로 옮겨서 큐의 특성을 유지한다.