C++ 스타일로 Queue를 구현해보고, Java 스타일로도 구현해보면서
Abstract Data Type이라는 게 무엇인지 더 감이 확실히 왔다.
강의 자료에서 보면 Queue ADT는
- Data : 'stores sequence of ordered elements(?)'라고 정의되어 있고,
- Operation : Enqueue, Dequeue, isEmpty, isFull 이 있다고 한다.
이 정의는 언어에 독립적이며, 구현 방식과는 더더욱 독립적이다.
이번 예시 코드를 보면 Circular array를 활용해서 구현했다.
그러면 어떤 구현 방식이 가장 Queue ADT에 가까울까?
즉, 큐의 추상적 정의(FIFO)를 잘 드러내고, 구현 세부사항에 덜 의존하는 방식은 무엇일까?
이론적으로는
클래스 기반 구현 (인터페이스/메서드만 노출)이 Queue ADT에 가장 가깝다고 한다.
구조적으로는
Linked List 구현이 가장 자연스럽게 보여준다고 한다.
실무적으로는
성능이나 메모리 예측 가능성을 중시해야 하므로, Array-based Circular Queue를 선호한다고 한다.
