Circular Queue

지난시간에 Queue 자료구조는 Data를 지울 경우 Queue의 Max Capacity가 감소한다고 했습니다.

teus-kiwiee.tistory.com/24

Queue

Circular Queue는 이러한 단점을 극복하기 위해서 고안된 특이한 Case의 Queue라고 할 수 있습니다.

 

추상화된 선형 Queue(좌)와 원형 Queue(우)

 

원형Queue는 선형Queue의 Input과 Output이 서로 붙어있는 구조라고 할 수 있습니다.

 

이렇게되면 FIFP의 원칙을 유지하되, Element가 삭제되어도 Capacity가 줄어들지 않습니다.

 

이때 Queue의 Empty상태와 Full상태를 구분하기 위해서 한칸의 공백을 유지하여

 

Input Pointer == Output Pointer -> Empty

 

input Pointer - Output Pointer == 1 -> Full

 

의 방법을 통해서 Queue의 Status를 확인할 수 있게됩니다.

 

Python으로 구현된 원형 Queue 소스코드입니다 :)

class c_queue:
    def __init__(self, Max_size):
        self.Max_size = Max_size
        #Status 확인을 위해서 Input_pointer의 초기값이 0이 아닌 1로 할당
        self.input_pointer = 1
        self.out_pointer = 0
        self.list = []
        
    def add(self, element):
        #1차원 구조상의 양 끝이 붙어있다고 추상화
        if (self.input_pointer == self.out_pointer-1) or (self.input_pointer-self.out_pointer==self.Max_size):
            return print("queue is full")
        else:
            if self.input_pointer>=self.Max_size:
                self.input_pointer = (self.input_pointer - self.Max_size)
                self.list= self.list + [element]
            else:
                self.input_pointer = self.input_pointer+1
                self.list= self.list + [element]
    
    def delete(self):
    	#1차원 구조상의 양 끝이 붙어있다고 추상화
        if (self.input_pointer-self.out_pointer==1) or (self.out_pointer-self.input_pointer==self.Max_size):
            return print("queue is empty")
        else:
            if self.out_pointer>=self.Max_size:                
                self.out_pointer = self.Max_size - self.out_pointer
                del(self.list[0])
            else:
                self.out_pointer = self.out_pointer+1
                del(self.list[0])
    
    def is_full(self):
        if (self.input_pointer == self.out_pointer-1) or (self.input_pointer-self.out_pointer==self.Max_size):
            return True
        else:
            return False
    
    def is_empty(self):
        if (self.input_pointer-self.out_pointer==1) or (self.out_pointer-self.input_pointer==self.Max_size):
            return True
        else:
            return False
        
        
import random
data = [i for i in range(20)]
random.shuffle(data)

test_que = c_queue(19)

for i in data:
    test_que.add(i)
==> queue is full
    
test_que.input_pointer
==> 19

for i in data:
    test_que.delete()
    
test_que.is_empty()
==> True