<aside> 💡

[BFS vs DFS]

• BFS (Breadth-First Search, 너비 우선 탐색)
  • 루트(시작점)에서 가까운 노드(레벨 순서)부터 탐색
  • 즉, 한 "층"의 모든 노드를 방문한 뒤 다음 층으로 넘어감
  • 큐(Queue) 자료구조 사용
• DFS (Depth-First Search, 깊이 우선 탐색)
  • 루트에서 한 경로를 끝까지 따라간 뒤, 더 이상 못 가면 되돌아와서 다른 경로 탐색
  • 즉, “깊게” 들어갔다가 다시 올라옴 (백트래킹)
  • 스택(Stack) 또는 재귀(Recursion) 사용

https://seanperfecto.github.io/BFS-DFS-Pathfinder/

</aside>

큐 (Queue)

: 먼저 들어온 데이터가 먼저 나가는 선형 자료구조(자료 간의 관계가 1:1의 관계를 가짐.)

• 스택과 마찬가질 삽입과 삭제의 위치가 제한적인 자료구조로 큐의 뒤에서 삽입만 하고, 앞에서는 삭제만 이루어지는 구조

• 선입선출 (FIFO, First In First Out)

  • 가장 먼저 넣은 자료가 가장 먼저 나오는 것

• 큐의 구조

  

  1. front
     • 데이터가 나가는 **'창구'**의 위치를 가리킴
     • 큐의 맨 앞 위치를 가리키는 인덱스
     • 삭제(dequeue) 연산이 일어나는 위치
     • dequeue가 일어나면 front는 다음 데이터로 이동
  2. rear
     • 줄의 가장 뒤에 있는 **'마지막 대기자'**의 위치를 가리킴
     • 큐의 맨 뒤 위치를 가리키는 인덱스
     • 삽입(enqueue) 연산이 일어나는 위치
     • enqueue가 일어나면 rear는 그 데이터를 가리키도록 이동

• 큐의 기본 연산

  • 삽입 : enqueue
  • 삭제 : dequeue

  

• 큐의 연산 과정

  

  ⇒ front = rear = -1 (같으면) 비었다는 것임

  하나 넣으면 rear는 +1 이 됨

  

  ⇒ 하나 빼면 front는 +1 이 됨

  

  

  ⇒ rear와 front가 같아짐.

  1. 공백 Queue 생성

     • 고정 배열에서 Queue의 사이즈를 지정
     • front와 rear의 값을 -1로 초기화
       • 이때 파이썬에서 음수 인덱스 유의

  2. 원소 A 삽입

     삽입 과정은 rear의 증가

     • front → -1
     • rear → 0 (+1)

  3. 원소 B 삽입

     삽입 과정은 rear의 증가

     • front → -1
     • rear → 1 (+1)

  4. 원소 반환/삭제

     삭제 과정은 front의 증가

     • front → 0 (+1)
       • 이때 해당 자리에 있었던 원소 반환
     • rear → 1

  5. 원소 C 삽입

     • front → 0
     • rear → 2 (+1)

  6. 원소 반환/삭제

     • front → 1 (+1)
     • rear → 2

  7. 원소 반환/삭제

     • front → 2 (+1)
     • rear → 2
     • front와 rear가 같아진다? → 공백 상태

1. 선형 큐

: 데이터를 일렬로 저장하며, 앞에서 꺼내고 뒤에 넣는 기본 큐 구조

• 구현 → .append() , .pop() , front , rear

  • 배열이나 연결형 리스트로 구현할 수 있음
  • 큐의 크기는 배열의 크기와 같음
  • front : 가장 최근에 삭제된 원소의 인덱스임
  • rear : 마지막으로 저장된 원소의 인덱스임

• 상태 표현

  • 초기 상태: front = rear = -1
  • 공백 상태: front == rear
  • 포화 상태: rear == n-1 (n: 배열의 크기, n-1: 배열의 마지막 인덱스)

• 구현 프로세스

  ① 초기 공백 큐 생성 : create_queue()

  • 크기 n인 1차원 배열 생성
  • front와 rear를 -1로 초기화

  # create_queue()에 해당
  q = [0] * n
  front = -1
  rear = -1
  

  ② 삽입 : enqueue(item)

  ---

  ③ 삭제 : dequeue()

  ---

  ④ 공백상태 및 포화상태 검사 : is_empty(), is_full()

  ---

  ⑤ 검색 : qpeek()

선형큐 구현

• append, pop 없는 버전으로 구현해봄

2. 원형 큐

<aside> 💡

</aside>

• 원형 큐란?
• 원형 큐의 구조