큐와 우선순위 큐(Queue and Priority Queue)
큐란, 스택과 동일하게 Data를 임시 저장할 때 사용하는 자료구조지만, 스택과는 다르게 선입선출(FIFO) 방식이다. 데이터를 넣을땐 인큐(Enqueue), 데이터를 꺼낼땐 디큐(Dequeue) 이라 한다.
큐의 특징을 아래 정리해봤다.
- 데이터를 꺼내는 쪽을 프론트(front), 데이터를 넣는 쪽을 리어(rear)라 함
- 인덱스가 0인 곳이 프론트이다
- 인큐시 처리의 복잡도는 O(1)으로 비용이 적은반면, 디큐같은 경우 2번째 이후의 원소를 앞쪽으로 옮겨야 하기 때문에 복잡도가 O(n)으로 나옴
위 큐의 특징 3번의 단점을 해결하고자 나온 방법으로 링 버퍼(Ring Buffer) 자료구조가 있다
- 링 버퍼는 논리적인 데이터 순서일 뿐, 배열의 물리적 원소의 순서는 아님
- front 와 rear(맨 끝 원소 바로 뒤의 인덱스)로 원소의 앞과 끝을 식별함
- 인큐와 디큐시 front와 rear의 값은 변함
그러면 큐 클래스를 알아보자
큐의 Empty와 Full
예제 : 큐가 비어 있는지 확인해보자
def is_empty(self) -> bool:
"""큐가 비어 있는지 판단"""
return self.no == 0
이렇게 사용해도 되지만, 프로그램 오류로 인해 값이 0보다 작아질 수 있어서 아래처럼 작성하면 오류를 최소화 할수 있다
return self.no <= 0
예제 : 큐가가 가득 차 있는지 확인해보자
def is_full(self) -> bool:
"""큐가 가득 찼는지 판단"""
return self.no == self.capacity
이것도 마찬가지로 오류를 방지하기 위해 아래처럼 부등호를 사용하자
return self.no >= self.capacity
스택과 동일하게 큐에서도 예외 처리를 진행한다. 예외 처리에 대해 다시 설명하자면, 예외 처리를 하면 실행되다가 중단되는것을 방지할 수 있다. 그리고 original code 에서 error가 발생했을때, 대처하는 코드를 분리할 수 있다는 장점이 있다.
예외 처리
예제 : Empty, deque()함수 또는 peek()함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리
class Empty(Exception):
"""비어 있는 FixedQueue에 대해 deque 또는 peek를 호출할 때 내보내는 예외처리"""
pass
예제 : Full, enque() 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리
class Full(Exception):
"""가득 찬 FixedQueue에 enque를 호출할 때 내보내는 예외처리"""
pass
이제부터는 큐큐에 사용되는 함수들을 나열하겠다.
큐(Queue) 함수
예제 : init() 함수, 큐 배열을 생성한다. 이때 queue의 no == 0
def __init__(self, capacity: int) -> None:
"""초기화 선언"""
self.no = 0 # 현재 데이터 개수, 처음에는 0이지만 가득 차게되면 capacity와 같아짐
self.front = 0 # 맨앞 원소 커서
self.rear = 0 # 맨끝 원소 커서, 여기서 왜 front와 같을지 의문이 들 수 있는데,
# 그 이유는 rear는 마지막 원소의 다음값이기 때문임
self.capacity = capacity # 큐의 크기
self.que = [None] * capacity # 큐의 본체
그렇다면, self.front = self.rear 이면 큐가 빈것일까? 답은 비거나 가득차거나 둘중 하나이다.
예제 : len() 함수, 큐의 쌓여있는 데이터 개수를 반환
def __len__(self) -> int:
"""큐에 있는 모든 데이터 개수를 반환"""
return self.no
예제 : enque() 함수, 큐의 rear에 데이터 추가. 가득차 있으면 FixedQueue.Full로 예외처리
def enque(self, x: Any) -> None:
"""데이터 x를 인큐"""
if self.is_full():
raise FixedQueue.Full # 큐가 가득 찬 경우 예외처리를 발생
self.que[self.rear] = x
self.rear += 1
self.no += 1
if self.rear == self.capacity: # 이부분 같은 경우 링버퍼에서 필수적인데, 링버퍼의 인덱스를 초과했을때
# 앞 인덱스로 값을 변경해주는 용도이다
self.rear = 0
예제 : deque() 함수, 큐의 front data 반환. 스택이 비었으면 FixedQueue.Empty로 예외처리
def deque(self) -> Any:
"""데이터를 디큐합니다"""
if self.is_empty():
raise FixedQueue.Empty # 큐가 비어 있는 경우 예외처리를 발생
x = self.que[self.front]
self.front += 1
self.no -= 1
if self.front == self.capacity: # 이부분 같은 경우 링버퍼에서 필수적인데, 링버퍼의 인덱스를 초과했을때
self.front = 0 # 앞 인덱스로 값을 변경해주는 용도이다
return x
예제 : peek() 함수, 큐의 front data 열람. 스택이 비었으면 FixedQueue.Empty로 예외처리
def peek(self) -> Any:
"""데이터를 피크합니다(맨 앞 데이터를 들여다 봄)"""
if self.is_empty():
raise FixedQueue.Empty # 큐가 비어 있으면 예외처리를 발생
return self.que[self.front]
예제 : clear() 함수, 큐의 모든 데이터를 삭제하여 빈 큐로 만듦
def clear(self) -> None:
"""큐의 모든 데이터를 비웁니다"""
self.no = self.front = self.rear = 0
예제 : find() 함수, 큐에서 데이터를 찾으면 원소의 인덱스를 반환. 실패하면 -1 반환. 만약 중복되는 숫자가 있으면 front에 가까운 원소의 인덱스를 반환한다.
def find(self, value: Any) -> Any:
"""큐에서 value를 찾아 인덱스를 반환하고 없으면 -1을 반환합니다"""
for i in range(self.no):
idx = (i + self.front) % self.capacity #self.capacity를 왜 나누냐 링 버퍼의 특성상 인덱스 값을
if self.que[idx] == value: # 검색 성공 #넘어버렸을때 앞으로 보내주기 위함이다.
return idx
return -1 # 검색 실패
예제 : count() 함수, 큐에서 특정 data의 개수를 반환. front쪽부터 센다.
def count(self, value: Any) -> bool:
"""큐에 포함되어 있는 value의 개수를 반환합니다"""
c = 0
for i in range(self.no): # 큐 데이터를 선형 검색
idx = (i + self.front) % self.capacity
if self.que[idx] == value: # 검색 성공
c += 1 # 들어있음
return c
예제 : contains() 함수, value가 들어 있는지를 판단
def __contains__(self, value: Any) -> bool:
"""스택에 value가 있는가?"""
return self.count(value)
예제 : dump() 함수, 큐에 쌓여 있는 데이터를 front부터 rear까지 순차적으로 출력함.
def dump(self) -> None:
"""모든 데이터를 맨 앞에서 맨 끝 순서로 출력합니다"""
if self.is_empty(): # 큐가 비어 있으면 예외처리를 발생
print('큐가 비어 있습니다.')
else:
for i in range(self.no):
print(self.que[(i + self.front) % self.capacity], end=' ')
print()
마지막 : FixedStack 같은 경우 아래 예시처럼 최대 64개까지를 저장하는 Queue을 만들고 싶다면, 아래처럼 명령어를 사용하면 된다
from fixed_queue import FixedQueue
q = FixedQueue(64)
이렇게 큐의 함수들을 알아보았다. 함수가 어떻게 구성되어 있는지 알아야 추후 사용할때 효율적으로 사용할 수 있을것이다.
