1. Queue란 무엇인가?
- 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식
- front(head)와 rear(tail)는 데이터의 위치를 가리키며 front는 데이터를 get할 수 있는 위치, rear은 데이터를 put할 수 있는 위치이다.
- BFS(너비우선탐색)에서 자주 쓰인다.
2. Queue의 종류
(1) 선형
막대 모양으로 된 큐이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.
(2) 환형
- 선형 큐의 문제점(배열로 큐를 선언할시 큐의 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달후 실제로는 데이터공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.
3. C++에서 queue의 기본 함수
- push(element): 큐에 원소를 추가(rear)
- pop(): 큐에 있는 원소를 삭제(front)
- front(): 큐 제일 앞에 있는 원소를 반환
- back(): 큐 제일 뒤에 있는 원소를 반환
- empty(): 큐가 비어있으면 true 아니면 false를 반환
- size(): 큐 사이즈를 반환