큐(Queue)

1. 선형큐

뒤에서 삽입, 앞에서 삭제를 하는 구조
삽입된 순서대로 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다: FIFO

• 2개의 인덱스
  • front: 저장된 첫 번째 원소 — 꺼낼 위치를 관리
  • rear: 저장된 마지막 원소 — 저장할 위치를 관리
• 기본 연산
  • enQueue (삽입): 인덱스 사용 시, ① rear 을 1 증가시키고, ② rear 인덱스에 데이터 저장
  • deQueue (삭제): 인덱스 사용 시, ① front을 1 증가시키고, ② front 인덱스 요소 반환
  👉 주요 연산
  • 큐 생성: front와 rear을 -1로 초기화
  • 큐가 공백인지 확인(isEmpty): front == rear 이면 공백
  • 포화상태인지 확인(isFull): N이 배열의 크기일 때, rear == N-1이면 포화 상태
  • 맨 앞 원소를 꺼내지는 않고 확인하는 연산(Qpeek): front+1 인덱스의 원소를 반환
• 선형큐 접근 방법 (빠른 순서)
  1. 배열의 크기를 정하고, front와 rear인덱스로 접근
  2. from collections import deque: append로 enqueue, popleft로 dequeue
  3. append와 pop (append는 시간이 조금 걸리는 편!)
• 선형큐의 문제점💬

"원소를 삽입할 때 rear을 +1 하고, 원소를 삭제할 때 front +1 하면서, 배열의 앞부분에 빈 공간이 있음에도 불구하고 rear == N-1 이 되었을 때 포화상태로 인식할 수 있다."
⇒ 연산이 이루어질 때마다 배열의 앞부분으로 위치를 이동시킬 수 있지만, 시간이 많이 소요되므로 좋은 방법은 아니다.

• ​collections 모듈의 deque
  • popleft(): 첫 번째 데이터를 pop
  • appendleft(x): 데이터를 맨 앞에 삽입 (== list의 insert(0, x))
  • 장점: deque의 popleft()와 appendleft(x) 메서드는 모두 $O(1)$의 시간 복잡도를 가진다.
  • 단점: 무작위 접근(random access)의 시간 복잡도가 $ O(N) $이다. 내부적으로 linked list를 사용하고 있기 때문에, $i$ 번째 데이터에 접근하려면 맨 앞 혹은 뒤부터 $i$ 번의 순회(iteration)를 해야 하기 때문이다.

 

그래서... 원형큐!

 

2. 원형큐

인덱스가 넘치면, 맨 앞으로 인덱스를 돌리는 방법

• 초기 공백 상태: front와 rear을 모두 0으로 초기화
• 배열의 크기를 N으로 둘 때, (rear + 1) % N, 즉 나머지를 삽입 인덱스로 사용한다.
• 삭제 인덱스는 (front + 1) % N으로 사용한다.
• front의 한 칸을 비워두고 사용한다! 공백 상태와 포화 상태를 쉽게 구분하기 위함.
  • (rear + 1) % N == front 이면 포화상태로 판단 (즉, rear의 다음 위치가 현재의 front면 포화상태로 본다.)
  • rear == front 이면 공백상태로 판단

 

3. [참고] 연결큐

너무 크기가 커서 물리적으로 연속된 공간을 할당받기 어려울 때, 데이터를 쪼개서 메모리의 여러 빈 공간에다 찔러 넣기(?)

• 다음 정보의 저장 위치를 알고 있어야 한다.
• 클래스로 구현: 저장하는 부분 & 다음 리스트를 가리키는 부분

 

4. 우선순위 큐

항목들에 우선순위가 주어져 있고, 그 순서대로 나가는 큐

• 활용: 시뮬레이션 시스템, 네트워크 트래픽 제어, OS의 태스크 스케줄링
• 구현
  • 배열을 이용
  • 연결 리스트를 이용
  ⇒ 배열과 트리를 함께 사용 (힙 구조)

 

5. 큐의 활용: 버퍼(Buffer)

데이터를 한 곳에서 다른 곳으로 전송하는 동안 일시적으로 데이터를 보관하는 메모리의 영역

• "임시 저장소"
• 버퍼링: 버퍼를 활용하는 방식, 또는 버퍼를 채우는 동작
• FIFO 방식의 자료구조인 큐를 활용함

 

6. BFS (Breadth First Search, 너비 우선 탐색)

시작점의 인접 정점을 모두 차례로 방문한 후, 방문한 정점을 새로운 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

• FIFO 방식의 자료구조인 큐를 활용함
• 거리순 탐색의 효과가 남
• 한 번에 탐색하는 그룹의 순서는 바뀌지 않음
• 시작점이 여러 개인 경우도 탐색 가능

반복구조의 탐색은 '초기화' 와 '반복 부분'으로 나뉜다.

 

초기화 부분

1) 큐 생성
2) visited 배열 생성 (방문 표시)
3) 시작점 enqueue
4) (시작점의 visited 표시)

 

반복 부분

1) 가장 앞의 요소 pop

2) (visited 표시)

3) 인접해 있고, 방문하지 않은 모든 정점들을 enqueue

4) 큐가 비면, 탐색 종료 (즉, 큐에 요소가 있는 동안 반복)

• visited 표시를 pop과 함께 한다면,
  • 이미 queue에 있는 요소가 중복되어 enqueue 될 수 있다.
  • ⇒ 인접한 정점을 탐색할 때, 해당 정점이 미방문인 경우에만 탐색을 진행하도록 if문을 짠다.
    • 중복이 발생할 수 있으므로, 큐의 크기를 정점의 개수만큼으로 고정하여 사용하는 방식은 사용하기 힘들다.
• visited 표시를 enqueue와 함께 한다면,
  • queue에 있다면 이미 방문표시가 되어 있으므로 중복 enqueue를 방지할 수 있다.
    • if문이 한 단계 줄어든다.
    • 큐의 크기를 확정적으로 사용할 수 있다. (중복을 고려하지 않아도 되므로)
• visited 배열에서 visited[i] = 1 이 아니라, visited[i] = visited[t] + 1 로 사용하면, 출발점으로부터의 거리 정보를 visited에 저장할 수 있게 된다!

 

 

예시 코드

def bfs(s, V):
    q = []  # 1) 큐 생성
    visited = [0] * (V + 1)  # 2) visited 생성
    q.append(s)  # 3) 시작점 인큐
    visited[s] = 1  # 4) 시작점 visited 표시
    while q:  # 큐가 비어있지 않으면 (처리할 정점이 남아 있으면)
        t = q.pop(0)  # 디큐 (꺼내서)해서 t에 저장
        print(t)  # t에 대한 처리
        for i in adjList[t]:  # adjList는 인접 리스트. t에 인접이고 미방문인 모든 i에 대해
            if visited[i] == 0:
                q.append(i)  # enqueue(i)
                visited[i] = visited[t] + 1  # i visited로 표시

※ 인접 행렬과 인접 리스트

둘 다 인접 정점끼리의 관계를 표현해주는 역할을 한다.

• 인접 리스트: 인접한 노드만 점검하므로 탐색 과정을 줄일 수 있다.
• 인접 행렬: 두 정점 사이 간선의 유무를 빠르게 확인할 수 있다.