11. 큐

---

 

 

1. 큐 (Queue)

큐는 스택과 같이 데이터를 임시 저장할 때 사용하는 대표적인 자료구조이다.

선입선출(FIFO) 방식에 따라 데이터를 입출력한다.

• 인큐(Enqueue): 큐에 데이터를 추가하는 작업
• 디큐(Dequeue): 큐에서 데이터를 꺼내는 작업
• 프런트(Front): 큐의 맨 앞 원소 (데이터를 꺼내는 쪽)
• 리어(Rear): 큐의 맨 뒤 원소 (데이터를 추가하는 쪽)

 

---

 

2. 배열을 큐로 구현한다면?

크기가 8인 배열 객체 que[ ]를 구현한다고 가정해보자.

 

2.1) 24를 인큐

맨 끝 데이터 que[3] 다음 원소인 que[4]에 24를 저장한다.

시간 복잡도는 O(1)으로, 비교적 적은 비용이 발생한다.

 

2.2) 19를 디큐

맨 앞 데이터 que[0]을 꺼내고, 모든 원소를 앞으로 이동시킨다.

시간 복잡도는 O(n)으로, 큐에 들어있는 데이터의 수가 늘어날수록 효율이 떨어진다.

 

---

 

3. 링 버퍼 (Ring Buffer)

배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 링 형태의 자료구조.

링 버퍼로 큐를 구현하면 원소를 옮기지 않고 프런트와 리어 인덱스만 업데이트하여 인큐, 디큐 연산 수행이 가능하다.

• front 변수: 맨 앞 원소의 인덱스 저장
• rear 변수: 맨 끝 원소의 바로 뒤 인덱스 저장 (다음에 인큐되는 데이터 저장 위치)

 

3.1) 링 버퍼를 이용한 큐 연산

큐인 상태 (Capacity == 12)일 경우, 35, 56, 24, 68, 95, 73, 19가 que[7], que[8], ~, que[0], que[1]에 저장된다.

front는 7, rear는 2가 된다.

여기서 82를 인큐하면 que[2]에 82를 저장하고, rear 값을 1 증가시킨다.

front는 7, rear는 3이 된다.

여기서 디큐를 실행하면 que[7]의 값을 반환하고, front 값을 1 증가시킨다.

front는 8, rear는 3이 된다.

 

---

 

4. FixedQueue 클래스 구현

링 버퍼를 사용하여 크기가 고정된 큐를 구현해보자.

from typing import Any

class FixedQueue :
    class Empty(Exception) :
        pass
        
    
    class Full(Exception) :
        pass

    def __init__(self, capacity: int) -> None :
        self.no = 0
        self.front = 0
        self.rear = 0
        self.capacity = capacity
        self.que = [None] * capacity

    def __len__(self) -> int :
        return self.no
        
    def is_empty(self) -> bool :
        return self.no <= 0
        
    def is_full(self) -> bool :
        return self.no >= self.capacity

    def enque(self, x: Any) -> None :
        if (self.is_full()) :
            raise FixedQueue.Full
        
        self.que[self.rear] = x
        self.rear += 1
        self.no += 1
        
        if (self.rear == self.capacity) :
            self.rear = 0

    def deque(self) -> Any :
        if (self.is_empty()) :
            raise FixedQueue.Empty
        
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        
        if (self.front == self.capacity) :
            self.front = 0
            
        return x

    def peek(self) -> Any :
        if (self.is_empty()) :
            raise FixedQueue.Empty
        
        return self.que[self.front]
        
        
    def find(self, value: Any) -> Any :
        for i in range(self.no) :
            idx = (i + self.front) % self.capacity
            
            if (self.que[idx] == value) :
                return idx
            
        return -1

    def cout(self, value: Any) -> bool :
        c = 0
        
        for i in range(self.no) :
            idx = (i + self.front) % self.capacity
            
            if (self.que[idx] == vaule) :
                c += 1
            
        return c
       
       
    def __contains__(self, value: Any) -> bool :
        return self.count(value)
    
    
    def clear(self) -> None :
        self.no = self.front = self.rear = 0
    
    
    def dump(self) -> None :
        if (self.is_empty()) :
            print('Queue is Empty')
        else :
            for i in range(self.no) :
                 print(self.que[(i + self.front) self.capacity], end='')
            print()

 

---

 

5. 링 버퍼 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

원소 수가 n인 배열에 가장 최근 입력된 n개의 데이터만 저장하고 오래된 데이터는 버린다.

 

---

 

---

수고하셨습니다!

---