-
Queue
큐는 또다른 기능적 자료구조입니다. 쉽게 스택의 "사촌"과 비슷합니다. 큐는
First-in, First-out (FIFO)
원리에 따라 삽입과 제거되는 객체들의 모임입니다. 요소는 자유롭게 삽입될 수 있습니다. 그러나, 요소는 가장 오래 머물렀던 요소 부터 제거됩니다. 큐 추상적 데이터 타입은 객체를 순서대로 유지하는 집합을 정의합니다. 요소의 접근 또는 삭제는 큐의 처음 요소로 제한되고 요소의 삽입은 큐 순서의 가장 마지막으로 제한됩니다.큐 추상적 데이터 형식(ADT)는 두가지 메서드를 다룹니다.
- Q.enqueue(e): 큐의 마지막에 요소를 추가합니다.
- Q.dequeue(): 큐의 가장 앞 요소를 제거하고 반환합니다. 큐가 비었을 때, 에러가 발생합니다.
큐 ADT는 또한 다른 메서드도 포함합니다.
- Q.first(): 큐의 첫번째 요소를 반환힞;민 제거하지는 않습니다. 큐가 비었을 때, 에러가 발생합니다.
- Q.is_empty(): 큐가 비었을 경우에 True 아니면 False를 반환합니다.
- len(Q): 큐의 길이를 반환합니다.
배열-기반 큐 구현
배열-기반 큐를 구현하는 것은 사실 비효율적입니다. 배열의 앞 원소를 제거히면 두번째 원소 부터 첫번째 요소로 옮겨야 하기 때문에 pop(0) 의 시간복잡도는 O(n) 입니다. 그래서 pop(0) 사용을 피함으로써 효율을 높힐 수 있습니다. 배열에서 dequeue된 요소를 None을 참조함으로 바꾸고 큐 요소 하나하나는 자신의 바로 뒤 요소의 값을 참조합니다. 이러한 알고리즘은 큐의 dequeue 시간 복잡도를 O(1) 로 줄일 수 있습니다.
그러나, 아직 단점이 있습니다. 스택의 경우, 리스트의 길이는 스택의 사이즈와 같습니다. 그러나 지금까지 디자인한 큐는 dequque를 해도 앞에 빈 공간이 있기 떄문에 배열의 사이즈가 줄지는 않습니다. 따라서 큐의 요소 길이가 짧더라도 실제 큐의 할당된 메모리의 크기는 더 클 수 있습니다.Using an Array Circularly
배열의 형태를 환형태로 구현하면 이 문제가 해결됩니다. 대신 큐의 맨 앞 인덱스의 위치를 저장하는
front
변수와 맨 뒤 인덱스의 위치를 저장하는rear
변수가 필요합니다. 삽입시 연산은rear = (rear+1) % N
(큐의 크기)이고, 제거시 연산은front = (front+1) % N
입니다.A Python Queue Implementation
큐 클래스에서는 다음 세가지 인스턴스 변수를 가집니다
- _data : 실제 큐의 값들을 리스트 형태로 저장합니다.
- _size : 현재 큐 사이즈를 저장합니다.
- _front: 리스트 형태 큐의 front 인덱스를 저장합니다.(큐가 비어있지 않을 경우)
class ArrayQueue: """선형 리스트를 사용한 FIFO 큐 구현""" DEFAULT_CAPACITY = 10 #큐의 용량 def __init__(self): """큐를 생성""" self.data = [None]* ArrayQueue.DEFAULT_CAPACITY self.size = 0 self.front = 0 def len (self): """큐의 길이 반환""" return self.size def is_empty(self): """큐가 비어있다면 False를 반환합니다""" return self.size == 0 def first(self): """ 큐의 맨 앞 요소의 값을 리턴합니다. 큐가 비어있다면 에러가 발생합니다. """ if self.is_empty(): raise Empty('Queue is empty') return self.data[self.front] def dequeue(self): """ 큐의 맨 앞 요소를 삭제하고 그 값을 리턴합니다. 큐가 비었있다면 에러가 발생합니다. """ if self.is_empty(): raise Empty( Queue is empty ) answer = self.data[self.front] self.data[self.front] = None self.front = (self.front+1)%len(self.data) self.size −= 1 return answer def enqueue(self,e): """ 큐의 공간이 꽉 차있다면 크기를 늘려줍니다 """ if self.size == len(self.data): self.resize(2*len(self)) avail = (self.front + self.size)% len(self.data) self.data[avail] = e self.size+=1 def resize(self, cap): """ 배열이 꽉 차있을 경우에 크기를 늘랴줍니다. front 요소부터 다시 차례대로 정렬합니다. """ old = self.data self.data = [None] * cap walk = self.front for k in range(self.size): self.data[k]=old[walk] walk = (walk+1)%len(old) self.front = 0
'자료구조' 카테고리의 다른 글
자료 구조 한방에 정리 (0) 2020.12.15 Doubly Linked List (0) 2020.10.06 Singly Linked List (0) 2020.10.03 Double-Ended Queue (0) 2020.09.30 Stack (0) 2020.09.27