큐(Queue)
- 자료(data element)를 보관할 수 있는 (선형) 구조
- 단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 - enqueue 연산
- 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음 - dequeue 연산
- 선입선출(FIFO - First In First Out) 특징을 가지는 선형 자료구조
큐의 추상적 자료구조 구현
- 배열(Array)를 이용하여 구현
class ArrayQueue:
def __init__(self):
self.data = []
def size(self):
return len(self.data)
def isEmpty(self):
return self.size() == 0
def enqueue(self, item):
self.data.append(item)
def dequeue(self):
return self.data.pop(0)
def peek(self):
return self.data[0]
❌ 이렇게 되면 dequeue 연산시 시간 복잡도가 $O(n)$이 된다.
- 연결 리스트(linked list)를 이용하여 구현
- 연산 정의
- size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
- imEmpty() - 현재 큐가 비어 있는지를 판단
- enqueue(x) - 데이터 원소 x를 큐에 추가
- dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
- peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)
환형큐(Circular Queue)
큐(queue)의 활용
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(asynchronously) 일어나는 경우
- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
- 자료를 처리하고 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
환형큐(Circular queue)
- 정해진 개수의 저장 공간을 빙 돌려가며 이용
- 큐가 가득 차면?
- 더 이상 원소를 넣을 수 없음(큐 길이를 기억하고 있어야 함)
- 환형 큐의 추상적 자료구조 구현
- 연상의 정의
- size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함
- isEmpty() - 현재 큐가 비어 있는지를 판단
- isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
- enqueue(x) - 데이터 원소 x를 큐에 추가
- dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거(또한, 반환)
- peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)
- 배열로 구현한 환형 큐
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]
'프로그래머스 AI 데브코스 5기 > CS' 카테고리의 다른 글
Flask 입문 (0) | 2023.04.04 |
---|---|
트리(Trees) (0) | 2023.03.28 |
스택(stack) (0) | 2023.03.27 |
Git & Github (0) | 2023.03.27 |
Web Scraping 기초 - 3 (0) | 2023.03.23 |