[TIL 24.07.12] 10.선형 자료구조 - Queue

.

 

목   차

 

확인 문제

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

큐(Queue)는 데이터 구조 중 하나로, 먼저 들어온 데이터가 먼저 나가는 FIFO(First In, First Out) 방식으로 작동한다. 즉, 먼저 추가된 요소가 먼저 제거된다.

 

• Enqueue: 큐의 끝부분에 새로운 요소를 추가.
• Dequeue: 큐의 앞부분에서 요소를 제거 및 반환
• Peek: 큐의 앞부분에 있는 요소를 제거하지 않고 반환.
• IsEmpty: 큐가 비어있는지 확인.
• Count: 큐에 있는 요소의 개수를 반환.

 

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

.

---

 

설명 문제

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

1. FIFO 구조.
2. 동적 크기 관리.

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

1. 작업 스케줄링
2. 데이터 스트리밍
3. 프린터 작업 관리
4. 너비 우선 탐색(BFS)

 

1. 랜덤 액세스가 필요한 경우.
2. Stack처럼 후입선출이 필요한 경우.
3. 복잡한 우선순위 관리가 필요한 경우 (우선순위 큐 or Heap)
4. 대용량의 데이터를 다루는 경우.
5. 양방향 접근이 필요한 경우.

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

Object Pool을 활용하여 객체의 생성과 소멸 과정을 최소화해야 하는 상황이 있었다. 필드에 존재하는 객체의 수가 풀에 보유한 객체의 수와 동일한 경우, 추가적인 객체가 필요할 때 가장 먼저 활성화된 객체를 다른 용도로 옮기는 방식이 필요했다. 이를 구현하기 위해 큐(Queue)를 사용했다.

---

 

실습 문제

namespace _10.선형자료구조_queue_실습
{
    public class Queue_new<T>
    {
        Stack<T> stack1 = new Stack<T>();
        Stack<T> stack2 = new Stack<T>();

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

        public void Enqueue(T item)
        {
            // ****** CODE HERE ******
            stack1.Push(item);
        }

        public T Dequeue()
        {
            // ****** CODE HERE ******
            if (stack2.Count == 0)
            {
                while (stack1.Count > 0)
                {
                    stack2.Push(stack1.Pop());
                }
            }

            return stack2.Pop();
        }
        public int Count()
        {
            // ****** CODE HERE ******
            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);
            }

            foreach (int i in q)
            {
                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("------------------------------------------------------");
            }
        }
    }
}

.