Queue

Queue는 Array를 활용한 사용자 자료구조 중 하나입니다.

 

Queue의 원리는 First In First Out(FIFP)

 

가장 먼저 들어온 Element가 가장 먼저 나간다 입니다.

 

정수기의 종이컵 / 놀이공원 대기열을 생각하면 쉽습니다.

 

Q추상화된 Queue

Queue 역시 자료구조이기 때문에, Element의 Add와 Delete가 존재합니다.

 

하지만 FIFP의 원칙 때문에 Delete는 Output에서만, Add는 Input 에서만 가능합니다.

 

Queue의 Operation

이때 Delete부분을 보면, Output Pointer가 움직이면서 첫번째 위치는 더이상 Pointing하지 못하는 것을 알 수 있습니다.

 

때문에 선형 Queue의 경우 Queue가 채워진 후 삭제되면 Capacity가 같이 감소하는 단점이 있습니다.

 

Python으로 구현된 선형Queue입니다.

class queue:
    def __init__(self, Max_size):
        self.Max_size = Max_size
        #Queue의 Input과 Output의 위치를 Pointing
        self.input_pointer = 0
        self.out_pointer = 0
        #Queue를 운용할 Array
        self.list = []
        
    #Input Pointer의 위치를 고려하여
    #가능한경우 Queue에 Element를 추가합니다.
    def add(self, element):
        if self.input_pointer>self.Max_size:
            return print("queue is full")
        else:
            self.list= self.list + [element]
            self.input_pointer = self.input_pointer+1
    
    #Output Pointer의 위치를 고려하여
    #가능한경우 Queue에 Element를 제거합니다.
    def delete(self):
        if self.input_pointer==self.out_pointer:
            return print("queue is empty")
        else:
            del(self.list[0])
            self.out_pointer = self.out_pointer+1
    
    def is_full(self):
        if self.input_pointer>self.Max_size:
            return True
        else:
            return False
    
    def is_empty(self):
        if self.input_pointer==self.out_pointer:
            return True
        else:
            return False
        
        
import random
data = [i for i in range(30)]
random.shuffle(data)

#Max Size가 20인 Queue 생성
test_que = queue(19)

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

#Queue가 가득 찬 상태의 Input Pointer의 위치
test_que.input_pointer
==> 20

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