큐

https://blog.encrypted.gg/934?category=773649 

[실전 알고리즘] 0x06강 - 큐

정의

• 한쪽 끝으로 원소를 넣고, 반대쪽 끝에서 원소를 뺄 수 있는 자료구조
• 원소가 추가되는 곳 : rear
• 원소가 제거되는 곳 : front
• FIFO

성질

• 원소의 추가&제거&제일 앞/뒤 확인 --> O(1)

구현

• 원소를 담을 배열 + 가장 앞에 있는 원소의 인덱스(head) + 가장 뒤에 있는 원소의 인덱스(+1)(tail)
• push --> tail 증가
• pop --> head 증가
• push, pop을 반복하면 배열 앞쪽에 사용하지 않는 공간이 많아짐
• 배열의 길이가 고정되어 있다면, tail이 배열 끝까지 갔다가, 다시 0으로 돌아옴 (마치 원형 배열)
• 혹은, push의 최대 횟수가 정해져 있다면 배열의 크기를 push의 최대 횟수보다 크게 두면 됌.