Queue

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