환형 큐 (Circular Queue)

큐의 활용

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우

 

 

자료를 생성하는 작업이 여러 곳에서 일어나는 경우

 

 

자료를 이용하는 작업이 여러곳에서 일어나는 경우

 

 

자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우

 

 

자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

 

 

 

 

 

환형 큐(Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용

 

 

 

 

큐가 가득차면 더이상 원소를 넣을 수 없으니 큐가 가득 찼는지 비어있는지 판단하기 위해서는 큐의 길이를 기억하고 있어야한다. 

 

 

 

 

 

환형 큐의 추상적 자료구조 구현

환형 큐를 구현하는데에도 선형 배열을 이용하거나 연결리스트를 이용할 수 있지만 여기에서는 선형 배열을 이용한다. 선형 배열과 연결 리스트의 장단점을 생각해보고 환형 큐를 만드는데 있어 어떤 장점을 택해야하는지 생각해보자.....

 

 

연산의 정의

• size() - 현재 큐에 들어있는 데이터 원소의 수를 구함
• isEmpty() - 현재 큐가 비어 있는지 판단
• isFull() - 큐에 데이터 원소가 꽉 차 있는지 판단
• enqueue(x) - 데이터 원소 x 를 큐에 추가
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거(또는 반환)
• peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)

 

 

 

배열로 구현한 환형 큐

정해진 길이 n (여기서 예제로 6) 의 리스트를 확보한다.

★front와 rear를 적절히 계산하여 배열을 환형으로 재활용★

 

 

 

class CircularQueue:
    # 빈 큐를 초기화 (주어진 인자로 큐의 최대) 길이 설정
    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1
        
    # 현재 큐 길이를 반환
    def size(self):
        return self.count
    
    # 큐가 비어있는가?
    def isEmpty(self):
        return self.count == 0
    
    # 큐가 꽉 차있는가?
    def isFull(self):
        return self.count == self.maxCount
    

    # 정해진 공간을 빙 돌려가며 이용, 즉 공간을 재활용해야 하기 때문에, 
    # front 와 rear 를 마냥 증가시키기만 함으로써는 환형 큐를 구성할 수 없다. -> 환형은 나머지를 이용하자!!!
    # 큐에 데이터 원소 추가
    def enqueue(self, x):
        if self.isFull():
            # IndexError('Queue full') exception으로 처리
            pass
        
        self.rear = (self.rear + 1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    # 큐에서 데이터 원소 뽑아내기
    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')

        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    # 큐의 맨 앞 원소 들여다 보기
    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]

 

 

퇴근 8분전~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~