728x90
04-2 큐란?
큐 알아보기
- 큐(queue): 스택과 같이 데이터를 임시 저장하는 자료구조
- 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조입니다.
- 큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue)라고 합니다.
- 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 합니다.
배열로 큐 구현하기
- 24를 인큐하기
: 맨 끝 데이터가 저장되어 있는 que[3]의 다음 원소인 que[4]에 24를 저장합니다. 이때 처리의 복잡도는 O(1)이고 비교적 적은 비용으로 구현할 수 있습니다. - 19를 디큐하기
: que[0]에 저장되어 있는 19를 꺼내면서 2번째 이후의 모든 원소를 위 그림의 c와 같이 앞쪽으로 옮겨야 합니다. 이때 처리의 복잡도는 O(n)입니다.
우선순위 큐(priority queue)
- 우선순위 큐: 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식
- 파이썬에서 우선순위를 부여하는 큐는 heapq 모듈에서 제공
- heap에서 data의 인큐는 heapq.heappust(heap, data)로 수행
- 디큐는 headpq.heappop(heap)으로 수행
링 버퍼(ring buffer)로 큐 구현하기
- 링 버퍼(ring buffer): 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조
- 어떤 원소가 맨 앞 원소이고, 어떤 원소가 맨 끝 원소인지 식별하는 변수가 각각 front와 rear입니다.
- 프런트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아닙니다.
인큐와 디큐 수행 시 front와 rear의 값이 변하는 과정
- 7개의 데이터 35, 56, 24, 68, 95, 73, 19가 늘어선 순서대로 que[7], que[8], ···, que[11], que[0], que[1]에 저장됩니다. front 값은 7이고 rear 값은 2입니다.
- 1에서 82를 인큐한 다음의 상태입니다. 맨 끝의 다음에 위치한 que[rear], 즉 que[2]에 82를 저장하고 rear값을 1 증가시켜 3으로 만듭니다.
- 2에서 35를 디큐한 다음의 상태입니다. 맨 앞 원소인 que[front] 즉, que[7]의 값인 35를 꺼내고 front값을 1 증가시켜 8로 만듭니다.
위 그림과 같이 링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐를 구현할 수 있습니다. 모든 처리의 복잡도는 O(1)입니다.
실습 4-3 고정 길이 큐 클래스 FixedQueue 구현하기
# 고정 길이 큐 클래스 FixedQueue 구현하기
from typing import Any
class FixedQueue:
class Empty(Exception):
"""비어 있는 FixedQueue에서 디큐 또는 피크할 때 내보내는 예외 처리"""
pass
class Full(Exception):
"""가득 차 있는 FixedQueue에서 인큐할 때 내보내는 예외 처리"""
pass
def __init__(self, capacity: int) -> None:
"""큐 초기화"""
self.no = 0 # 현재 데이터 개수
self.front = 0 # 맨 앞 원소 커서
self.rear = 0 # 맨 끝 원소 커서
self.capacity = capacity # 큐의 크기
self.que = [None] * capacity # 큐의 본체
def __len__(self) -> int:
"""큐에 있는 모든 데이터 개수를 반환"""
return self.no
def is_empty(self) -> bool:
"""큐가 비어 있는지 판단"""
return self.no <= 0
def is_full(self) -> bool:
"""큐가 가득 차 있는지 판단"""
return self.no >= self.capacity- 예외 처리 클래스 Empty와 Full
: 비어 있는 큐에 deque(), peek() 함수를 호출할 때 내보내는 예외 처리는 Empty 클래스이고, 가득 차 있는 큐에 enque() 함수를 호출할 때 내보내는 예외처리는 Full 클래스입니다. - 초기화하는 __init__() 함수
: __init__() 함수는 큐 배열을 생성하는 등의 준비 작업을 하며 다음과 같이 5개의 변수에 값을 설정합니다.- que: 큐의 배열로서 밀어 넣는 데이터를 저장하는 list형 배열입니다.
- capacity: 큐의 최대 크기를 나타내는 int형 정수입니다. 이 값은 배열 que의 원소 수와 일치합니다.
- front, rear: 맨 앞의 원소, 맨 끝의 원소를 나타내는 인덱스입니다. 큐에 넣은 데이터 중에 가장 처음에 넣은 맨 앞 원소의 인덱스가 front이고, 가장 마지막에 넣은 맨 끝의 원소의 바로 다음 인덱스가 rear입니다. rear는 다음에 인큐할 때 데이터를 저장하는 원소의 인덱스입니다.
- no: 큐에 쌓여 있는 데이터 개수를 나타내는 int형 정수입니다. 변수 front와 rear의 값이 같을 경우 큐가 비어 있는지 또는 가득 차 있는지 구별하기 위해 필요합니다. 큐가 비어 있는 경우에는 no가 0이 되고, 가득 차 있는 경우에는 capacity와 같은 값이 됩니다.
- 추가한 데이터 개수를 알아내는 __len__() 함수
: __len__() 함수는 큐에 추가한 데이터 개수를 반환합니다. no의 값은 그대로 반환합니다. - 큐가 비어 있는지를 판단하는 is_empty() 함수
: is empty() 함수는 큐가 비어 있는지를 판단합니다. 비어 있으면 True를, 그렇지 않으면 False를 반환합니다. - 큐가 가득 차 있는지를 판단하는 is_full() 함수
: is_full() 함수는 큐가 가득 차 있어서 더 이상 데이터를 추가할 수 없는 상태인지 검사합니다. 가득 차 있으면 True를, 그렇지 않으면 False를 반환합니다.
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
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- 데이터를 넣는 enque() 함수
: enque() 함수는 큐에 데이터를 인큐합니다. 하지만 큐가 가득 차서 인큐할 수 없는 경우 예외 처리인 FixedQueue.Full을 내보냅니다. - 데이터를 꺼내는 deque() 함수
: deque() 함수는 큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환합니다. 그러나 큐가 비어 있어 디큐할 수 없는 경우 예외 처리인 FixedQueue.Empty를 내보냅니다.
def peek(self) -> Any:
"""큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)"""
if self.is_empty():
raise FixedQueue.Empty
return self.que[self.front]
def find(self, value: Any) -> Any:
"""큐에서 value를 찾아 인덱스를 반환(없으면 -1을 반환)"""
for i in range(self.no):
idx = (i + self.front) % self.capacity
if self.que[idx] == value: # 검색 성공
return idx
return -1 # 검색 실패
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
def __contains__(self, value: Any) -> bool:
"""큐에 value가 있는지 판단"""
return self.count(value)
def clear(self) -> None:
"""큐의 모든 데이터를 비움"""
self.no = self.front = self.rear = 0
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()- 데이터를 들여다보는 peek() 함수
: peek() 함수는 맨 앞 데이터, 즉 다음 디큐에서 꺼낼 데이터를 들여다봅니다. que[front]의 값을 반환할 뿐 데이터를 꺼내지는 않으므로 front, rear, no의 값은 변하지 않습니다. 큐가 비어 있을 때는 예외 처리 Fixed Queue.Empty를 내보냅니다. - 검색하는 find() 함수
: find() 함수는 큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아냅니다. 맨 앞에서 맨 끝쪽으로 선형 검색을 수행합니다. 물론 스캔은 배열의 맨 앞 원소가 아니라 큐의 맨 앞 원소(front)부터 시작합니다. 따라서 스캔할 때 주목하는 인덱스 idx를 구하는 식은 (i + front) % capacity입니다. 검색에 성공하면 찾은 원소의 인덱스를 반환하고 실패하면 -1을 반환합니다. - 데이터 개수를 세는 count() 함수
: count() 함수는 큐에 있는 데이터(value)의 개수를 구하여 반환합니다. - 데이터가 포함되어 있는지를 판단하는 __contains__() 함수
: __contains__() 함수는 큐에 데이터(value)가 들어 있는지를 판단합니다. 들어 있으면 True를, 그렇지 않으면 False를 반환합니다. 내부의 count() 함수를 호출하여 구현합니다. - 큐의 전체 원소를 삭제하는 clear() 함수
: clear() 함수는 현재 큐에 들어 있는 모든 데이터를 삭제합니다. - 큐의 전체 데이터를 출력하는 dump() 함수
: dump() 함수는 큐에 들어 있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 순서대로 출력합니다. 하지만 큐가 비어 있으면 '큐가 비어 있습니다.'를 출력합니다.
링 버퍼로 큐 프로그램 만들기
실습 4-4 고정 길이 큐 클래스(FixedQueue)를 사용하기
# 고정 길이 큐 클래스(FixedQueue)를 사용하기
from enum import Enum
from fixed_queue import FixedQueue
Menu = Enum('Menu', ['인큐','디큐','피크','검색','덤프','종료'])
def select_menu() -> Menu:
"""메뉴 선택"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep = ' ', end='')
n = int(input(': '))
if 1 <= n <= len(Menu):
return Menu(n)
q = FixedQueue(64) # 최대 64개를 인큐할 수 있는 큐
while True:
print(f'현재 데이터 개수: {len(q)} / {q.capacity}')
menu = select_menu() # 메뉴 선택
if menu == Menu.인큐: # 인큐
x = int(input('인큐할 데이터를 입력하세요.: '))
try:
q.enque(x)
except FixedQueue.Full:
print('큐가 가득 찼습니다.')
elif menu == Menu.디큐: # 디큐
try:
x = q.deque()
print(f'디큐한 데이터는 {x}입니다.')
except FixedQueue.Empty:
print('큐가 비어 있습니다.')
elif menu == Menu.피크: # 피크
try:
x = q.peek()
print(f'피크한 데이터는 {x}입니다.')
except FixedQueue.Empty:
print('큐가 비어 있습니다.')
elif menu == Menu.검색: # 검색
x = int(input('검색할 값을 입력하세요.: '))
if x in q:
print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다.')
else:
print('검색값을 찾을 수 없습니다.')
elif menu == Menu.덤프: # 덤프
q.dump()
else:
break현재 데이터 개수: 0 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요.: 1
현재 데이터 개수: 1 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요.: 2
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요.: 3
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요.: 1
현재 데이터 개수: 4 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요.: 5
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 5
12315
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 4
검색할 값을 입력하세요.: 1
2개 포함되고, 맨 앞의 위치는 0입니다.
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 3
피크한 데이터는 1입니다.
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 2
디큐한 데이터는 1입니다.
현재 데이터 개수: 4 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 2
디큐한 데이터는 2입니다.
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 5
315
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 6링 버퍼의 활용
링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있습니다. 예를 들면 원소 수가 n인 배열에 데이터를 계속해서 입력할 때 가장 최근에 들어온 데이터 n개만 저장하고 나머지 오래된 데이터는 버리는 경우입니다.
실습 4C-2 원하는 개수(n)만큼 값을 입력받아 마지막 n개를 저장
# 원하는 개수(n)만큼 값을 입력받아 마지막 n개를 저장
n = int(input('정수를 몇 개 저장할까요?: '))
a = [None] * n # 입력받은 값을 저장하는 배열
cnt = 0 # 정수를 입력받은 개수
while True:
a[cnt % n] = int(input((f'{cnt + 1}번째 정수를 입력하세요.: ')))
cnt += 1
retry = input(f'계속 할까요?(Y … Yes / N … No): ')
if retry in {'N','n'}: # N이나 n을 입력하면 더 이상 값을 받지 않음
break
i = cnt - n
if i < 0: i = 0
while i < cnt:
print(f'{i +1}번째 = {a[i % n]}')
i += 1정수를 몇 개 저장할까요?: 10
1번째 정수를 입력하세요.: 15
계속 할까요?(Y … Yes / N … No): 17
2번째 정수를 입력하세요.: 19
계속 할까요?(Y … Yes / N … No): 21
3번째 정수를 입력하세요.: 23
계속 할까요?(Y … Yes / N … No): 25
4번째 정수를 입력하세요.: 59
계속 할까요?(Y … Yes / N … No): 55
5번째 정수를 입력하세요.: 84
계속 할까요?(Y … Yes / N … No): 30
6번째 정수를 입력하세요.: 53
계속 할까요?(Y … Yes / N … No): 20
7번째 정수를 입력하세요.: 49
계속 할까요?(Y … Yes / N … No): 38
8번째 정수를 입력하세요.: 29
계속 할까요?(Y … Yes / N … No): n
1번째 = 15
2번째 = 19
3번째 = 23
4번째 = 59
5번째 = 84
6번째 = 53
7번째 = 49
8번째 = 29
- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file: https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%8A%A4%ED%83%9D%EA%B3%BC%20%ED%81%90.ipynb
GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습
파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습. Contribute to heejvely/Algorithm development by creating an account on GitHub.
github.com
728x90
'Code > Algorithm' 카테고리의 다른 글
| [Algorithm] 재귀 알고리즘_2 (0) | 2022.12.09 |
|---|---|
| [Algorithm] 재귀 알고리즘_1 (2) | 2022.12.06 |
| [Algorithm] 스택과 큐_1 (0) | 2022.12.02 |
| [Algorithm] 검색 알고리즘_4 (해시법) (0) | 2022.11.28 |
| [Algorithm] 검색 알고리즘_3 (이진 검색) (2) | 2022.11.28 |