큐는 FIFO(First In First Out)의 특징을 가진 자료구조이다. 먼저 큐에 들어간 원소가 제일 먼저 나오게 되고, 특정 위치에서만 원소를 넣거나 뺄 수 있기 때문에 스택과 마찬가지로 Restricted Structure라고 부른다. C++ STL에서는 queue<>으로 사용할 수 있다.
큐의 성질
- 원소의 추가는 O(1)
- 원소의 제거는 O(1)
-> 큐는 스택과 다르게 원소를 제거하면 맨 앞에 쓸모 없는 공간이 계속해서 누적되기 때문에, 이를 방지하기 위해 원형큐를 사용한다. - 제일 앞/뒤의 원소 확인이 O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능
-> 큐에서 추가되는 부분, 즉 뒤쪽을 rear라고 하고, 큐에서 제거되는 부분, 즉 앞쪽을 front라고 한다.
STL queue의 멤버 함수
- queue 선언
- queue<변수 타입> 이름
- queue 접근
- front(): 큐의 맨 앞 원소를 반환한다.
- back(): 큐의 맨 뒤 원소를 반환한다.
- queue 삽입/삭제
- push(element): 큐의 맨 앞에 element를 삽입한다.
- pop(): 큐의 맨 앞의 원소를 제거한다.
- queue 정보
- size(): 큐 원소의 개수를 반환한다.
- empty(): 큐가 비어있으면 true, 아니면 false를 반환한다.
