RingBuffer
-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48
안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다. 아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요. 그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요. RingBuffer는 read / write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다. 예시를 보면서 살펴볼게요. 처음엔 Read, Write 모두 0번째 인덱스에서 출발..