배열 큐의 한계와 링 버퍼 큐

큐?

 

큐는 선입 선출구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입 선출구조입니다.

 

큐에 데이터를 추가하는 작업을 enqueue, 데이터를 꺼내는 작업을 dequeue, 데이터를 꺼내는 쪽을 front, 데이터를 넣는 쪽을 rear라고 합니다.

 

배열로 큐 구현하기

 

1. enqueue

데이터 x를 enqueue하려면 배열 que의 마지막 원소의 인덱스인 idx의 다음 인덱스인 idx + 1에 추가합니다. 

que[idx + 1] = x

 

이때 처리의 복잡도는 O(1)이고, 비교적 적은 비용으로 구현할 수 있습니다.

 

2. dequeue

데이터 y를 dequeue하려면 배열 que의 0번째 원소를 꺼내고, 이후의 원소들을 앞쪽으로 옮겨야 합니다. 

이때의 처리 복잡도는 O(n)으로, 데이터를 꺼낼 때마다 이런 처리 작업을 수행하면 효율성이 떨어집니다.

 

그러므로 dequeue할 때 배열 안의 원소를 옮기지 않는 링 버퍼로 큐를 구현하겠습니다.

 

링 버퍼로 큐 구현하기

 

링 버퍼는 배열 맨 끝 원소 뒤에 맨 앞의 원소가 연결되는 자료구조입니다. 그럼 어떤 원소가 맨 앞이고, 어떤 원소가 맨 뒤인지 식별하는 변수 front, rear가 필요합니다. 그럼 enqueue와 dequeue를 수행하면 front와 rear의 값이 변한다는 것을 추측할 수 있겠네요.

 

① front: 맨 앞 원소의 인덱스

② rear: 맨 끝 원소 바로 다음 인덱스

 

만약 cnt개의 데이터가 들어있는 링 버퍼로 구현한 큐 rque가 있다고 가정하겠습니다.

 

1. enqueue

데이터 x를 enqueue 작업은 인덱스 rear의 rque에 값을 대입하고, rear에 1을 더해주는 것입니다.

rque[rear] = x
rear += 1

 

처리의 복잡도는 배열로 구현한 큐와 같이 O(1)입니다.

 

2. dequeue

데이터 y를 dequeue하는 작업은 rque의 front에 있는 값입니다. 이후 front에 1을 더해주는 것입니다.

return rque[front]
front += 1

 

이제 링 버퍼로 이루어진 고정 길이 큐인 FixedQueue를 구현해보겠습니다.

from typing import Any

class FixedQueue:
	
    def __init__(self, capacity: int) -> None:
    	self.cnt = 0      # 현재 데이터 개수
        self.front = 0
        self.rear = 0
        self.capacity = capacity
        self.que = [None] * capacity
    
    def enqueue(self, x: Any) -> None:
    	if self.no >= self.capacity:
            raise FixedQueue.Full
        
        self.que[self.rear] = x
        self.rear += 1
        self.cnt += 1
        
        # 만약 rear이 링 크기와 같다면 rear 인덱스에 0 대입
        if self.rear == self.capacity:
            self.rear = 0
            
    def dequeue(self) -> Any:
    	if self.cnt == 0:
            raise FixedQueue.Empty
        
        y = self.que[self.front]
        self.front += 1
        self.cnt -= 1
        
        if self.front == self.capacity:
            self.front = 0
        
        return y
        
    # 특정 데이터 z를 찾고 그 인덱스를 반환하는 함수 find
    def find(self, z: Any) -> Any:
        for i in range(self.cnt):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == z:
                return idx
        return -1

 

링 버퍼의 활용

 

링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있습니다. 예를 들면 원소 수가 n인 배열에 데이터를 계속해서 입력할 때 가장 최근에 들어온 데이터 n개만 저장하고 나머지 오래된 데이터는 버리는 경우입니다.

# 최근 n개의 데이터만을 저장하고 싶을 때
n = int(input())
a = [None] * n

# 실제 들어오는 데이터 cnt개
cnt = 0

while True:
    # cnt == n 인 경우 다시 0번째에 그 최신 값을 대입한다 -> "나머지"를 활용해서
    a[cnt % n] = int(input())
    cnt += 1
    
    ...