Queue
큐(Queue)는 선형 자료구조로, 데이터를 저장하고 검색하는 데 사용되는 중요한 자료구조이다.
queue는 데이터를 저장할 때 "FIFO(First-In-First-Out)" 원칙을 따른다. 즉, 먼저 Queue에 추가된 데이터는 먼저 처리되고 제거된다.
Queue의 구성요소
- 데이터 요소(Elements): 큐에 저장되는 실제 데이터 항목, 큐에 추가되거나 제거된다.
- 프론트(Front)와 리어(Rear): 큐의 시작과 끝 지점을 나타내는 두 포인터이다. 이들은 데이터의 추가 및 제거에 사용된다.
- 리어(Rear) : 큐의 끝 지점을 가리키는 포인터이다. 큐에 추가 연산이 수행되면, 새로운 데이터가 리어에 추가된다.
- Enqueue(데이터 추가): 큐의 리어에 데이터를 추가, 새로운 데이터가 큐의 가장 뒤에 추가된다.
- Dequeue(데이터 제거): 큐의 프런트에서 데이터를 제거하고 반환한다. 가장 먼저 추가된 데이터가 가장 먼저 제거된다.
- Peek(데이터 확인):큐의 프런트에서 데이터를 확인하지만 제거하지 않는다.
삽입 연산은 새로운 데이터를 큐의 뒤(rear)로 넣는 것이고, 삭제 연산은 기존 데이터를 큐의 앞(front)에서 빼는 것이다.
Queue의 동작
큐는 뒤에서 데이터가 추가되고, 데이터가 하나씩 삭제되는 구조를 가지고 있다.
스택은 한 쪽에서 삽입과 삭제가 일어나지만, 큐는 서로 반대쪽에서 일어난다고 생각하면 된다.
Queue의 종류
-
선형 큐(Linear Queue): 데이터를 FIFO 순서로 처리하는 가장 기본적인 큐
하지만, 삽입과 삭제를 여러번 진행할 경우 그림처럼 배열의 위치가 점점 오른쪽으로 이동하게된다.
즉 이렇게 구현하게 된다면, 붉게 표시된 배열의 빈 공간은 사용되지 않지만 메모리를 계속 차지함으로, 메모리 낭비를 발생시킨다. -
환형 큐(Cicular Queue) : 큐의 마지막 요소가 첫 요소와 연결된 큐로, 원형으로 순환한다.
환형 큐 구현
class CircularQueue:
def __init__(self, size):
self.size = size # 큐의 크기를 설정합니다.
self.queue = [None] * size # 크기만큼의 리스트를 생성하여 큐를 초기화합니다.
self.front = self.rear = -1 # front와 rear를 초기화합니다.
def is_full(self):
# rear 다음 위치가 front인 경우 큐가 가득 찬 상태입니다.
return (self.rear + 1) % self.size == self.front
def is_empty(self):
# front와 rear가 동일한 경우 큐가 비어 있는 상태입니다.
return self.front == -1
def enqueue(self, data):
if self.is_full():
print("Queue is full")
elif self.is_empty():
self.front = self.rear = 0 # 큐가 비어 있는 경우 front와 rear를 0으로 설정합니다.
self.queue[self.rear] = data
else:
self.rear = (self.rear + 1) % self.size # rear를 다음 위치로 이동합니다.
self.queue[self.rear] = data
def dequeue(self):
if self.is_empty():
print("Queue is empty")
return None
elif self.front == self.rear:
temp = self.queue[self.front]
self.front = self.rear = -1 # 큐에 하나의 요소만 남아 있는 경우 front와 rear를 초기화합니다.
return temp
else:
temp = self.queue[self.front]
self.front = (self.front + 1) % self.size # front를 다음 위치로 이동합니다.
return temp
def front(self):
if self.is_empty():
print("Queue is empty")
return None
return self.queue[self.front]
def rear(self):
if self.is_empty():
print("Queue is empty")
return None
return self.queue[self.rear]
# 사용 예제
cq = CircularQueue(3) # 크기가 3인 환형 큐를 생성합니다.
# 큐에 데이터 삽입
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
# 큐가 가득 찬 상태 확인
print(cq.is_full()) # 출력: True
# 큐에서 데이터 삭제
print(cq.dequeue()) # 출력: 1
# 큐에 데이터 삽입
cq.enqueue(4)
# 큐의 현재 상태 출력
print(cq.queue) # 출력: [4, 2, 3]
# 큐의 front와 rear 요소 확인
print("Front element:", cq.queue[cq.front]) # 출력: Front element: 2
print("Rear element:", cq.queue[cq.rear]) # 출력: Rear element: 4
- 배열 인덱스 처리 : 배열의 인덱스를 사용할 때 원형적으로 처리하여, 배열의 끝에 도달하면 다시 배열의 처음으로 돌아가는 방식을 취한다. 이는 원형큐의 장점으로, 공간의 효율성을 높이며 오버플로우 문제를 방지한다.
- 공간 활용 : 큐의 마지막 위치와 처음 위치가 연결되어 원형 구조를 이룬다. 원형큐에서는 데이터를 순환하기 때문에, 큐의 앞쪽이 비워져도 데이터를 추가할 수 있어 공간 활용이 효율적이다.
- 포인터 사용 : 원형큐는 front와 rear라는 두 개의 포인터를 사용하여 원형 배열을 관리한다. front는 데이터가 제거되는 위치를 가리키고, rear는 데이터가 추가되는 위치를 가리킨다.
- 우선순위 큐(Prioirty Queue): 각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐
데이터를 저장할 때 각각의 데이터에 우선순위를 부여하고, 우선순위가 높은 데이터가 낮은 데이터보다 먼저 처리되는 자료구조이다. 이는 일반적인 큐(queue)와 다르게 데이터가 들어온 순서가 아니라 우선순위가 높은 데이터가 먼저 나가는 특성을 가지고 있다.
우선순위 큐 구현
import heapq # heapq 모듈을 가져옵니다.
class PriorityQueue:
def __init__(self):
self.queue = [] # 빈 큐를 생성합니다.
self.index = 0 # 우선순위가 동일한 경우를 위한 인덱스를 초기화합니다.
def enqueue(self, item, priority):
# 우선순위가 높은 순으로 정렬하기 위해 음수 우선순위를 사용합니다.
heapq.heappush(self.queue, (-priority, self.index, item))
self.index += 1 # 인덱스를 증가시킵니다.
def dequeue(self):
if not self.is_empty():
return heapq.heappop(self.queue)[-1] # 가장 높은 우선순위의 항목을 제거하고 반환합니다.
else:
return "Priority Queue is empty"
def is_empty(self):
return len(self.queue) == 0 # 큐가 비어 있는지 확인합니다.
# 사용 예제
pq = PriorityQueue() # 우선순위 큐를 생성합니다.
pq.enqueue("task1", 1) # 우선순위가 1인 작업을 추가합니다.
pq.enqueue("task2", 2) # 우선순위가 2인 작업을 추가합니다.
print(pq.dequeue()) # 우선순위가 가장 높은 작업을 제거하고 반환합니다.
print(pq.dequeue()) # 다음 우선순위가 높은 작업을 제거하고 반환합니다.
print(pq.dequeue()) # 큐가 비어 있음을 반환합니다.
- 데큐(Dequeue) : 양쪽에서 삽입, 삭제가 가능한 구조
Deque는 덱의 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐이다.
일반적인 큐와 달리 양쪽 끝에서 데이터를 삽입하고 삭제할 수 있어 더 유연한 데이터 구조를 제공한다.
- 삽입 연산
- append() : Deque의 뒤쪽에 요소를 추가
- appendleft() : Deque의 앞쪽에 요소를 추가
from collections import deque # collections 모듈에서 deque 클래스를 가져옵니다.
d = deque() # 빈 deque를 생성합니다.
# 뒤쪽에서 삽입(append)
d.append(1) # Deque의 뒤쪽에 1을 추가합니다.
d.append(2) # Deque의 뒤쪽에 2를 추가합니다.
print(d) # 출력: deque([1, 2])
# 앞쪽에서 삽입(appendleft)
d.appendleft(3) # Deque의 앞쪽에 3을 추가합니다.
print(d) # 출력: deque([3, 1, 2])
- 삭제 연산
- pop() : Deque의 뒤쪽에 요소를 제거하고 반환
- popleft() : Deque 앞쪽에 요소를 제거하고 반환
# 뒤쪽에서 삭제(pop)
last_element = d.pop() # Deque의 뒤쪽에서 요소를 제거하고 반환합니다.
print(last_element) # 출력: 2
print(d) # 출력: deque([3, 1])
# 앞쪽에서 삭제(popleft)
first_element = d.popleft() # Deque의 앞쪽에서 요소를 제거하고 반환합니다.
print(first_element) # 출력: 3
print(d) # 출력: deque([1])
KHU I.E 23