큐(queue)

• FIFO

시간복잡도

• 원소추가 : O(1)
• 원소제거 : O(1)
• 제일 앞/뒤의 원소 확인 : O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

원형 큐(Circular queue)

• 배열로 구현 가능
• head 나 tail 이 끝 인덱스를 가리키는 상태에서 0번지로 다시 오도록 구현

선형배열 큐 vs 원형 큐

• 선형 배열로 구현한 큐 : 앞쪽에 공간이 많음에도 불구하고, 새 원소를 추가할 수 없는 상황이 발생

• 원형 큐 : head 나 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 개수가 배열의 크기보다 커지지 않는 한 문제가 없다.

STL queue

• push, pop
• front, back (back 으로 맨뒤 원소도 조회 가능하다는 점 유의하자!)
• empty, size

유의사항

• 큐가 비어있는데 front(), back(), pop() 을 호출하면 runtime error가 발생

• BFS, flood fill 유형 => STL queue 를 꼭 알아야함!!!!!!!!!