Queue

삽입과 삭제가 선입선출 방식이다.

삽입은 queue의 끝에서 이루어지고 삭제는 queue의 앞에서 이루어진다.

선입선출은 먼저들어온 것이 먼저 나가는 방식이다,

operation

enqueue(object): 큐의 끝 부분에 요소를 넣는다

dequeue(): 큐의 앞 부분 요소를 제거한 후 반환한다.

first(): 제거 없이 맨 앞 요소를 반환한다.

len(): 저장된 요소의 갯수를 반환한다.

is_empty(): 저장된 요소의 여부를 반환한다.

Array-based Queue

◾ front 인자와 rear 인자를 받는다.

◾ rear 위치는 항상 비어있어야 한다.

size()

$(n - f + r)\; mod\;n$으로 표현할 수 있다.

유도

큐에 저장된 항목의 갯수를 N이라 할 때, N = (r - f) mod N이라고 할 수 있다.
이 식을 변형해서 N = (r - f + N) mod N으로 쓸 수 있다.
∴ N = (N - f + r) mod N이라는 결과가 나온다.

is_Empty()

r과 f가 같을 때 큐가 비어있다고 판단할 수 있다.

enqueue(object)

만약 size가 N-1이라면 큐가 가득 찼으므로 오류를 발생시킨다.
아니라면 큐의 끝에 오브젝트를 넣은 후 rear = (rear + 1) mod N을 해준다.

N을 나눈 이유는 r이 배열의 인덱스를 벗어날 경우 다시 처음 위치로 돌리기 위함이다.

dequeue()

queue가 비어있다면 뺄 요소가 없으므로 오류를 발생시킨다.
아니라면 큐의 맨 앞 요소를 새 변수에 넣은 후
front = (front + 1) mod N을 해준다.
그 후 맨 앞 요소를 반환한다.

구현코드

class ArrayQueue:
    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):
        return self.size == 0
    
    def first(self):
        if self.is_empty():
            raise ValueError('Queue is Empty')
        return self.data[self.front]
    
    def dequeue(self):
        if self.is_empty():
            raise ValueError('Queue is Empty')
        answer = self.data[self.front]
        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.data))
        avail = (self.front + self.size) % len(self.data)
        self.data[avail] = e
        self.size += 1
        
    def resize(self, cap):
        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