코딩테스트, 초급, 원형큐, circular Queue

[@kimjiyoung8655]

정말 이해하는데 도움이 많이 됐어요! 고맙습니다.

[@rootelon]

감사합니다!

[@raipen]

4:23 마지막에 디큐를 5번 했다면 rear와 front가 같은 위치에 있어야하는거 아닌가요? 왜 front가 하나 더 앞에 가있는지...

[@코드없는프로그래밍]

frontIdx를 5번 옮겨주기만 하면 됩니다. 한번 옮겨주면 숫자 7을 가르키고 두번 옮겨주면 숫자 2를 가르키고 세번 옮겨주면 숫자 4를 가르키고 네번 옮겨주면 숫자 6을 가르키고(자동적으로 mod 연산) 다섯번 옮겨주면 숫자 3을 가르킵니다. 감사합니다.

[@ssigz]

@@코드없는프로그래밍 implementation 보기 전까지 설명만 봐서는 front랑 rear만 가지고는 데이터가 비어있는 상태랑 꽉 차있는 상태를 구분할 수 없다고 생각이 되는데 size라는 추가 변수 없이는 구현 못할까요?

[@plttji2615]

혹시 그냥 queue 말고 왜 circular queue 를 사용하는지 더 자세히 여쭤봐도 될까요? 어떠한 장점이 있는거죠??

[@코드없는프로그래밍]

Circular Queue가 일반 queue에 비해서 가지는 잇점이 몇가지가 있습니다. 첫번째는 기본적인(linked list로 구현한) Queue의 randomIndex는 O(n)인데 반해, circular Queue는 O(1)으로 index에 접근이 가능합니다. 이는 C++ 의 Deque container와도 비슷합니다. 또 linked list queue에 비해 1d array가 가지는 잇점은 memory가 연속적이게 data가 들어있기 때문에 cache hit이 계속해서 나옵니다. 결론은 queue와 circular queue로 비교를 하기보다는 circular queue의 뒷단이 array나 list인 경우 가져가는 잇점들이 많습니다. 또궁금한것 있으시면 질문주세요.

[@plttji2615]

@@코드없는프로그래밍 감사합니다!