[DataStructure] Queue

Queue (큐)

• 선형구조

• FIFO (First In First Out)

• 한쪽의 방향으로 데이터를 추가하고 반대방향에서 데이터를 제거 가능

Method

• push : 임의의 데이터 추가

• pop : front 에 위치하는 데이터 꺼낸 뒤 해당값 반환

• get_front : front 에 위치하는 값 반환

• get_back : back 에 위차하는 값 반환

• get_size : 데이터 갯수 (사이즈) 반환

• is_empty : 비어있는지 유무 반환 (bool)

Python Implementation Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        

class Queue:
    def __init__(self):
        self.front = None
        self.back = None
        self.size = 0
        
    def push(self, data):
        new = Node(data)  # 새로운 node 생성
        if not self.is_empty():
            self.back.next = new
            self.back = new
        else:
            self.front = new
            self.back = new
        self.size += 1
    
    def pop(self):
        if not self.is_empty():
            tmp = self.front.data
            self.front = self.front.next
            self.size -= 1
            return tmp
        else:
            print('Empty Queue')
    
    def get_front(self):
        if not self.is_empty():
            return self.front.data
        else:
            print('Empty Queue')
    
    def get_back(self):
        if not self.is_empty():
            return self.back.data
        else:
            print('Empty Queue')
    
    def get_size(self):
        return self.size
        
    def is_empty(self):
        return False if self.get_size() else True

push

새로운 노드 new 인스턴스를 생성한 뒤
현재 back 에 해당하는 node 가 새로 push 된 node 을 참조하도록 하는 것이 우선되어야한다.
queue 의 back 을 new 로 먼저 할당할 경우 이전의 back 을 참조할 수가 없어지기 때문이다.

pop

queue 의 front 가 self.front.next 를 참조하도록 하는 것으로
이전 front 에 해당했던 node 는 제거된다. (해당 인스턴스를 참조하는 값이 없기 때문)
제거된 값을 반환할 수는 없기 때문에 제거하기전 tmp 에 self.front.data 값을 저장해둔 뒤, 마지막에 반환한다.