큐(Queues)

1. 큐의 정의 및 특징

큐는 자료를 보관하는 선형 구조 중 하나이다. 자료를 넣을 때는 한 쪽에서 밀어넣고(Enqueue) 꺼낼 때는 반대 쪽에서 꺼낸다(Dequeue). 때문에 선입선출(First In, First Out)(FIFO)의 원칙을 갖는다.
큐의 가장 쉬운 예시로는 ‘줄서기’가 있다. 먼저 줄을 선 순서대로 처리가 된다.
자료구조의 공부를 위해 직접적으로 구현하겠으나, from pythonds.basic.queue import Queue 설치를 통해 공개 라이브러리로 제공된 큐를 사용할 수도 있다.

2. 큐의 동작 개요

Enqueue를 하면 순서대로 쌓인다. Dequeue를 하면 먼저 들어온 순서대로 나간다.

3. 큐의 구현

1) 연산 정의

• size(): 현재 큐에 들어있는 데이터 원소의 수
• isEmpty(): 현재 큐가 비어있는가?
• enqueue(x): x를 큐에 추가
• dequeue(): 맨 앞에 저장된 데이터 원소 제거 & 반환
• peek(): 맨 앞에 저장된 데이터 원소 반환. 제거는 하지 않음

2) 구현 방식과 연산 복잡도
배열 혹은 이중연결리스트를 이용할 수 있다.
배열을 이용할 경우, 나머지 연산은 모두 다 O(1)이나, dequeue만 O(n)으로 큐의 길이에 비례하는 연산 시간을 가진다. Dequeue는 맨 앞 요소를 꺼내서 없애므로 빈 자리를 그 뒤의 원소들이 한 칸씩 앞으로 옮겨와 채워져야 하며 마지막 원소가 없어져야 하기 때문이다.

4. 큐의 코드 구현

이중연결리스트를 이용해 구현해볼 것이다. 이중 연결리스트의 구현은 여기선 생략한다.

class LinkedListQueue:
    def __init__(self):
    	# 큐로 사용할 이중연결리스트를 선언한다.
        self.data = DoublyLinkedList()

    ## 큐의 크기(원소 개수)를 리턴
    def size(self):
        return self.data.nodeCount

	## 큐가 비었는지 알려줌
    def isEmpty(self):
        return self.data.nodeCount == 0

	## 요소를 큐에 삽입함
    def enqueue(self, item):
        node = Node(item)  # 새 노드를 만듦
        self.data.insertAt(self.data.nodeCount + 1, node)  # 맨 뒤에 추가함

	## 큐에서 요소를 꺼냄
    def dequeue(self):
        return self.data.popAt(1)  # 가장 첫번째 노드를 꺼냄

	## 가장 앞의 요소 값을 알려줌
    def peek(self):
        return self.data.head.next.data  # 첫 번째 노드의 값임

환형 큐(Circular Queues)

1. 환형 큐의 특징

환형 큐는 큐의 최대치를 정해둔 뒤 해당 저장 공간을 빙 돌려가며 이용한다.
배열처럼 일자(선형)로 큐를 만들 경우, Dequeue 연산에서 본 바와 같이 하나를 빼면 앞으로 자리를 옮겨와야 하므로 불편한데, 환형 큐로 이 문제를 해결할 수 있다.
환형 큐는 컴퓨터 메모리 등의 동작에 사용하곤 한다.
보통 dequeue 연산으로 꺼내는 부분은 front, enqueue로 넣는 부분은 rear이라고 한다.
큐가 가득 차면 더이상 원소 넣을 수 없으므로 큐 길이를 기억하고 있어야 한다. 또는 rear와 front가 같은지로 알 수도 있다.

2. 추가적 연산의 정의

• isFull(): 큐에 데이터 원소가 꽉 차있는가?

3. 배열로 구현한 환형 큐

전체 큐 크기를 n라 할 때, 크기 n의 빈 리스트를 생성한다. 처음엔 front = rear = -1라 두고 시작한다.
큐가 작동하며 새로 enqueue 되는 곳이 rear, dequeue 지점이 front가 된다. dequeue시 그곳의 데이터는 무효한 데이터가 된다.
배열 끝까지 rear/front가 가면 다시 맨 처음으로 돌아오도록 한다. 이때 배열의 크기로 나머지 연산(%)을 사용하면 된다. 다시 처음으로 돌아오고 rear이 그 자리에 enqueue를 한다면 무효한 데이터가 있는 경우 그저 덮어쓰면 된다.
남은 자리가 남아있지 않을 때까지 삽입이 가능하다.

그림의 [1]에서 첫 번째 원소가 삽입되고 해당 위치를 rear라 했다. [2]처럼 계속 삽입하며 D가 rear가 되어 있다.

[3]에서 보면 맨 앞 요소인 A를 dequeue했다. 그러면서 front가 A의 위치를 가리키고 있으며, A라는 데이터는 무효한 데이터가 되었다. 또 한 번 dequeue를 하면 B로 front의 위치가 이동해 있다. 즉, 유효한 데이터는 front의 뒤부터 rear까지인 것이다.

만약 [5]처럼 rear이 배열의 끝에 위치했다고 하자. 그럼 rear은 [6]처럼 배열의 처음으로 돌아와 계속 삽입을 할 수 있게 한다.

4. 환형 큐의 코드 구현

class CircularQueue:
    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n  # None으로 공간을 초기화함
        self.count = 0
        self.front = -1
        self.rear = -1  # front와 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
        	# 나머지 연산을 이용해 현재 rear의 다음 위치(맨 뒤 위치라면 다시 맨 앞으로)를 구함
        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
        	# 나머지 연산을 이용해 현재 front의 다음 위치(맨 뒤라면 다시 맨 앞으로)를 구함
        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]

우선순위 큐(Priority Queues)

1. 우선순위 큐의 특징

큐의 선입선출(FIFO) 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식이다. 우선순위는 정의하기 나름인데, 예를 들자면 작은 수가 우선순위가 높은 원소를 우선할 수 있다.
우선순위 큐는 운영체제의 CPU 스케줄러 등에 활용되고 있다.

2. 우선순위 큐의 구현

아래와 같이 두 가지 방식으로 구현할 수 있다.

• (가) Enqueue할 때 우선순위 순서를 유지하도록 한다.
• (나) Dequeue할 때 우선순위 높은 것을 선택하도록 한다.

이 때 (가)번이 조금 더 유리한데, (나)를 선택할 경우 dequeue 할 때 모든 데이터 원소를 다 탐색해야 하므로 큐의 길이에 비례해 시간이 걸린다. (가)의 경우 이미 큐가 정렬되어 있으므로 시간적 측면에서 조금 더 유리하다.

또한 구조를 구현하는 방법으로는 또 두 가지 방식이 있다.

• (가) 선형 배열 이용
• (나) 연결리스트 이용

(가)의 경우 메모리 차지량은 (나)보다 적겠으나, 시간 방면에서는 (나)가 더 유리하다. 우선순위 큐의 경우엔 특히 자료의 중간에 새 요소를 삽입하는 일이 빈번하게 발생하는데, 배열로 구현할 경우 앞뒤로 밀어내고 당겨야 하는 연산이 추가적으로 필요하기 때문이다.

3. 우선순위 큐의 코드 구현

이중연결리스트를 사용하며, 역시 여기에서도 우선순위 큐 클래스만 나타냈다.

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())
        	# 맨 뒤에 작은 수가 있으므로 가장 뒤에서 pop을 함

	# 큐에서 가장 우선순위가 높은 수(최솟값)을 알려줌
    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data