출처: Do it! 자료구조와 함께 배우는 알고리즘 입문- 파이썬편
큐는 스택과 같이 데이터를 임시 저장하는 자료구조이지만, 스택처럼 가장 나중에 넣은 데이터를 가장 먼저 꺼내지 않는다. 선입선출(가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조)이다.
인큐(enqueue) : 큐에 데이터 추가
디큐(dequeue): 데이터를 꺼냄
프런트(front): 데이터를 꺼내는 쪽
리어(rear): 데이터를 넣는 쪽
링 버퍼로 큐 구현하기
링 버퍼 ring buffer는 디큐할 때 배열의 원소를 옮기지 않는 큐이다.
front 값은 5, rear 값은 2이다.
여기서 82를 인큐하면 맨끝의 다음에 위치한 que[rear]= que[2]에 82를 저장하고 rear 값을 2에서 3으로 움직인다.
24를 디큐 하면 맨 앞 원소인 que[5]인 값 24 값을 꺼내고 front 값을 1증가시켜 6으로 만든다.
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.capacityEmpty: 비어있는 큐에 deque(), peek() 함수를 호출할 때 내보내는 예외처리 클래스
Full: 가득차 있는 큐에 enque() 함수를 호출할 때 내보내는 예외 처리 클래스
__init__: 초기화 함수
- que: 큐의 배열로서 밀어넣는 데이터를 저장하는 list 배열
- capacity: 큐의 최대크기를 나타내는 int형 정수, 배열 que의 원소수와 일치
- front, rear: 맨앞, 맨 끝 원소를 나태는 인덱스, 가장 처음에 넣은 것(맨 앞 원소) -> front, 가장 나중에 넣은것(맨 뒤 원소의 다음 인덱스)-> rear
- no: 큐에 쌓여있는 데이터 갯수를 나타내는 int형 정수, 비어있으면 0, 가득차 있으면 capacity와 같은 값이다.
__len__: 추가한 데이터 개수 반환, no값 그대로 반환
is_empty(): 큐가 비어있는지 판단, 비어 있으면 True, 아니면 False 반환
is_full() 큐가 가득차 있는지 판단, 가득차 있으면 True, 아니면 False
enque()
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=0a) 82를 인큐할때 -> que[rear]인 que[2]에 인큐하는 데이터를 저장하고 rear과 no의 값을 1 증가시킨다.
b) 17를 인큐-> 인큐를 하기전 rear 값이 배열의 맨끝인 경우에는 rear를 1증가시키면 capacity값을 넘어선다.
rear에 1을 증가시킨 뒤 rear값이 큐의 capacity 크기와 같은 경우, rear을 맨 앞 인덱스 0으로 되돌린다.
deque()
def deque(self,x:Any)->None:
#데이터를 디큐
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
a) 14를 디큐했을때 -> 인덱스 5에 위치한 14를 빼면 front 1증가, no는 1 감소
b)17을 디큐-> 디큐하기전에 front가 배열의 맨끝인 경우, front를 1증가 시키면 그 값이 capacity와 같아져서 배열 인덱스를 넘는다. 이럴 경우 front를 1 증가시키기고 front값을 0으로 되돌린다.
peek() 함수
def peek(self)-> Any:
#큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)
if self.is_empty():
raise FixedQueue.Empty #큐가 비어있는 경우 예외 처리 발생
return self.que[self.front]peek는 다음 디큐에서 꺼낼 데이터를 들여다봄. que[front] 값을 반환할 뿐 데이터를 꺼내지는 않음. 비어있을 때는 FixedQueue.Empty를 내보냄
find()함수
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 #검색 실패큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아냄. 스캔은 큐의 맨 앞 원소(front)부터 시작함. 스캔할 때 주목하는 인덱스 idx를 구하는 식은(i+front) % capacity로 구한다.
여기서 capacity는 8, front는 5이므로 (i+5)/8 한값의 나머지를 구하면, 다음과 같이 idx값이 나온다.
| i | 0 | 1 | 2 | 3 | 4 |
| idx | 5 | 6 | 7 | 0 | 1 |
검색에 성공하면 찾은 원소의 인덱스를 반환하고, 실패하면 -1을 반환한다.
count() 함수
큐에있는 데이터(value)의 갯수를 구하여 반환
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)가 있는지 판단한다. 들어있으면 True, 없으면 False를 반환한다. 내부의 count() 함수를 호출한다.
def __contains__(self,value:Any)-> bool:
#큐에 value가 있는지 판단
return self.count(value)
clear() 함수
큐에 들어있는 모든 데이터 삭제
def clear(self)-> None:
#큐의 모든 데이터를 비움
self.no = self.front=self.rear=0
dump() 함수
큐에 들어있는 모든 데이터를 맨 앞부터 맨 끝쪽으로 순서대로 출력, 큐가 비어있으면 '큐가 비어있습니다' 출력
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()
양방향 대기열 덱(deque)
맨 앞과 맨 끝 양쪽에서 데이터를 넣고 꺼낼 수 있는 자료구조이다.
파이썬에서는 collections.deque 컨테이너로 제공된다.
맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입, 삭제할 수 있는 자료구조로, 2개의 포인터를 사용하여 양쪽에서 삽입, 삭제가 가능하며 큐와 스택을 합친 형태이다.
링 버퍼의 활용
만약 데이터를 12개를 받고, 배열에는 최근에 입력한 10개만 남을수 있게 하는 코드, 노란색 부분 버림:
ex) 14, 13, 12, 15 13, 32, 46, 65, 32,23, 55, 30
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
