Queue

• 큐(Queue)는 데이터를 선입선출(FIFO, First-In First-Out) 방식으로 저장하는 자료구조다.

• 데이터는 들어간 순서대로 저장되며, 먼저 들어간 데이터가 먼저 제거된다.
  ex) 줄 서기 방식

• 헤드(Head)와 테일(Tail)로 값들의 시작과 끝을 알 수 있다.

---

문법

Queue<T> queue = new Queue<T>(); // T에 타입

---

특징

• 데이터의 삽입 및 삭제가 빠르다. 삽입, 삭제 O(1)

• 연속적인 인덱스가 없으며,
  특정 값을 찾기 위해서는 전체를 탐색해야 한다. 접근, 검색 O(n)

• 배열과 다르게 크기를 미리 할당할 필요가 없으며,
  리스트처럼 자동으로 크기가 할당된다.

• 헤드(Head)는 첫 번째 값이 위치한 곳을 뜻한다.

• 테일(Tail)은 마지막 값이 위치한 곳을 뜻한다.

---

순서 (원형 큐 방식)

• 크기가 8인 큐배열에 1, 2, 3, 4, 5, 6 값이 들어있다고 해보자

• 헤드는 처음 값인 1의 위치인 0을 가르킨다.

• 테일은 다음에 들어올 값의 위치인 6을 가르킨다.

---

• 처음 값을 제거하면 헤드의 위치도 그 다음값이였던 2를 가르킨다.

---

• 값 추가

---

• 큐(Queue)는 순서대로 쭉 늘어나지 않고, 배열의 빈공간을 최대한 활용(원형 큐)한다.

• 즉 현재 배열은 n 2 3 4 5 6 7 8 상태라 테일은 다음 값이 들어올 n의 위치인 0을 가르킨다.

---

• 9 2 3 4 5 6 7 8 상태가 되어 헤드와 테일이 같은 곳을 가르킨다.
  이 때 값을 추가하면 어떻게 될까?

---

• 배열이 가득찬 상태라 기존 8의 크기를 2배 늘려 16의 크기를 가진 배열을 새로 생성한다.

• 그 후 헤드부터 테일까지 순서대로 새 배열에 할당한다.
  9 2 3 4 5 6 7 8 ▶ 2 3 4 5 6 7 8 9 10 n n n n n n n n은 빈공간

---

예시

• 타입은 임시로 int로 설정

데이터 추가 (Enqueue)

Queue<int> queue = new Queue<int>();

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

foreach (int i in queue)
{
    Console.WriteLine(i);
}
// 1 2 3 4 5 순으로 출력

---

데이터 삭제 (Dequeue, TryDequeue)

// 1, 2, 3, 4, 5 가 있는 상태
queue.Dequeue(); // 1 삭제

// 데이터가 있으면 제거
bool isDequeue = queue.TryDequeue(out int result); // 2 삭제

---

마지막 데이터 확인 (Peek, TryPeek)

int topValue = queue.Peek();
Console.WriteLine(topValue); // 3 출력

bool hasValue = queue.TryPeek(out int result2);
if (hasValue)
    Console.WriteLine(result2); // 3 출력

---

BFS (너비 우선 탐색)

• BFS(Breadth First Search, 너비 우선 탐색)은 그래프 탐색 알고리즘 중 하나로,
  큐(Queue)를 활용하여 탐색을 진행한다.

• 선입선출(FIFO) 방식으로 먼저 방문한 노드의 인접 노드를 차례대로 탐색하며,
  최단 경로 탐색에 유리한 알고리즘이다.

예시

Queue<int> queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);

while (queue.Count > 0)
{
    int current = queue.Dequeue();
    Console.WriteLine(current); // 1 > 2 > 3 순으로 출력
}

---

딱히 비유할만한게 떠오르진 않는다.

그냥 먼저 들어온 값이 먼저 나간다.