[ Open Data Structures ] - ArrayStack - 1

Array Based List

이번 장에선 Array를 사용하여 정보를 저장하는 List와 Queue의 Interfece에 대해 공부할 것입니다. 후에 Interface의 공통된 Operation을 정리하는데 기본적으로 List interface는 다음과 같은 네 가지의 기능을 제공합니다. Get, Set, Add, Remove. 다음은 각각의 Data Structure의 각 Operation에 대한 Running time을 나타낸 표입니다.

Figure a.

단일 배열을 사용하여 정보를 저장하는 자료구조는 공통적인 장단점이 존재합니다.

1. 배열은 격납된 어떤 정보든 접근하는데에 상수시간만을 요구합니다. 덕분에 Get(i)와 Set(i, x)의 수행시간도 상수 시간 내에 해결을 할 수 있게 됩니다.

2. 배열은 Dynamic하다고는 할 수 없습니다. 임의의 충분히 큰 배열이 존재한다고 했을 때, 중간 근방에 정보를 추가하거나 제거하는 작업은 곧 많은 수의 정보의 이동을 야기합니다. 바로 이 점이 Add와 Remove의 Running time이 n(전체 자료 또는 원소의 개수)과 i(삽입하려는 위치 혹은 Index)에 크게 의존하는 이유입니다.

3. 이론적으로 배열은 확장되거나 축소시킬 수가 없습니다. 한 번 정한 크기의 배열을 초과하는 수의 정보가 계속해서 배열에 삽입된다면 기존 배열을 제거하고 그 정보를 새롭게 생성한 배열에 복사해야 합니다. 당연하게도 이는 많은 비용(Time)을 요구하게 됩니다.

이상의 장단점 중에서 세 번째 포인트가 중요합니다. Figure a에는 배열의 삭제와 복사, 생성이 수치에 포함되어 있지 않습니다. 하지만 관리만 잘 한다면 평균적인 수행시간에 큰 변화가 없게 할 수 있다는 사실을 알 수 있습니다. 조금더 명확히 말하면 완전히 빈 자료구조에서 추가나 삭제 작업을 m번 수행할 때, 배열의 확장과 축소는 O(m)내에서 완료할 수 있다고 할 수 있습니다. 물론 일부 작업의 경우는 더 많은 Running time을 요구하지만 대략적으로 추산한 추가와 삭제를 m번의 수행하기 위해서 필요한 추가적인 Running time은 O(1)에 수렴하게 됩니다.

List interface를 구현함에 있어서는 데이터의 크기를 추적하는 것이 권장할 만한한데, C++에서 제공하는 배열은 일반적으로 size를 반환하는 함수가 내장되어 있지 않습니다. 따라서 따로 사용할 배열 Class를 만들도록 합니다. *나중에 떠오른 것이지만 vector container을 이용하는 것도 편리합니다.*

mLength는 배열의 '크기' 자체를 이른다는 점을 기억해야 합니다. 배열 내부에 격납된 원소의 개수가 아니라 배열의 크기를 이르는 말입니다. 그리고 이 크기는 생성시 결정되도록 합니다.

배열이기 때문에 아래와 같이 index를 통해 접근할 수 있도록 합니다.

그리고 어떤 배열이 다른 배열에 할당되는 경우가 있을 수 있습니다. 그런데, Array Class는 정보를 포인터의 형태로 잡고 있기 때문에 Assign이 발생하면 Constant time내에 정보교환을 다음과 같이 해결할 수 있습니다.

어떤 어려운 연산도 없이 포인터만 바꿔준다.

Array Stack : Fast Stack Operations Using  an Array

Array Stack은 Backing Array를 사용하여 List Interface를 구현합니다. index i를 가진 원소는 배열 a의 a[i]에 격납되어 있을 것입니다. 프로그램이 실행되는 어느 순간에서도 배열 a의 크기는 항상 충분히 크다고 가정합니다. 따라서, 실제로 배열이 갖는 정보의 개수를 추적하는 n(여기선 mSize)이 필요합니다. (격납공간이 충분히 크기 때문에 몇 개의 자료가 격납되어 있는지 확인할 수 있는 방법이 필요합니다.) 즉, Zero based indexing에서 언제나 배열의 크기 mArr.mLength >= mSize입니다.

The Basics

Array에서 mLength는 Array의 크기를 나타냈습니다. ArrayStack interface의 mSize는 Array가 가진 실제 원소(정보)의 개수를 가리킵니다. Array에 접근하거나 수정하기 위한 Get와 Set은 구현하는 것이 자명합니다. 필요한 Bound-Checking을 수행하고 ( 배열의 크기를 넘었는가 아닌가를 확인 ) 각각 Return을 해주거나 필요한 작업을 수행해주도록 합니다.

Adding and Removing

ArrayStack에서의 Adding/Removing Operation 진행을 다음과 같이 그려볼 수 있습니다. 

Add(_i, _x) 작업을 구현하기 위해선 먼저 배열 mArr가 포화상태인지 아닌지(혹은 더 추가할 수 있는 상태인지 아닌지)를 검증합니다. 만약, 포화상태라면 Resize()를 호출하여 배열 mArr을 확장합니다. Resize()에 관해서는 후에 더 자세히 다루기로 합니다. 현재로서는 Resize()를 호출하고 나면 mArr.mLength > mSize인 상태가 된다는 것만 인지하기로 합니다. 이런 논의는 차치하고 이제 확장된 mArr[i], mArr[i +1],...,mArr[n-1]의 원소들을 필요한 방향으로(상단의 그림참조) 한 칸씩 옮겨서 _x를 위한 공간을 확보하고 a[i]를 x와 같게 해주고 mSize를 1만큼 증가시켜보도록 하겠습니다.

만약, Resize()를 호출하는 잠재적인 비용을 무시한다면 Add operation의 수행시간은 추가되는 정보 x를 위해서 움직이는 원소들의 개수에 비례할 것입니다. 따라서, Add operation은 O(n-i)의 time을 요구합니다.

Remove operation을 구현하는 것도 비슷합니다. mArr[i + 1], ... , mArr[n - 1]을 필요한 방향으로(직관적으로 좌측 혹은 zero index를 향해) 한 칸씩 움직이며 mArr[i]를 Overwrite하고 mSize를 1만큼 감소시킵니다. 그리고 나서 mArr이 충분히 작은지를 검증하고 Resize()를 호출합니다. 충분히 작다는 것은 mArr.mLength >= 3*mSize를 만족한다는 것을 의미합니다.

만약, 여기서도 Resize()의 잠재적인 호출 비용을 무시한다면 O(n-i)의 Running time을 요구할 것입니다.