큐

순환 큐와 링크드 큐를 알아 보도록 하자.

 

순환 큐는 배열로 구현을 해 볼 수 있다. 이때에, 전단과 후단이 맞닿아 있다고 생각을 하고, 구현을 하도록 한다.

이떄 후단은 실제 마지막 아이템의 인덱스보다 1이 더 큰 수이다.

따라서 큐가 비어있는지, 가득차 있는지의 구분은 실제 큐의 길이 보다 1더 크게 구현을 하여 전단과 후단이 같으면 비어있고, 전단 보다 후단이 1 더 작으면 꽉 차이는 큐라고 생각 할 수 있다.

 

링크드 큐는 각각의 노드로 나누어 링크드 리스트 처럼 구현을 하는데 큐 구조체에서 front노드 와  rear노드를 저장하도록 한다.

구현은 큐의 특성 선입 선출에 맞게 추가 될때 마다 rear 노드를 바ㄷ꾸어 주고 삭제 시에 front 모드를 바꾸어주면 된다. 이떄의 이점은 순환 큐는 용량이 정해져 있지만 이 방식은 용량이 정해지지 않아서 무한히 붙일 수 가 있다.