[알고리즘] 큐(Queue)

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

큐(Queue)

한 쪽 끝에서 자료가 삽입되고, 반대쪽 끝에서 자료가 삭제되는 FIFO(First In First Out)형 식의 자료 구조
즉, 먼저 추가한 항목이 가장 먼저 제거되는 자료구조

• 큐(Queue)를 리스트(List)로 구현할 시 단점
  • 리스트로 구현하고 listN.pop(0)을 하는 경우 시간복잡도 O(n)이 된다.
  • 그 이유는 0번째 원소를 삭제할 시 1~N까지의 원소들을 다 앞으로 옮겨야하기 때문에 n을 다 돌아야한다.

큐(Queue)의 연산

• append(item): item 하나를 큐의 뒷 부분에 추가
• popleft(): 큐에 가장 앞에 있는 항목을 제거하고 반환

파이썬에서의 큐(Queue) 사용 예시

from collections import deque 
def solution():
  queue = deque() 
  queue.append(1) 
  queue.append(2) 
  queue.append(3) 
  print(queue.popleft()) 
  print(len(queue) == 0) 
  queue.popleft() 
  queue.popleft() 
  print(len(queue) == 0) 
  return queue
  
print(solution())

---

위와 같이 큐(Queue)를 학습한 후 풀이한 문제는 아래와 같다.

• 공주 구하기