[Python] 큐(Queue)

 

 

≣ 목차

 

---

 큐   

큐

• 자료를 보관할 수 있는 선형 구조로 push(enqueue)와 pop(dequeue)이 반대에서 이루어지기 때문에 선입선출(FIFO)방식을 채택한 자료구조이다.
• 큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어날 때 사용된다.
• 또한 자료 생성이 여러 곳에서 발생하거나, 자료 이용이 여러 곳에서 발생할 때 사용된다.
• 스택과 마찬가지로 큐 역시 배열(리스트)과 연결 리스트(이중 연결 리스트)를 이용하여 구현가능하다.

연산 종류	설명	배열 시간 복잡도	연결 리스트 시간 복잡도
size()	현재 큐에 들어 있는 데이터 원소 수 반환	O(1)	O(1)
isEmpty()	현재 큐가 비어 있는지 판단	O(1)	O(1)
enqueue()	원소 x를 큐에 push	O(1)	O(1)
dequeue()	큐의 맨 앞 원소를 반환 후 제거	O(n)	O(1)
peek()	큐의 맨 앞 원소를 반환	O(1)	O(1원형 큐

연결 리스트를 활용한 큐 구현 코드

class LinkedListQueue:

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAfter(self.data.tail.prev, node)

    def dequeue(self):
        return self.data.popAfter(self.data.head)

    def peek(self):
        return self.data.head.next.data

---

원형 큐

큐는 인큐와 디큐가 반복될 경우 사용되는 메모리 영역이 옆으로 밀리는 현상이 발생한다. 이런 현상이 발생하는 것을 방지할 수 있는 자료구조가 바로 원형 큐이다. 큐의 한쪽 끝과 반대쪽 끝이 서로 맞닿아있는 구조이다. 이러한 구조 특성 때문에 기존 큐의 연산에서 큐가 가득찼는지 확인하는 isFull() 연산이 추가되어야 한다.

선형 배열을 활용한 큐 연산 구현 코드 

class CircularQueue:

    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]

---

우선순위 큐

우선순위 큐란 데이터 원소를 dequeue할 때, 우선순위에 따라 꺼내는 방식을 채택한 자료구조이다. 우선순위 큐는 아래 두 방법으로 구현이 가능하다.

1. 큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법
2. 큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법

이 두 방법 중에서 조금 더 유리한 방법은 1번 방법이다. 기존의 큐와 동일하게 우선순위 큐 역시 선형 배열과 연결 리스트를 사용하여 구현 가능하며, 연결 리스트를 사용한 구현 방식이 좀 더 효율적이다.

이중 연결 리스트를 활용한 우선순위 큐 구현

class PriorityQueue:

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

        while curr.next.next is not None and curr.next.data >= x:
            curr = curr.next
        return 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