[자료구조] Queue

 

[Unity/C#] 큐 (Queue)

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

• 데이터를 저장하고 관리하는 자료구조 중 하나로, 요소 추가와 삭제의 위치가 양 끝으로 나누어져 있다.

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

• 선입선출 (FIFO, First In First Out)
  • 먼저 저장된 데이터가 먼저 나간다.
• 연산 속도
  • 큐는 양 쪽 끝에서만 삽입/삭제가 일어나기 때문에 Enqueue, Dequeue, Peek등을 사용할 때, 연산 속도가 빠르다 [ O(1) ]
• 제한된 접근
  • 큐는 전단에 있는 데이터만 확인이 가능하고 중간에 있는 데이터에는 직접 접근할 수 없다.
    • 하지만 큐를 어떻게 어떻게 만드냐에 따라 다르다.
      • ex) List, Arr

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

• 저장된 순서대로 데이터를 처리해야될 때, 유용하게 사용할 수 있다.
  • BFS
  • 오브젝트 풀
  • 프로세스 스케줄링
  • 우선순위 큐
• 첫 번째 데이터 이외의 데이터를 접근해야할 때는 사용하기 힘든 자료구조이다.

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

• 오브젝트 풀을 구현할 때, 를 사용하여 비활성화된 풀 오브젝트들을 저장하고 관리했다.
• 오브젝트가 활성화될 때는 Dequeue 연산으로 큐에서 오브젝트를 가져와 활성화했다.
• 오브젝트가 비활성화될 때는 Enqueue 연산으로 큐에 다시 반환하여 재 사용할 수 있도록 했다.
• 큐를 사용하여 오브젝트의 활성화 및 비활성화에 따른 메모리 할당 및 해제 비용을 줄였다.

---

배열로 만든 큐.cs

using System;

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

    public bool IsEmpty()
    {
        // 큐가 비어있는지 확인하는 함수
        return head >= tail;
    }

    public void Enqueue(T item)
    {
        // 큐가 가득 찼는지 확인
        if (tail >= data.Length)
        {
            throw new InvalidOperationException("Queue is full");
        }
        
        // 새로운 요소를 큐의 맨 뒤에 추가
        data[tail] = item;
        tail++;
    }

    public T Dequeue()
    {
        // 큐가 비어있는지 확인
        if (IsEmpty())
        {
            throw new InvalidOperationException("Queue is empty");
        }
        
        // 큐의 맨 앞에 있는 요소를 제거하고 반환
        T item = data[head];
        head++;
        return item;
    }

    public int Count()
    {
        // 큐에 있는 요소의 개수를 반환
        return tail - head;
    }
}

// 구현 확인을 위한 코드입니다.
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);
        }

        for (int i = 0; i < 10; ++i)
        {
            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("------------------------------------------------------");
        }
    }
}

 

스택으로 만든 큐.cs

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

    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;
    }
}

// 구현 확인을 위한 코드입니다.
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);
        }

        for (int i = 0; i < 10; ++i)
        {
            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("------------------------------------------------------");
        }
    }
}