1. 서론
원형 배열 기반의 데크(Deque)를 구현하고 있었는데 배열의 인덱스 이동을 처리하는 과정에서 깔끔하지 못 하게 처리하는 상황이 있었다. 아주 단순하고 기본적인 부분이지만 정말 확실하게 기억하기 위해 정리를 하려고 한다. 이번 글에선 원형 배열에서 인덱스를 증가시키거나 감소시킬 때 사용할 수 있는 코드를 기록할 것이다.
2. 원형 배열(Circular Array)
배열의 첫 번째 위치와 마지막 위치가 연결된 것처럼 구현하면 그것을 원형 배열이라고 한다. 연결돼 있다는 것은 0번 인덱스에서 인덱스를 감소시키면 배열의 마지막 인덱스가 되고, 배열의 마지막 위치에서 인덱스를 증가시키면 0번 인덱스가 되는 것을 의미한다. 원형 배열은 원형 큐(Circular Queue), 원형 데크(Circular Deque) 등을 구현할 때 사용된다.
3. 인덱스 증가
현재 원소의 인덱스를 저장하는 변수를 index, 배열의 크기를 size라고 할 때 다음 원소의 인덱스를 index에 저장하고 싶은 경우 아래와 같이 코드를 짤 수 있다.
index = (index + 1) % size;
C++
복사
배열의 크기를 넘어서지 않는다면 index는 1 증가할 것이다. 만약 현재 인덱스가 마지막 원소의 인덱스라면 index + 1과 size가 같게 되므로 나머지가 0이 되어 index에는 0이 저장된다.
4. 인덱스 감소
변수는 인덱스 증가 예제와 같을 때 현재 원소에서 이전 원소의 인덱스로 index의 값을 바꾸고 싶을 때 아래와 같이 코드를 작성할 수 있다.
index = (index - 1 + size) % size;
C++
복사
현재 원소가 첫 번째 원소가 아니라면 index의 값은 1 감소한다. 만약 현재 원소가 첫 번째 원소면 index - 1은 -1이 되고 size - 1이 index에 저장된다. size - 1은 배열 마지막 자리의 인덱스이다.