[파이썬 자료구조] 큐(Queue) - 큐의 활용, 환형큐 구현, 우선순위 큐 구현

1. 큐의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우.
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우

 

https://cwiki.apache.org/confluence/download/attachments/35981/competing-consumers.png?version=1&modificationDate=1410121265000&api=v2

 

2. 환형 큐 (Circular Queue)

 

https://s3.us-west-2.amazonaws.com/secure.notion-static.com/9d25f626-218a-4baa-8921-9491855e655e/Untitled.png?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=AKIAT73L2G45O3KS52Y5%2F20210824%2Fus-west-2%2Fs3%2Faws4_request&X-Amz-Date=20210824T174723Z&X-Amz-Expires=86400&X-Amz-Signature=3807c7d73e46950848eb6c7376596092481fa53b3c84246be21d562fad9fd3d2&X-Amz-SignedHeaders=host&response-content-disposition=filename%20%3D%22Untitled.png%22

환형 큐는 왼쪽과 같이 동그랗게 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 것을 말한다.

예를 들어

Q. enqueue(A) -> 큐에 A를 집어 넣는다.

Q.enqueue(B) -> 큐에 B를 집어 넣는다.

Q.enqueue(C) -> 큐에 C를 집어 넣는다.

r1 = Q.dequeue() → 들어간 순서대로 빠지므로 A가 가장 먼저 빠짐. r1에 A 저장

Q.enqueue(D) -> 큐에 D를 집어 넣는다.

r2 = Q.dequeue() → B가 빠짐. r1에 B 저장

이런식으로 데이터의 저장과 요소 제거가 반복하게 된다.

 

이때 데이터를 집어넣는 부분은 rear라는 포인터를 가지게 하고 데이터를 빼는 부분은 front라는 포인터를 가지게 한다.

 

따라서 배열로 구현한 환형 큐는

→ 정해진 길이 n (그림에서는 8) 의 리스트를 확보해 두고

Q.enqueue(A) → A가 큐에 들어감, A가 있는 자리를 rear로 지정

Q.enqueue(B) → B가 큐에 들어감, B가 있는 자리를 rear로 지정

r1 = Q.dequeue() → r1에 A가 저장. 큐에 있는 A는 무효한 데이터 가 됨. A가 있던 큐의 자리를 front로 지정

 

이런식으로 작동한다.

그럼 코드로 구현해 보자.

 

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)]

환형 큐는 요소를 추가하거나 제거할 때 리스트의 마지막 자리에서 다시 처음 자리로 이동하여 요소를 추가하거나 제거해야 한다는 점에 유의해야한다. 즉 

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

여기에서 self.rear의 값을 그냥 한자리 이동하니까 self.rear+1 해버리면 안된다는 것이다. 

'원형'으로 작동하게 만들어야 하기 때문에 마지막 자리에서 그 다음 자리는 첫자리가 되도록 해야한다.

 

예를 들어 만약 이 큐가 8자리가 있는 큐 라면 자리는 0부터 7까지 있다. 

큐에 0부터 7까지 데이터가 다 꽉차있다가 0에 있는 데이터가 나가서 다음에 들어올 데이터를 0에 넣고 싶다고 해보자.

self.rear + 1로 되어 있다면 self.rear가 8이 되어 버린다. 에러가 발생한다.

위와 같이  self.rear = (self.rear+1)%(self.maxCount) 로 되어 있다면 현재 maxCount는 8이고 따라서 현재 self.rear 값인 7에 1을 더하고 8로 나눈 나머지는 0이다. self.rear=0 즉 다시 0인 자리로 돌아간다.

 

나도 처음에 코드 작성할 때 % 연산자는 생각도 못하고 if문으로 짰었는데 %를 이용해 굉장히 간단하게 작성할 수 있다.

 

 

 

3. 우선순위 큐( priority Queue)

 

마지막으로 우선순위 큐에 대해 알아보자.

 

→ 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

 

우선순위를 지정하는 방법은 두가지가 있다.

1. Enqueue 할 때 우선순위 순서를 유지하도록 하여 Dequeue할 때 그냥 앞에서부터 차례대로 뺄 수 있도록 하는 것. →시간적인 측면에서 얘가 더 유리하다.
2. Dequeue 할 때 우선 순위 높은 것을 선택하여 빼내는 것.

 

그렇다면 배열과 연결리스트도 비교해보자.

1. 선형배열 이용 → 메모리 측면에서 더 유리
2. 연결 리스트 이용 → 시간적 측면에서 더 유리

배열을 이용하면 우선순위를 유지하며 Enqueue 할 때 하나를 넣을 때마다 뒤에 있는 요소를 하나씩 전부 미뤄주어야 하기 때문에 시간적 측면에서는 연결리스트가 유리하다.

 

우선순위 큐는 연결리스트를 이용하여 코드를 구현하였다.

이 코드는 숫자로 이루어진 연결리스트를 목적으로 만들었으며 숫자가 작을 수록 우선순위가 높다는 가정이다.

즉 우선순위가 높은 것은 가장 먼저 빠져 나갈 것들이다. 

Dequeue는 tail에 가까운 자리부터 빼낸다고 설정하였고 따라서 숫자가 낮은 것들이 tail에 가깝다.

그 점에 유의하여 코드를 보길 바란다.

 

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount


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.data != None and x < curr.next.data:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)
        
    '''
    def enqueue(self, x): # 오답.
        newNode = Node(x)
        curr = self.queue.head.next
        # 이유는 이 curr 때문이다. curr 위치에 주의 해야한다. 
        # 이 코드의 경우 head 다음 을 첫 curr로 지정했다.
        # 조건에 맞는 curr까지 가는 경우 다음 노드로 지정되기 때문에 
        # 이 코드를 사용하려면 insertAfter 에서 curr 전 노드를 보내야한다.
        while curr.data!=None and x < curr.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


p=PriorityQueue()
p.enqueue(3)
p.enqueue(2)
print(p.dequeue())

 

enqueue 할때 우선순위를 신경써서 큐에 집어 넣는 방식을 택했기 때문에 enqueue 부분 외에는 크게 어려운 부분은 없다.

다만 enqueue 부분에서 코드를 작성할 때 curr의 위치를 주의하도록 하자. 잘못된 위치를 인자로 넘겨줄 수 있다.

 

알고리즘 짤 때에는 간단하게라도 예시를 들어가며 직접 진행을 손으로 해보는 것이 에러를 줄이는 방법인 것 같다.

특히 반복문!!