- [자료구조&알고리즘 | WEEK02] 큐(Queue) 자료구조 정리(원형 큐 | 링 버퍼)2022년 11월 05일 22시 09분 08초에 업로드 된 글입니다.작성자: nickhealthy
큐(Queue)는 스택과 같이 데이터를 임시 저장하는 자료구조이다.
하지만 스택과는 다르게 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.용도
어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용한다.
서로 다른 쓰레드 사이 또는 프로세스 사이에서나 네트워크를 통해 자료를 주고받을 때 자료를 일시적으로 저장하는 용도로 많이 사용한다.스택 용어 정리
- 인큐(enqueue): 큐에 데이터를 추가하는 작업
- 디큐(dequeue): 데이터를 꺼내는 작업
- 프론트(front): 데이터를 꺼내는 쪽(가장 앞에 있는 원소)
- 리어(rear): 데이터를 넣는 쪽(가장 뒤에 있는 원소)
큐(Queue)의 자료구조 스택과 마찬가지로 큐 또한 배열을 사용하여 구현이 가능하다.
참고로 인큐는 밀어 넣기라고도 표현한다.
디큐(dequeue)는 양방향 대기열 자료구조인 덱(deque)와 혼동하지 말아야 한다.
Queue(큐)와 deque(덱)와다른 자료구조이다. - 하단 이미지 참고
양방향 대기열 자료구조인 덱(deque) 시간 복잡도
- 인큐(enqueue) - O(1)
- 큐에 데이터를 추가하는 작업은 rear(데이터를 넣는 쪽)에 한번 발생하므로 O(1)의 처리 복잡도 시간을 가지게 된다.
- 디큐(dequeue) - O(1)
- 큐에 데이터를 추출하는 작업은 front(데이터를 꺼내는 쪽)에 한번 발생하므로 O(1)의 처리 복잡도 시간을 가지게 된다.
- 디큐 이후 데이터 재배치 및 검색 - O(n)
- 데이터를 front에서 꺼낸 이후, 뒤에 있는 데이터를 앞으로 재배치해주는 작업이 필요하다. 그러므로 O(n)만큼의 시간을 가지게 된다. 검색도 일반적으로 모든 원소를 탐색해야 하기때문에 마찮가지
큐의 인큐, 디큐, 시간 복잡도 우선순위 큐(priority queue)
우선순위 큐는 평범한 큐나 스택과 비슷한 축약 자료형이다. 그러나 각 원소들은 우선순위를 갖고 있다. 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 우선순위 큐는 리스트 또는 힙(heap)이라는 자료구조를 통해서 구현이 가능하다. 리스트 또는 힙을 이용해 우선순위 큐를 구현하면 시간복잡도는 아래와 같다.
우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(lonN) O(logN) 힙 정렬은 N개의 데이터를 넣고, 데이터를 넣을 때마다 정렬O(logN)을 모두 해야하므로 O(NlogN)의 시간복잡도를 가지게 된다.
우선순위 큐는 최소한 다음의 연산이 지원 되어야 한다.
- insert_with_priority: 하나의 원소에 대해 우선순위를 지정하여 큐에 추가한다.
- pull_highest_priority_element: 가장 높은 우선순위를 가진 원소를 큐에서 제거하고 이를 반환한다.
따라서 인큐할 때는 데이터에 우선순위를 부여하여 추가하고, 디큐할 땐 우선순위가 가장 높은 데이터를 꺼내는 방식이다. 파이썬에서 우선순위를 부여하는 큐는
heapq, queue모듈에서 제공한다.개인적으로 조금 더 명시적이라고 생각한 PriorityQueue 클래스를 이용했습니다.
PriorityQueue 클래스를 이용한 우선순위 큐 정렬 기준 변경
별다른 핸들링 없이는 단순히 오름차순만 구하게 되어있는데, 내림차순 및 다른 기준으로 원소가 정렬되기를 원한다면 아래와 같이 구현이 가능하다.
우선순위 큐 내림차순으로 정렬 원형 큐(링 버퍼 - ring buffer)
큐를 위해 배열을 지정해 놓고 디큐를 쓰다보면 배열의 앞부분이 비게 된다는 점을 활용해서 배열의 맨 마지막 부분을 쓰면 다시 제일 처음부터 다시 큐를 채우기 시작하는 형태의 큐이다. (디큐할 때 배열 안의 원소를 옮기지 않는 큐) 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일한 자료구조이다. 하지만 마지막 위치가 시작 위치와 연결되는 원형구조를 띄기 때문에, 링 버퍼(Ring Buffer)라고도 부른다.
기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수가 없었다. 심지어 앞쪽에 요소들이 디큐로 모두 빠져서 충분한 공간이 남아도 그쪽으로는 추가할 수 있는 방법이 없다. 그래서 앞쪽에 공간이 남아 있다면 위 그림과 같이 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐이다.
고정 길이의 원형큐(링버퍼)로 구현 전, 필요한 데이터 정의
원형 큐는 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조라고 위에서 설명했다.
이를 식별하는 변수가 front, rear이다. 또한 링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐 모두 실행가능하게 된다. 이때 모든 처리의 시간 복잡도는 O(1)이다.예외 처리 클래스 구현, Empty와 Full
- 비어 있는 큐에 deque(), peek() 함수를 호출할 때 내보내는 예외 처리 - Empty 클래스
- 가득 차 있는 큐에 enque() 함수를 호출할 때 내보내는 예외 처리 - Full 클래스
class 구현의 초기화 _init_ 함수
큐를 구현하기 위한 초기화 변수는 다음과 같이 5개의 변수가 필요하다.
파이썬에서는 스택과 큐의 자료구조를 모두 list로 구현 가능하다.- que: 큐의 배열로서 데이터를 저장하는 list형 배열
- capacity: 큐의 최대 크기를 나타내는 int형 정수, 이 값은 que의 배열 크기와 동일하다.
- front: 맨 앞의 원소를 나타내는 인덱스(큐에 넣은 데이터 중 가장 처음에 넣은 데이터)
- 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을 호출한다.enque()함수를 호출하는 과정에서 배열의 마지막 인덱스rear == FixedQueue.que[capacity - 1]까지 도달했을 때, 인큐하는 과정에서 rear(배열의 마지막 값이자 다음에 데이터가 들어와야 하는 위치)가 1 증가하면서 배열의 범위를 넘으므로, rear의 값을 배열의 맨 앞 인덱스인 0으로 초기화 시킨다. 이렇게 되었을 때 배열의 앞 부분이 비었있다면 배열의 크기 범위 내에서 배열의 재사용이 가능하다.코드로 나타냈을 때는 아래와 같다.
... 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 함수
deque()함수는 큐의 맨 앞에서부터 디큐하여 그 값을 반환한다.
하지만 큐가 비어있어 디큐할 수 없는 경우 위에서 정의한 예외 처리인FixedQueue.Empty을 호출한다.deque()함수를 호출하는 과정에서 배열의 마지막 인덱스front == FixedQueue.que[capacity - 1]까지 도달했을 때, 디큐하는 과정에서front(배열의 첫 번째 값이자 다음에 추출해야 하는 값)가 1 증가하면서 배열의 범위를 넘을 수 있다. 이때 다시 배열의 값이 있는FixedQueue.que[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 ...인큐와 디큐 모두
capacity의 범위를 넘으면 초기화 하는 이유는 원형 큐에서 지정된 크기 만큼 큐에서 계속 순회해야 하기 때문이다.데이터의 값을 확인하는 peek 함수
peek()함수는 맨 앞의 데이터, 즉 다음 디큐에서 꺼낼 데이터를 확인한다.
데이터를 추출하지 않고 확인만 하기 때문에que[front]값만 반환하고,front, rear, no의 값은 변하지 않는다.
큐가 비어 있을 땐 예외 처리FixedQueue.Empty를 호출하게 된다.데이터를 검색하는 find 함수
find()함수는 큐의 배열에서 value와 같은 데이터가 포함되어 있는지 확인해 위치를 반환한다.
배열의 스캔 작업은front- 맨 앞의 원소부터rear- 맨 뒤의 원소를 선형 검색한다.
따라서 스캔할 때 주목하는 인덱스를 구하는 식은(i + front) % capacity이다.
예를 들어, capacity가 5인 배열 크기에서 front가 3이라고 쳤을 때, 맨 처음의 원소 값(front)부터 선형 검색을 해야하므로(0 + 3(front)) % 5(capacity) = 3의 식을 도출할 수 있다.코드로 나타냈을 땐 다음과 같다.
... 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 ...이렇게 구현해야 다음의 인큐와 디큐의 값을 정확히 알 수 있고, 당연하게도 데이터의 순서도 정확하게 확인이 가능하다.
데이터 개수를 세는 count 함수
count()함수는 큐에 있는 데이터(value)의 개수를 구하여 반환한다.데이터가 포함되어 있는지 판단하는 _contains_ 함수
__contains__()함수는 큐에 데이터(value)가 포함되어 있는지 판단한다.
데이터가 들어있다면True, 그렇지 않다면False를 반환한다.큐의 전체 원소를 삭제하는 clear 함수
clear()함수는 현재 큐에 들어있는 모든 데이터를 삭제한다.
인큐와 디큐는 모두 no, front, rear를 바탕으로 수행하므로, 이들 값을 0으로 초기화 해주면 된다.(실제 que의 원솟 값을 삭제할 필요는 없다. 어차피 다음 인큐에서 데이터를 덮어쓰고, 디큐을 했을 땐 예외처리가 발생하므로큐의 전체 데이터를 출력하는 dump 함수
dump()함수는 큐에 들어 있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 출력한다.고정 길이의 원형 큐(링 버퍼) 구현 - 전체 코드
# FixedQueue.py # 고정 길이 큐 클래스 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): """큐가 비어 있는지 판단""" return self.no <= 0 def is_full(self): """큐가 모두 차 있는지 판단""" return self.no >= self.capacity 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 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()[LAB] 위에서 구현한 FixedQueue 실습
# fixedqueue_test.py from enum import Enum from FixedQueue 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
실습한 내용은 이미지로 대체! 더 알아보기
원형 큐(링 버퍼)의 활용
원형 큐는 위에서 언급했듯이 배열을 재사용하는 용도로 설명했는데, 다른 뜻으로 풀이해보면 오래된 데이터는 버리고 최신의 데이터 n개만 저장하는 용도로 사용이 가능하다는 것을 뜻한다. 즉, 인큐는 계속할 수 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 n개만 링 퍼버에 남는 것!
예를 들어 n = 10개, 인큐를 12개 했다고 했을 때 가장 처음에 인큐한 2개의 데이터는 삭제되고, 3번째에 넣은 데이터부터 마지막에 입력한 데이터까지만 큐에 저장되게 된다.
즉que[2] ~ que[9], que[0], que[1]순서대로 출력하게 해야함이를 구현한 코드는 아래와 같다.
# 원하는 개수(n)만큼 값을 입력받아 마지막의 n개를 저장 n = int(input('정수를 몇 개 저장할까요?: ')) que = [None] * n # 큐의 크기 cnt = 0 # 정수를 입력받은 개수 while True: que[cnt % n] = int(input(f'{cnt + 1}번째 정수를 입력하세요.: ')) cnt += 1 retry = input(f'계속 진행할까요?(Y or N) : ') if retry in {'N', 'n'}: break i = cnt - n # 12개(총 입력한 데이터 개수) - 10개(수용할 수 있는 큐의 크기) = 2개를 버려야 함 if i < 0: # cnt(총 입력한 데이터)가 n개 보다 적을 때 위의 코드로 음수가 출력되기 때문에 i = 0 # 0으로 초기화 while i < cnt: # 3번째의 데이터부터 마지막 데이터까지 순회하면서 출력 print(f'{i + 1}번째 = {que[i % n]}') i += 1Ref
두잇파이썬
https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)
파이썬 알고리즘 인터뷰 - 원형큐
파이썬 알고리즘 인터뷰 - 데크https://ko.wikipedia.org/wiki/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84_%ED%81%90
이전글이 없습니다.댓글