큐 알아보기
큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조이다.
큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.
또 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 한다.
배열로 큐 구현하기
스택과 마찬가지로 큐 또한 배열을 사용하여 구현할 수 있다.
아래 그림은 배열의 맨 앞부터 순서대로 4개의 데이터 19, 22, 37, 53이 들어있다.
배열 이름을 que라고 할 때 que[0] ~ que[3]까지 int형 데이터가 저장된다.(인덱스 0인 원소가 큐의 첫 번째 원소이다.)
이 상태에서 데이터 24를 인큐하고 19를 디큐하는 과정을 알아보자.
24를 인큐하기
맨 끝 데이터가 저장되어 있는 que[3]의 다음 원소인 que[4]에 24를 저장한다. 이때 처리의 복잡도는 O(1)이고 비교적 적은 비용으로 구현할 수 있다.
19를 디큐하기
que[0]에 저장되어 있는 19를 꺼내면서 2번째 이후의 모든 원소를 앞쪽으로 옮겨야 한다.
이 때 처리의 복잡도는 O(n)이다. 데이터를 꺼낼 때마다 이런 처리를 수행해야 한다면 프로그램의 효율성을 기대할 수 없다.
링 버퍼로 큐 구현하기
디큐할 때 배열 안의 원소를 옮기지 않는 큐를 구현하게 되는 경우 사용하는 자료구조는 링 버퍼이다.
링 버퍼는 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다.
어떤 원소가 맨 앞 원소이고, 어떤 원소가 맨 끝 원소인지 식별하는 변수가 각각 front와 rear이다.
여기에서 프런트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아니다.
인큐와 디큐를 수행하면 front와 rear의 값은 변한다.
아래 과정을 통해 두 값이 변하는 과정을 알아보자.
4개의 데이터 68, 95, 21, 73이 늘어선 순서대로 que[5], que[6], que[7], que[0]에 저장된다.
front 값은 5이고 rear 값은 1이다.
아래는 82를 인큐한 다음의 상태이다.
맨 끝의 다음에 위치한 que[rear], 즉 que[1]에 82를 저장하고 rear값을 1 증가시켜 2로 만든다.
아래는 68을 디큐한 다음의 상태이다.
맨 앞 원소인 que[front], 즉 que[5]의 값인 68을 꺼내고 front 값을 1 증가시켜 6으로 만든다.
링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐를 수행할 수 있다.
이로써 모든 처리의 복잡도는 O(1)이다.
링 버퍼를 사용한 큐를 구현하는 프로그램
# 고정 길이 큐 클래스 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를 반환한다.
데이터를 넣는 enque( ) 함수
enque( ) 함수는 큐에 데이터를 인큐한다. 하지만 큐가 가득 차서 인큐할 수 없는 경우 예외 처리인 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
위 그림 중 좌측 그림은 맨 앞부터 순서대로 95, 21, 73, 82를 넣은 큐에 47을 인큐하는 모습이다.
que[rear]인 que[2]에 인큐하는 데이터를 저장하고 rear와 no의 값을 1 증가시키면 인큐가 완료된다.
그런데 우측 그림과 같이 인큐를 하기 전의 rear 값이 배열의 맨 끝에서는 rear값을 1 증가시키면 capacity의 값과 똑같이 되어 배열 인덱스의 한계를 넘어간다. 이런 경우 인큐의 모습을 보여준다.
rear에 1을 증가시킨 뒤 rear값이 큐의 크기인 capacity와 같을 경우 rear를 배열의 맨 앞 인덱스 0으로 되돌린다.
이렇게 하면 다음에 인큐하는 데이터가 que[0] 위치에 제대로 저장된다.
데이터를 꺼내는 deque( ) 함수
deque( ) 함수는 큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환한다. 그러나 큐가 비어 있어 디큐할 수 없는 경우 예외 처리인 FixedQueue.Empty를 내보낸다.
def enque(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
디큐를 수행하는 과정은 아래와 같다.
위 그림 중 좌측 그림은 맨 앞부터 순서대로 68, 95, 21, 73, 82를 넣은 큐에서 68을 디큐하는 모습이다.
큐의 맨 앞인 que[front], 즉 que[5]에 저장된 값 68을 꺼내고 front를 1 증가, no를 1 감소시킨다.
그런데 우측 그림과 같이 디큐하기 전에 front가 배열의 맨 끝인 경우 front를 1 증가시키면 그 값이 capacity와 같아져서 배열 인덱스의 한계를 넘어간다. 그럴 땐 front의 값이 큐의 크기인 capacity와 같을 경우 front를 1 증가시켜 배열의 맨 앞 인덱스인 0으로 되돌린다.
이렇게 하면 다음 디큐를 수행할 때 데이터를 que[0] 위치에서 제대로 꺼낼 수 있다.
데이터를 들여다보는 peek( ) 함수
peek( ) 함수는 맨 앞 데이터, 즉 다음 디큐에서 꺼낼 데이터를 들여다본다.
que[front]의 값을 반환할 뿐 데이터를 꺼내지는 않으므로 front, rear, no의 값은 변하지 않는다.
큐가 비어 있을 때는 예외 처리 FixedQueue.Empty를 내보낸다.
검색하는 find( ) 함수
find( ) 함수는 큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아낸다.
맨 앞에서 맨 끝쪽으로 선형 검색을 수행한다.
물론 스캔은 아래 그림처럼 배열의 맨 앞 원소가 아니라 큐의 맨 앞 원소(front)부터 시작한다.
따라서 스캔할 때 주목하는 인덱스 idx를 구하는 식은 (i + front) % capacity이다.
다음과 같이 i와 idx의 값이 변한다.
| i | 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 |
| idx | 5 → 6 → 7 → 0 → 1 → 2 → 3 → 4 |
검색에 성공하면 찾은 원소의 인덱스를 반환하고 실패하면 -1을 반환한다.
데이터 개수를 세는 count( ) 함수
count( ) 함수는 큐에 있는 데이터(value)의 개수를 구하여 반환한다.
데이터가 포함되어 있는지를 판단하는 __contains__( ) 함수
__contains__( ) 함수는 큐에 데이터(value)가 들어 있는지를 판단한다. 들어 있으면 True를, 그렇지 않으면 False를 반환한다.
내부의 count( ) 함수를 호출하여 구현한다.
큐의 전체 원소를 삭제하는 clear( ) 함수
clear( ) 함수는 현재 큐에 들어 있는 모든 데이터를 삭제한다.
인큐와 디큐는 no, front, rear의 값을 바탕으로 수행된다. 그러므로 값을 0으로만 하면 된다.(실제 큐 배열 que의 원솟값을 변경할 필요가 없다.)
큐의 전체 데이터를 출력하는 dump( ) 함수
dump( ) 함수는 큐에 들어 있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 순서대로 출력한다.
하지만 큐가 비어 있으면 '큐가 비어 있습니다.'를 출력한다.
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()
큐 FixedQueue 클래스를 실제 사용하는 프로그램(fixed_queue.test.py)
# 고정 길이 큐 클래스(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
1 2 3 1 5
현재 데이터 개수: 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)종료: 2
디큐한 데이터는 3입니다.
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 5
1 5
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 6
Process finished with exit code 0
링 버퍼의 활용
링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있다.
예를 들면 원소 수가 n인 배열에 데이터를 계속해서 입력할 때 가장 최근에 들어온 데이터 n개만 저장하고 나머지 오래된 데이터는 버리는 경우이다.
아래 코드는 리스트형 배열 a의 원소 수는 총 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
실행 결과(n이 10일 때 12개의 정수를 입력받으면 마지막에 입력받은 정수 10개만 남게된다.)
정수를 몇 개 저장할까요?: 10
1번째 정수를 입력하세요.: 15
계속 할까요?(Y ... Yes / N ... No): y
2번째 정수를 입력하세요.: 17
계속 할까요?(Y ... Yes / N ... No): y
3번째 정수를 입력하세요.: 64
계속 할까요?(Y ... Yes / N ... No): y
4번째 정수를 입력하세요.: 57
계속 할까요?(Y ... Yes / N ... No): y
5번째 정수를 입력하세요.: 99
계속 할까요?(Y ... Yes / N ... No): y
6번째 정수를 입력하세요.: 21
계속 할까요?(Y ... Yes / N ... No): y
7번째 정수를 입력하세요.: 0
계속 할까요?(Y ... Yes / N ... No): y
8번째 정수를 입력하세요.: 23
계속 할까요?(Y ... Yes / N ... No): y
9번째 정수를 입력하세요.: 44
계속 할까요?(Y ... Yes / N ... No): y
10번째 정수를 입력하세요.: 55
계속 할까요?(Y ... Yes / N ... No): y
11번째 정수를 입력하세요.: 97
계속 할까요?(Y ... Yes / N ... No): y
12번째 정수를 입력하세요.: 85
계속 할까요?(Y ... Yes / N ... No): n
3번째 = 64
4번째 = 57
5번째 = 99
6번째 = 21
7번째 = 0
8번째 = 23
9번째 = 44
10번째 = 55
11번째 = 97
12번째 = 85
Process finished with exit code 0
위에서 입력받은 값을 배열 원소에 저장하는 과정은 아래와 같다.
1번째 값 입력받기
cnt 값은 0이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[0]에 저장한다.
2번째 값 입력받기
cnt 값은 0이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[1]에 저장한다.
(...생략...)
10번째 값 입력받기
cnt 값은 9이고, 이것을 10으로 나눈 나머지는 9이다. 입력받은 값을 a[9]에 저장한다.
11번째 값 입력받기
cnt 값은 10이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[0]에 저장한다.
a[0]에 이미 1번째 값이 있지만 11번째 값이 덮어쓴다.
12번째 값 입력받기
cnt 값은 11이고, 이것을 10으로 나눈 나머지는 1이다. 입력받은 값을 a[1]에 저장한다.
a[1]에 이미 2번째 값이 있지만 12번째 값이 덮어쓴다.
입력받은 값을 저장하는 곳의 인덱스를 cnt % n으로 구하고, 그 뒤 cnt 값을 1 증가시켜 링 버퍼(배열)의 모든 원소를 순환하면서 저장하게 된다.