0. 🔖 목차
- 큐 자료구조 개념
- 큐 종류
2-1. 선형 큐
2-2. 환형 큐
2-3. 덱
2-4. 우선순위 큐 - 코드 구현
1. 큐 자료구조
큐는 첫 번째로 들어온 요소가 첫 번째로 나가는, 즉 '선입선출' 원칙을 따르며 이를 FIFO(First In First Out)라고 한다.
큐에 요소를 넣는 작업을 Enqueue, 제거하는 작업을 Dequeue라고 한다.
- Rear: Enqueue 연산이 이루어지는 큐의 맨 뒤에 있는 공간을 가리키는 포인터
- Front: Dequeue 연산이 이루어지는 큐의 맨 앞에 있는 요소를 가리키는 포인터
이후의 설명은 C, C++ 처럼 메모리 참조가 불가능한 파이썬을 기준으로 설명
2. 큐 종류
2-1. 선형 큐(Linear Queue)
가장 기본적인 큐의 구조로 선형 구조로 되어있다.
Enqueue와 Dequeue 연산이 이루어지는 Rear와 Front를 통해서 요소를 추가, 삭제, 참조할 수 있다.
- 장점
- 가장 단순한 구조이며 구현하기 쉬움 - 단점
- 포인터를 통해 참조하는 경우가 아닌 경우, Enqueue 때 앞의 요소가 모두 한 칸 씩 이동해야함
2-2. 환형 큐(Circular Queue)
선형 큐의 단점을 해결하기 위해, 배열의 끝과 시작이 연결된 형태로 되어있다.
- 장점
- Enqueue를 할 때 앞의 요소를 이동시킬 필요가 없다. - 단점
- 사전에 큐의 크기를 정해야함(큐의 길이가 한정됨)
2-3. 덱(Deque, Double-Ended Queue)
양쪽 끝에서 Enqueue, Dequeue가 가능한 특수한 형태의 큐
파이썬의 경우 기본적으로 큐, 환형 큐 자료구조를 쓰지 않고 모두 덱 자료구조로 통일된다.
2-4. 우선순위 큐(Priority Queue)
큐의 요소에 우선순위를 두어 큐 내에서의 배치와 반환이 우선순위에 의해서 결정되는 구조.
Enqueue를 할 때 우선순위를 기준으로 적합한 위치에 삽입된다.
Dequeue를 할 때 항상 우선순위가 가장 높은 요소를 반환한다.
우선순위 큐는 추상적인 개념이고 이를 구현하기 위해 최대 힙 자료구조가 주로 사용된다.
최대 힙 자료구조는 각 노드가 자신의 부모 노드보다 작은 값으로 저장이 되어 있고 루트 노드는 항상 최대값이다.
Dequeue를 할 때 루트 노드의 값을 반환해주고, Enqueue를 할 때 최대 힙에 요소를 추가해주면 자연스럽게 우선순위 큐가 완성이 된다.
이때 요소의 변동이 생겨도 여전히 최대 힙의 성질을 유지해야 하기 때문에 heapify과정을 거친다.
3. 코드 구현
선형 큐와 환형 큐의 클래스를 배열로 구현해보았다.
개인적으로 front를 배열의 왼쪽, rear를 배열의 오른쪽으로 지정하는게 편해서 이렇게 구현했다.
리스트 메소드는 최대한 사용하지 않았으며 선형 큐의 경우 정직(?)하게 Dequeue를 하는 방법과 더 빠르게 Dequeue를 하는 방법까지 총 두 가지를 만들었다.
총 10000개의 데이터를 순서대로 삽입, 삭제했을때의 시간 비교는 아래와 같다.
class Queue:
def __init__(self) -> None:
pass
def __repr__(self) -> str:
print_list = []
f, r = self.front, self.rear
if self.is_full():
for i in range(self.max_len):
print_list.append(str(self.queue[(i+self.front)%self.max_len]))
else:
while f != r:
print_list.append(str(self.queue[f]))
f=(f+1)%self.max_len
return ' < '.join(print_list)
def is_empty(self) -> bool:
if self.queue[self.rear%self.max_len] is None and self.rear%self.max_len == self.front:
return True
else:
return False
def is_full(self) -> bool:
if self.queue[self.rear%self.max_len] is not None:
return True
else:
return False
class LinearQueue(Queue):
def __init__(self, list=[], max_len=1) -> None:
super()
if max_len <= 1 or len(list)>max_len:
raise Exception(f"입력으로 주어진 max_len의 값({max_len})이 너무 작습니다.")
list_len = len(list)
self.queue = [list[i] if i<list_len else None for i in range(max_len)]
self.max_len = max_len
self.front, self.rear = 0, list_len
@classmethod
def create_queue(self, list, max_len):
return LinearQueue(list, max_len=max_len)
def enqueue(self, element):
if not self.is_full():
self.queue[self.rear] = element
self.rear+=1
else:
raise Exception("현재 큐에 남은 공간이 없습니다.")
def dequeue(self) -> int:
if not self.is_empty():
ret = self.queue[self.front]
for i in range(self.front,self.rear):
if i < self.max_len - 1:
self.queue[i] = self.queue[i+1]
else:
self.queue[i] = None
self.rear -= 1
return ret
else:
raise Exception("현재 큐에 반환할 요소가 없습니다.")
def faster_dequeue(self) -> int:
if not self.is_empty():
ret = self.queue[self.front]
self.queue = self.queue[1:]+[None]
self.rear -= 1
return ret
else:
raise Exception("현재 큐에 반환할 요소가 없습니다.")
class CircularQueue(Queue):
def __init__(self, list=[], max_len=1) -> None:
super()
list_len = len(list)
self.max_len = max_len
if self.max_len <= 1 or len(list)>self.max_len:
raise Exception(f"입력으로 주어진 max_len의 값({self.max_len})이 너무 작습니다.")
self.queue = [list[i] if i<list_len else None for i in range(self.max_len)]
self.front, self.rear = 0, list_len
@classmethod
def create_queue(self, list, max_len):
return CircularQueue(list, max_len=max_len)
def enqueue(self, element):
if not self.is_full():
self.queue[self.rear] = element
self.rear += 1
self.rear %= self.max_len
else:
raise Exception("현재 큐에 남은 공간이 없습니다.")
def dequeue(self) -> int:
if not self.is_empty():
ret = self.queue[self.front]
self.queue[self.front] = None
self.front += 1
self.front %= self.max_len
return ret
else:
raise Exception("현재 큐에 반환할 요소가 없습니다.")
import time
n = int(10e3)
lq = LinearQueue.create_queue([], n)
cq = CircularQueue.create_queue([], n)
l_start = time.time()
for i in range(n):
lq.enqueue(i)
for _ in range(n):
lq.dequeue()
l_end = time.time()
print(f'선형 큐 소요 시간:{l_end-l_start}')
f_start = time.time()
for i in range(n):
lq.enqueue(i)
for _ in range(n):
lq.faster_dequeue()
f_end = time.time()
print(f'빠른 선형 큐 소요 시간:{f_end-f_start}')
c_start = time.time()
for i in range(n):
cq.enqueue(i)
for _ in range(n):
cq.dequeue()
c_end = time.time()
print(f'환형 큐 소요 시간:{c_end-c_start}')