큐의 활용
1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(asychronously)으로 일어나는 경우
2. 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
3. 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
4. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
5. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
환형 큐 (circular Queue) : 정해진 개수의 저장 공간을 돌려가며 이용
큐가 가득차면 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야 함)
기존 큐 연산에 다음을 추가한다.
isFull() : 큐에 데이터 원소가 꽉차있는지를 판단
rear는 가장 최근에 enqueue된 데이터를 가리킴
front는 가장 첫번째 데이터 부터 삭제되는 위치를 가리킴
15강 실습 : 환형 큐 구현
class CircularQueue:
def __init__(self, n):
self.maxCount = n
self.data = [None] * n
self.count = 0
self.front = -1
self.rear = -1
def size(self):
return self.count
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.maxCount
def enqueue(self, x):
if self.isFull():
raise IndexError('Queue full')
self.rear = (self.rear + 1) % self.maxCount
self.data[self.rear] = x
self.count += 1
def dequeue(self):
if self.isEmpty():
raise IndexError('Queue empty')
self.front = (self.front + 1) % self.maxCount
x = self.data[self.front]
self.count -= 1
return x
def peek(self):
if self.isEmpty():
raise IndexError('Queue empty')
return self.data[(self.front+ 1)%self.maxCount]
'Algorithm' 카테고리의 다른 글
[프로그래머스 알고리즘] 17강: 트리 (Trees) (0) | 2021.07.20 |
---|---|
[프로그래머스 알고리즘] 16강: 우선순위 큐 (Priority Queues) (0) | 2021.07.19 |
[프로그래머스 알고리즘]14강: 큐(Queue) (0) | 2021.07.17 |
[프로그래머스 알고리즘] 12강, 13강: 수식의 후위 표기법 및 수식 계산(Postfix Notation) (0) | 2021.07.16 |
[프로그래머스 알고리즘] 11강: 스택 (Stacks) (0) | 2021.07.16 |