resize 관련 질문이 있습니다.

Question

Circular Queue도 마찬가지로 크기가 꽉 차면 리사이즈가 일어난다고 하셨는데 더블링 리사이즈가 일어났을 때 배열이 두배로 커지고 다시 앞부분이 1부터 들어가게 되는 건가요? 아니면 8분19초 상황에서 11 12 13 4 5 6 7 8 9 10 14 15 16 이렇게 들어가는 건가요?

개발남노씨 · Answer

사실 모든 자료구조는 구현하는 사람에 따라 달라집니다. 기준일 될만한 언어에 내장된 자료구조를 살펴보아도 언어마다 구현이 조금씩 다릅니다. 그래서 정답은 없습니다! 예를 들면 https://en.cppreference.com/w/cpp/container/queue 를 참고했을 때, C++ STL에서 Queue에 대한 내용은 자세히 살펴보기 어려웠지만 https://en.cppreference.com/w/cpp/container/deque 를 보게 되면 우리가 알던 방식과는 많이 다른 방식으로 deque이 구현된걸 알 수 있었습니다. 저장공간이 부족하면 새로운 fixed-array를 할당하여 deque의 size를 확장합니다. 따라서 기존에 있던 데이터를 복사하여 이동시킬 필요가 없어 집니다. As opposed to std::vector , the elements of a deque are not stored contiguously : typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one. The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location. On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++). 따라서 Circular Queue또한 사용자가 정의하기에 따라 다르게 구현할 수 있습니다. 대부분의 인터넷에서 볼 수 있는 구현은 isFull == true 이면 overflow 경고 메세지를 주는 방식으로 되어 있습니다. 만약에 제가 더블링 리사이즈 하여 확장하는 circular queue 자료구조를 구현한다면 직관적인 방법으로 다음과 같이 할 것 같습니다. (rear) (front) 11 12 13 4 5 6 7 8 9 10 (full) (front) (rear) 4 5 6 7 8 9 10 11 12 13 __ __ __ __ __ __ __ __ (doubling) 4 5 6 7 8 9 10 11 12 13 14 __ __ __ __ __ __ __ (doubling) 4 5 6 7 8 9 10 11 12 13 14 15 __ __ __ __ __ __ (doubling) 해당 방식이 직관적이라서 코드를 작성하기에도 수월합니다. 좋은 질문 감사드립니다. 혹시 풀리지 않은 의혹(?)이 있으시면 편하게 말씀해주세요 :) 그리고 각 언어에 내장되어있는 Queue가 어떻게 구현되어 있는지에 대해서 잘 아시는 분이 계시다면 답변해주시면 감사하겠습니다.