[ Open DataStructures ] - The Interface

The Interface

자료구조를 배우는데 있어서 Interface와 Interface의 Implemetation을 구분하는 것은 매우 중요하다. Interface는 データ構造가 무엇을 하는지 묘사하는 것에 가깝고 자료구조의 Implementations는 실제　データ構造가 행하는 그 무엇을 어떻게 수행하는지 묘사되어 있는 것에 가깝다.

An Interface는 종종 Abstract Data Type이라도고 불리는데 이는 자료구조가 제공하는 Operation(혹은 関数나 作業)을 정의하고 해당 Operation의 Semantics나 의미 등을 정의한다. Interface는 자료구조가 어떻게 operations을 implement하는지 알려주지 않는다. 오직 Interface가 가진 Operation의 목록과 Operation에 필요한 parameters, 반환 값에 대한 정보만을 제공할 뿐이다.

Data Structure implementation은 Data Structure interface와는 다르게 각 Operation의 선언과 정의 및 알고리즘이 모두 드러나 있다. 이러한 이유로 하나의 Interface엔 다양한 Implementations가 있을 수 있다. 가령, 전에 List interface를 구현하는데 있어서 Array-based나 Pointer-based인 SLList를 각각 사용해 서로 다른 List Interface를 구현했다.

각각의 List Interface는 Implementation은 Array-based이거나 Pointer-based이지만 Interface의 기능은 완전히 같다.

The Queue interface

Queue interface는 대체로 Add(x)와 Remove()를 지원한다.

Add(x) : 원소 x를 Queue에 추가한다.

Remove() : Queue로부터 다음 원소(혹은 가장 최근에 추가된)를 제거한다.

Remove 작업이 argument를 받지 않는다는 점에 주목하자. 어떤 원소가 제거될지 결정하는 것은 일명 Queueing Discipline이다(強いて翻訳すると「並び規則」). 호출 시에 FIFO는 가장 최초에 추가된 원소가 제거되고 LIFO은 가장 최후에 추가된 원소가 제거된다. Priority Queue(優先順位Queue)의 경우엔 항상 가장 작은 원소(일련의 우선순위에 따른다.)를 제거하며 임의로 원소들 간의 연결을 끊기도 한다.

가장 유명한 Queueing Discipline은 LIFO(Last-In-First-Out)인데 너무 유명해서 Stack이라는 이름까지 붙어있다. 여타 Interfaces들과 혼동을 막기 위해서 종종 Add(x)는 Push(x), Remove()는 Pop()으로 쓰기도 한다. 지금까지는 구분없이 Deletion을 쓴다거나 했으나 앞으로는 약속에 따라 작성하기로 한다.

The Deque interface

Deque interface는 LIFO과 FIFO의 일반형이다. 즉, Front이든 Back이든 원소의 추가와 삭제가 자유로운 interface이다. 그런 이유로 Deque inteface는 AddFirst(x), RemoveFirst(), AddLast(x), RemoveLast() 등의 기능이 반드시 지원되어야 한다. Deque가 LIFO와 FIFO의 일반형이기 때문에 각각의 자료구조를 가진 Interface인 Queue와 Stack을 implentation하는 것이 가능하다. FIFO Queue는 AddLast(x)와 RemoveFirst()를 쓰고 LIFO인 Stack interface는 AddFirst(x)와 RemoveFirst()를 묶어서 구현하면 된다.

The list interface : Linear Sequence

FIFO Queue나 Stack, Deque는 사실 List interface의 부분집합이다. 보통 List interface는 x_0, x_1, ... , x_n-1까지 n개의 원소들의 나열을 나타낸다. 통상적으로 List interface는 다음과 같은 기능(Operation)을 포함한다.

위에서 보았던 AddFirst나 RemoveFirst등을 List interface로 다뤄보면 다음과 같이 쓸 수 있다.

n이 어떤 자료구조의 원소의 개수를 나타낸다는 점만 주의하면 좋겠다.

The USet interface : Unordered sets

USet은 이름에서 읽을 수 있는 것처럼 정렬되지 않은 원소들의 나열 혹은 집합이다. 이는 사실 수학의 집합과 관련된 이야기이다.  하나의 USet은 n개의 서로 중복되지도 않고 개별원소들은 중복되어 나타나지 않으며 특정한 정렬기준을 가지고 있지 않다. USet은 다음과 같은 Operation을 제공한다.

x와 y를 구분하는 것이 상당히 무의미한 짓이라고 여겨질 수도 있다. x와 y는 언뜻 보기엔 완전히 같은 값인 것 같으나 사실은 서로 구분되는 Objects들이다. 이런 명확한 정의로 Dictionary나 Map의 생성을 가능하게 해준다. 예를 들어, std::pair<int, int>의 형태로 {KeyX, ValueA}와 {KeyX, ValueB}는 Key값이 완전히 같지만 Value값이 다르기 때문에 Find({KeyX, ValueA})라고 할지라도 내장된 함수 내에선 ValueA와 ValueB를 비교하기 때문에 사용할 수 있게 된다.

The SSet interface : Sorted sets

USet이 정렬되지 않은 원소들의 집합을 나타냈다면 SSet은 정렬된 원소들의 집합을 나타낸다. USet과는 달리 SSet은 공통된 정렬조건이 있기 때문에 임의의 집합 내부의 원소들의 비교가 가능해진다. 다음과 같은 예시가 가능하다는 뜻이다.

SSet은 USet의 Size, Remove, Add와 같은 Methods를 제공하지만 Find는 조금 다르다.

이런 타입의 Find를 Successor Search라고 하기도 한다. USet의 Find와는 다르게 SSet의 경우엔 x와 완전히 같은 값이 없더라도 일정 조건만 만족하면 NULL이 아닌 어떤 값을 반환한다는 점에서 큰 의미가 있다.

물론, 이와 같은 구성은 높은 시간복잡도와 구현의 복잡성을 동반한다. 따라서, Find를 구현할 때는 어떤 상황에 어떻게 쓸지를 잘 고민해보는 것이 중요하다.