큐(Queue)
큐(Queue) 는 한쪽에서는 삽입 연산만 가능하고, 다른 한쪽에서는 삭제 연산만 가능한 구조로,
먼저 들어온 작업이 먼저 처리되는, 선입선출 (First-In First-Out, FIFO) 의 알고리즘 원리를 따른다.
큐는 구조와 원래는 아래 이미지와 같다.
가장 마지막에 삽입된 자료는(이미지에서 data3 또는 data4)는 rear가 되고,
최초의 삭제 연산이 일어나기 전까지 front는 빈 공간을 가리킨다.
삽입 전의 상태에서는 data3이 가장 마지막 데이터이므로, rear였지만, data4가 삽입되면서 rear는 data4를 가리키도록 이동한다.
반대로 삭제가 일어날 때는 빈 공간을 가리키던 front는 삭제 연산이 일어나고 나면, 삭제된 data1이 위치하던 곳을 가리키게 된다.
그리고 다음 삭제 연산 발생 시 가리키던 위치의 다음 데이터를 삭제한다.
큐 클래스 구현하기
아래는 큐 클래스를 파이썬으로 구현한 코드이다.
삽입, 삭제 연산이 가능하고, 큐의 empty, full 여부를 알 수 있도록 메소드도 추가해두었다.
class Queue:
# CreateQueue
def __init__(self, size):
self.size = size
self.queue = [None] * size
self.front = -1
self.rear = -1
def is_empty(self):
return self.rear == -1
def is_full(self):
return self.rear == self.size - 1
def add(self, element):
if self.is_full():
print("Queue is full.")
return
else:
self.rear += 1
self.queue[self.rear] = element
return
def delete(self):
if self.is_empty():
print("Queue is empty.")
return
else:
self.front += 1
element = self.queue[self.front]
return element
def display(self):
print(self.queue[self.front+1:self.rear+1])
return
queue = Queue(3)
queue.delete()
queue.add(1)
queue.add(2)
queue.add(3)
queue.add(4)
queue.delete()
queue.display()원형 큐
기존의 큐는 배열 형태로 되어 있어, 큐의 크기가 정해져 있는 경우,
큐가 쉽게 꽉 찬 상태가 될 수 있다.
삭제 연산을 진행하여 앞에 공간이 남아있어도, 데이터의 추가는 큐의 뒤에서만 가능하므로, 데이터의 추가가 불가능한 상황이다.
이러한 문제를 해결하기 위해,
큐의 앞과 뒤, 즉 데이터의 입구와 출구 부분을 연결 시킨 원형 큐 (Circular Queue) 가 등장했다.
기존의 배열 형태의 큐는 인덱스를 비교하여 front와 rear의 위치가 동일한 경우, 큐가 full 하다고 판단한다면,
원형 큐는 단순 인덱스가 아닌, 큐의 사이즈 값으로 나머지 연산(mod)을 한 인덱스를 사용해,
큐의 앞쪽에 빈 공간을 다시 사용할 수 있다.
DEQ (Doubly-Ended Queue)
데크(DEQ) 는 원소의 삽입과 삭제를 큐의 양 끝에서 할 수 있는 자료구조 이다.
기존의 큐 자료구조는 원소의 삽입은 큐의 앞(front)에서, 삭제는 큐의 뒤(rear)에서만 가능했다면,
DEQ는 삽입과 삭제 모두를 front와 rear에서 가능하다.
파이썬에서도
from collections import deque 로 라이브러리를 가져와 사용할 수 있다.
DEQ를 사용하면,
한쪽 끝에서만 삽입과 삭제가 일어나는 스택(stack) 과
한쪽 끝에서 삽입, 반대쪽 끝에서 삭제가 일어나는 큐(queue) 구조를 모두 사용할 수 있다는 큰 장점이 있다.
우선순위 큐 (Priority Queue)
우선순위 큐 는 우선 순위에 따라 원소를 삽입하거나 삭제하는 큐로,
오름차순 또는 내림차순으로 데이터를 정렬하여,
우선순위가 높은 원소부터 먼저 삭제하는 자료구조이다.
원소를 삽입할 때마다 큐 내부의 원소들을 정렬을 해야하지만,
원소를 내보낼 때는(삭제) 가장 앞에 있는 값이 우선순위가 높을 것이므로, 시간이 덜 걸린다는 장점이 있다.
우선순위 큐에서 원소들을 정렬할 때 사용하는 알고리즘이 바로 힙 정렬 (Heap Sort) 인데,
이와 관련한 내용은
바로 요 포스팅 👇
[알고리즘] 정렬 (선택, 버블, 삽입, 병합, 퀵, 힙) (클릭)
에서 확인 가능하다.
