큐란 ?

-FIFO 의 자료형
-선형 큐 / 원형 큐 두가지 종류가 있음
-double ended que (deque)자료형을 이용해 구현 할 수 있다.
-서비스에 우선순위를 둔 것임

큐를 쓰면 좋은 상황

-우선순위에 맞게 정렬 시켜줘야하는 문제가 생길 수 있음
->이때 큐를 쓰는것이 좋다
-응용 사례 :

• 서비스의 콜큐(여러사람이 서비스를 요청할때,큐로 받아서 사용하면 좋을것 같음)
• 프린트와 컴퓨터 사이에서 배치 서비스를 할때
• 실시간 비디오 스트리밍에서 버퍼링
• 대기열을 만들때
• 통신에서 패킷들의 모델링을 할때

큐의 ADT

큐의 데이터 특징 : 선입선출의 데이터를 유지하는 접근방법을 유지
삽입은 큐의 후단에서, 삭제는 전단에서 이루어진다.

연산 :

• queue : 비어있는 새로운 큐를 만든다
• isEmpty() : 큐가 비어있으면 True를 아니면 False를 반환한다.
• enqueue(x) : 항목 x 를 큐의 맨 뒤에 추가한다.
• dequeue() : 큐의 맨 앞에 있는 항목을 꺼내 반환한다.
• peek() : 큐의 모든 항목을 삭제하지 않고 반환한다.
• size() : 큐의 모든 항목들의 개수를 반환한다.
• clear() : 큐를 공백 상태로 만든다.

큐의 규현

• 파이썬의 리스트 활용
  -append 가 list의 맨 끝에 추가하고
  -pop(0) 을 하면 맨 앞에 있는 데이터를 가져옴

• 선형 큐의 문제점
  -비효율 적이다.
  -삽입연산 O(1) 의 시간 복잡도를 가진다
  -삭제연산 O(n) 의 시간 복잡도를 가진다.
  :삭제되는 데이터의 자리를 채우기 위해 데이터를 앞으로 옮기게 됨
  -> 어떻게 하면 자리를 채우지 않고, 삭제를 할 수 있을까??->! 원형큐를 이용하면 된다
  
• 원형 큐 : 배열을 원형으로 사용하는 큐
  데이터를 옮기는게 아니라,
  맨 앞과,맨 뒤에 포인터를 두는데 그것이 front/rear 이고 이것들의 인덱스를 바꿔준다.
  -포인터의 계산 방법 : 나머지 연산자를 사용한다.
  front : (fornt+1)%max_qsize
  rear : (real+1)%max_quesize
  -O(2)로 시간 복잡도를 가지게 된다.