큐란 ?
-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)로 시간 복잡도를 가지게 된다.