[자료구조] 큐(queue)

선형 큐

FIFO(First in First Out)

먼저 들어가는 데이터가 먼저 나오는 입구 출구가 따로 있는 원통 형태

맨 뒤 삽입 + 맨 앞 접근 및 삭제 기능이 필요하다.

따라서 더블리 링크드 리스트를 이용해 O(1)으로 처리하는 것이 빠르다.

파이썬의 deque는 더블리 링크드로 구현되어 있다.

from collections import deque

queue = deque()

# 큐의 맨 끝에 데이터 삽입
queue.append("A")
queue.append("B")

# 맨 앞 데이터 접근
print(queue[0])

# 맨 앞 데이터 삭제
print(queue.popleft())

print(queue) # 큐 출력

>>>  A
>>>  A
>>>  deque(['B'])

• 큐 추상자료형 구현 바로가기

원형 큐

• 일반큐는 큐가 꽉 찼을 경우, 데이터 삽입 시 데이터를 한칸 씩 끌어와야 하므로 오버헤드가 발생하는 문제점이 있음.
• 원형 큐는 데이터 삽입 시오버헤드가 발생하지 않음

원형 큐 원리

• 원형 큐가 빈 경우 : front == rare

  

• 원형 큐가 꽉 찬 경우 : if (rear +1) % (큐의 SIZE) == front

  

• 원형 큐는 빈 것과 꽉 찬 것을 구별하기 위해 기본적으로 한칸을 비워두게됌

  • 예시) 일반 큐와 다르게 초기 front, rear 값을 index 0으로 설정하여 index 1부터 데이터가 쌓이게 함

• 데이터 삽입 시 : rear = (rear + 1) % (큐의 SIZE)

  • 선형 큐의 경우 데이터 삽입 시 출구쪽이 비어있다면 데이터를 한칸씩 땡겨와야 하기 때문에 삽입에 O(n)의 시간복잡도가 걸리는 반면,

    원형 큐의 경우 데이터의 위치와 관계없이 O(1)

• 데이터 추출 시 : front = (front + 1) % (큐의 SIZE)

원형 큐 구현 바로가기