Queue

큐의 특성

• 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조

  • 큐의 뒤에서만 삽입하고, 큐의 앞에서는 삭제만 이루어지는 구조

• 선입선출 구조

  • 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소는 가장 먼저 삭제된다.
    • 머리(저장된 원소 중 첫 번째 원소) : Front
    • 꼬리(저장된 원소 중 마지막 원소) : Rear == (마지막으로 저장된 원소)

• 큐의 기본 연산

  • 삽입 :enQueue
  • 삭제 : deQueue

큐의 구현

• 큐의 사용을 위해 필요한 주요 연산

  • enQueue : 큐의 뒤쪽에 원소를 삽입하는 연산
  • deQueue : 큐의 앞쪽에 원소를 삭제하고 반환하는 연산
  • createQueue : 공백 상태의 큐를 생성하는 연산
  • isEmpty : 큐가 공백상태인지 확인하는 연산
  • isFull : 큐가 포화상태인지를 확인하는 연산
  • Qpeek : 큐의 앞쪽에서 원소를 삭제없이 반환하는 연산

• 큐의 연산 과정

  1. 공백 큐 생성 : createQueue()
  2. 원소 A 삽입 : enQueue(A)
  3. 원소 B 삽입 : enQueue(B)
  4. 원소 반환/삭제 : deQueue()
  5. 원소 C 삽입 : enQueue(C)
  6. 원소 반환/삭제 : deQueue()
  7. 원소 반환/삭제 : deQueue()

선형 큐

• 1차원 배열을 이용한 큐

  • 큐의 크기 = 배열의 크기
  • front : 저장된 첫 번째 원소의 인덱스 (꺼내진 위치)
  • rear : 저장된 마지막 원소의 인덱스

• 상태 표현

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

• 초기 공백 큐 생성

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

• 삽입 : enqueue(item)

  • 마지막 원소 뒤에 새로운 원소를 삽입하기 위해
    • rear 값을하나 증가시켜 새로운 원소를 삽입할 자리를 마련
    • 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장

• 삭제 : deQueue

  • 가장 앞에 있는 원소를 삭제하기 위해
    • front 값을 하나 증가시켜 큐에 남아있게 될 첫 번째 원소 이동
    • 새로운 첫 번째 원소를 리턴함으로써 삭제와 동일한 기능함

• 공백상태 및 포화상태 검사 : isEmpty(), isFull()

  • 공백상태 : front == rear
  • 포화상태 : rear == n-1

• 검색 Qpeek()

  • 가장 앞에 있는 원소를 검색하여 반환하는 연산
  • 현재 front의 한자리 뒤 (front+1)에 있는 원소, 즉 큐의 첫 번째에 있는 원소 반환

선형 큐 이용시의 문제점

• 잘못된 포화상태 인식
  • 선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear=n-1 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 ㅇ낳게 됨
• 해결방법 1
  • 매 연산이 이루어질 때마다 저장된 원소들을 배열의 앞부분으로 모두 이동시킴
  • 원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어짐
• 해결방법 2
  • 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용
  • 원형 큐의 논리적 구조

원형 큐의 구조

• 초기 공백상태
  • front=rear=0
• index의 순환
  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1를 가리킨 후 , 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
  • 이를 위해 나머지 연산자 mod를 사용함
• front 변수
  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
• 삽입 위치 및 삭제 위치
  • 선형큐
    • 삽입 위치 rear = rear+1
    • 삭제 위치 front= front + 1
• 원형 큐의 구현
  • front=rear=0으로 초기화
• 공백 상태 및 포화상태 검사 : isEmpty(), isFull()
  • 공백상태 : front=rear
  • 포화상태 : 삽입할 rear의 다음 위치 == 현재 front
    • (rear +1)mod n == front
• 삭제 : deQueue()

BFS

# 인풋받기
input_str = "1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7"
lst = list(map(int,input_str.split(", ")))

# 그래프 만들기
from collections import defaultdict
graph = defaultdict(list)

for i in range(0, len(lst), 2):
    a = lst[i]
    b = lst[i+1]    
    graph[a].append(b)
    graph[b].append(a)


# 큐 생성
queue = []
visited = []

queue.append(1)
visited.append(1)

# BFS
while queue:
    # deQueue
    tmp = queue.pop(0)

    for node in graph[tmp]:
        if node not in visited:
            queue.append(node)
            visited.append(node)
    print(queue)



# BFS, visited가 tmp 아래 있으면 비효율 발생

queue = []
visited = []

queue.append(1)

# BFS
while queue:
    # deQueue
    tmp = queue.pop(0)
    visited.append(tmp)

    for node in graph[tmp]:
        if node not in visited:
            queue.append(node)
    print(queue)