큐

FIFO(First In First Out) 형식 자료구조

 

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 앞/뒤의 원소 확인이 O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

만약 배열로 구현한다 칠 때,

삭제가 발생할 때마다 앞쪽에 쓸모없는 공간이 생기는데

이것을 방지할 수 있는 방법은 원형큐(맨첫 인덱스와, 마지막 인덱스를 연결)를 만드는 것이다.

그래서 실무에서 큐를 만들고자 한다면, 원형큐를 만들어 쓰는게 좋다.

 

원형큐의 경우 그냥 head와 tail로 지정한 부분이 배열 끝 수에 오면

0으로 바꿔주는 식으로 한다