큐(Queue)의 활용

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

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

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

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

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

환형 큐(Circular Queues)

---

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

• 큐가 가득 차면?

  → 더 이상 원소를 넣을 수 없음(큐 길이를 기억하고 있어야함)

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

---

연산의 정의

---

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

배열로 구현한 환형 큐

---

• 정해진 길이 n(예를들면 6)의 리스트를 확보해두고

환형 큐를 구현

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으로 처리
            raise IndexError('Queue full')
        
        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]

[실습] 환형 큐 구현

문제

어서와! 자료구조와 알고리즘은 처음이지?15강 실습: 환형 큐 구현

문제 설명

Python 의 내장 데이터형인 리스트 (list) 를 이용하여 환형 큐의 추상적 자료 구조를 구현한 클래스 CircularQueue 를 완성하세요.

[참고] 함수 solution() 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 넣어 둔 것이니 무시해도 좋습니다. 또한, 실행 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 의미가 없습니다.

---

코드

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으로 처리
            raise IndexError('Queue full')
        
        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]