인프런 커뮤니티 질문&답변

사실 모든 자료구조는 구현하는 사람에 따라 달라집니다. 기준일 될만한 언어에 내장된 자료구조를 살펴보아도 언어마다 구현이 조금씩 다릅니다. 그래서 정답은 없습니다!

예를 들면 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가 어떻게 구현되어 있는지에 대해서 잘 아시는 분이 계시다면 답변해주시면 감사하겠습니다.