[Programmers] 11. 기본 자료구조: 큐 (Queue) (2): 큐의 응용: 환형/원형 큐, 우선순위 큐

illstandtall·2021년 4월 29일

programmers python 원형 큐 자료구조 큐

Programmers dev course

목록 보기

12/34

오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!

큐의 응용

자료구조 4-1. 환형/원형 큐 (Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며(원형으로) 이용하는 큐입니다.
큐가 가득 차면 더이상 원소를 넣을 수 없습니다. 따라서, 큐의 길이를 기억하고 있어야 합니다.
대기열을 구현하기 쉽습니다.

환형/원형 큐의 연산

기존 큐의 연산
isFull(): 큐에 데이터 원소가 꽉 차있는지를 판단합니다.
꽉차있으면 True를, 빈 공간이 있으면 False를 반환합니다.

배열로 구현

배열로 구현된 큐에서 큐의 맨 앞 데이터를 제거할 때(dequeue()), 모든 원소를 뒤로 미는 것 때문에 시간이 오래 걸렸습니다.
그러나, 환형/원형 큐는 큐의 크기가 정해져 있고, front와 rear를 활용하여 큐를 돌려가며 이용하기 때문에 dequeue()역시 빠르게 수행될 수 있습니다.

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

    def enqueue(self, x):
        if self.isFull():
            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]

자료구조 4-2. 우선순위 큐 (Priority Queue)

큐의 선입선출 방식을 따르지 않고, 원소들의 우선순위에 따라 순서대로 빠져나오는 방식의 큐입니다.
예) CPU 스케줄러

가장 큰 수부터 제거(dequeue())하는 우선순위 큐

우선순위를 유지하는 방법

큐에 데이터를 삽입(enqueue(x))할 때 우선순위 유지하기
큐에서 데이터를 제거(dequeue())할 때 우선순위 유지하기
- 모든 원소를 확인해야할 필요가 있기 때문에 조금 더 불리합니다.
enqueue(x)할 때 우선순위를 유지합니다.
- 따라서, 시간 복잡도는 enqueue(x): $O(N)$ , dequeue(x): $O(1)$ 이 됩니다.

우선순위 큐의 구현

배열 이용
연결 리스트 이용
- 삽입이 빈번하게 일어날 것이기 때문에 연결 리스트가 시간적으로 효율적입니다.
- 그러나, 메모리가 더 많이 사용될 것입니다.

from doublylinkedlist import Node
from doublylinkedlist import DoublyLinkedList

class PriorityQueue:
    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head

        while curr.next != self.queue.tail and x < curr.next.data:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data