[ Open Data Structures ] - Array Queue - 1

Array Queue : An Array-Based Queue

FIFO ( First In First Out ) 자료구조인 Array Queue를 가볍게 만들어본다. Array Stack은 배열에 들어온 순서( Add(x) Operation )대로 다시 나갔다( Remove() Operation ).

가만 생각해보면 Array Stack을 FIFO Queue를 구현하는데 선택하는 것은 비효율적인 선택이라고 할 수 있다. 왜냐하면, 배열의 한쪽 끝에서 Add를 하면 Remove는 반드시 정반대에서 수행해야 하기 때문이다. 두 작업 중 하나는 반드시 배열의 머리에서 수행되어야만 한다면 다른 하나는 반드시 꼬리에서 수행되어야만 하고 이는 원소의 개수 n에 비례한 Running time을 요구하게 된다.

Queue를 Array-Based로 효율적으로 구성하려면 무한한 크기의 배열이 존재한다고 가정하면 일이 수월하다는 것을 알 수 있다. Remove호출 시 삭제될 index를 추적하는 j를 도입하고 Queue에 저장된 실제 원소들의 개수를 추적하는 n을 도입할 수 있다. 배열의 크기가 무한하고 j와n이 각각 도입되어 있다면 다음과 같은 형태로 배열에 정보를 저장할 수 있다.

Initialise될 시에 각 j와 n은 당연히 0으로 설정된다. Element(원소나 자료)를 추가하려면 a[j+n]에 두고 개수를 추적하는 n을 1만큼 증가시킨다. 반대로 원소를 삭제하려면 a[j]의 원소를 삭제하고 j를 1만큼 증가, n을 1만큼 감소시키면 된다.

당연하게도, 이러한 형태의 문제해결 방법은 무한한 크기의 배열을 요구한다는 점이다. Array Queue는 무한한 배열의 형태 대신에 유한한 배열과 Modular arithmetic을 통하여 문제를 해결한다. 모듈로 연산은 시간과 날짜에 대한 문제를 해결할 때 주로 도입된다. 예를 들어서, 10:00에 5시간을 더하면 03:00이 된다. 수식을 도입하여 풀어서 쓰면 다음과 같은 형태가 된다.

통상적으로 뒤의 등식을 "15는 3의 모듈로 12와 합동이다(15 is congruent to 3 modulo 12)"라고 읽는다. 여기서 Binary operator를 도입해서 다음과 같이 쓸 수고 있다.

조금 더 일반적으로 어떤 임의의 정수 a와 양의 정수 m에 대해서, a mod m은 a = r + mk로 표현되는 {0, 1, .. ㅡ -1}에 속하는 고유의 어떤 정수 r이 된다(k는 임의의 정수). 어렵지 않고 편하게 말하면 r은 a를 m으로 나눈 나머지 값이다. C++를 포함한 상당수의 프로그래밍 언어에선 이 연산 기호를 '%'를 사용해서 나타낸다.

Modular arithmetic은 i mod a.length가 언제나 {0, 1, ... ,a.length - 1} 사이의 값을 내놓기 때문에 무한한 배열을 simulating할 때 상당히 유용하다. Modular arithmetic을 사용하여 Queue의 자료를 배열의 각 위치에 저장할 때, 다음과 같은 표현을 사용할 수 있다.

이렇게 표현하면 a.length - 1보다 큰 index들은 배열 a의 0-index를 시작으로 a를 마치 원형으로 둘러싼 Circular Array처럼 취급할 수 있다. 이제, 고려해야 할 것은 배열a에 저장된 원소의 개수가 배열 a의 크기를 초과하지 않게끔 유지해주는 것뿐이다. 이하에선 j = mElem2Remove, n = mNumOfElem이다. 가끔 혼용할 수도 있다.

Adding and Removing

다음은 Array Queue에서의 Add(_x)와 Remove()의 operation의 과정을 표현한 그림이다. 

Add(_x)를 implement하기 위해서 가장 먼저, 배열 a(여기서는 mArr)가 포화상태(Full)인지 아닌지 검증하고 필요하다면 Resize()를 호출하여 배열의 크기를 확장한다. 그리고 나서 mArr[(mElem2Remove+mNumOfElem)%mArr.mLength]에 정보를 저장하고 mNumOfElem을 1만큼 증가시킨다. 

Remove()를 implement하기 위해서, 가장 먼저 후에 반환(Return)하기 위해서 a[j]의 값을 저장해 준다. 그 다음, mNumOfElem을 1만큼 감소시키고 mElem2Remove ( modulo mArr.mLength )는

mElem2Remove = ( mElem2Remove + 1 ) mod mArr.mLength로 설정해준다. 마지막으로 붙들고 있던 mArr[mElem2Remove]값을 반환한다. 만약, 필요하다면 배열의 크기를 수축시키기 위해서 Resize()를 호출한다.

마지막으로 Resize()는 Array Stack에서 다루었던 Resize()와 유사한 형태다. 기존 배열의 크기의 두 배에 해당하는 새로운 배열 b를 만들고 정보를 복사한다. 정확히는 다음과 같이 이루어 진다.

를

에 각각 복사하는 작업이다. 그리고 mElem2Remove 즉, 다음으로 삭제할 index는 0으로 맞춘다.

Summary

Array Queue의 Performance는 다음과 같은 Theorem이 정리한다.

Theorem. Array Queue는 FIFO Queue Interface를 Implement한다. Resize()를 호출하는 비용을 무시한다면 Array Queue는 Add(x)와 Remove()를 O(1)의 시간복잡도로 해결한다. 더 나아가서 텅 빈 Array Queue에서 m번 의 Add(x)나 Remove()의 호출 동안에 호출된 Resize()의 총 비용은 O(m)에 수렴한다.

HiddenWriter/List at ArrayQueue (github.com)