[DataStructure] Deque

Deque (덱)

• 선형구조

• Double-ended queue 의 약자

• 양방향으로 데이터를 추가, 제거 가능

Method

• push_front : front 에 임의의 데이터 추가

• push_back : back 에 임의의 데이터 추가

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

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

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

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

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

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

Python Implementation Code

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None  # left = front side
        self.right = None  # right = back side
        

class Deque:
    def __init__(self):
        self.front = None
        self.back = None
        self.size = 0
        
    def push_front(self, data):
        new = Node(data)
        if not self.is_empty():
            new.right = self.front
            self.front.left = new
            self.front = new
        else:
            self.front = new
            self.back = new
        self.size += 1
    
    def push_back(self, data):
        new = Node(data)
        if not self.is_empty():
            new.left = self.back
            self.back.right = new
            self.back = new
        else:
            self.back = new
            self.front = new
        self.size += 1
    
    def pop_front(self):
        if not self.is_empty():
            tmp = self.front.data
            self.front = self.front.right
            if self.front: self.front.left = None
            self.size -= 1
            return tmp
        else:
            print('Empty Deque')
    
    def pop_back(self):
        if not self.is_empty():
            tmp = self.back.data
            self.back = self.back.left
            if self.back: self.back.right = None
            self.size -= 1
            return tmp
        else:
            print('Empty Deque')
    
    def get_front(self):
        if not self.is_empty():
            return self.front.data
        else:
            print('Empty Deque')
    
    def get_back(self):
        if not self.is_empty():
            return self.back.data
        else:
            print('Empty Deque')
    
    def get_size(self):
        return self.size
    
    def is_empty(self):
        return False if self.get_size() else True

push_front

pop_front

deque 의 front 가 self.front.right 를 참조하게 한 뒤,
self.front.left 가 None 을 참조하게 하여
이전 front 에 해당했던 node 는 제거된다. (해당 인스턴스를 참조하는 값이 없기 때문)
제거된 값을 반환할 수는 없기 때문에 제거하기전 tmp 에 self.front.data 값을 저장해둔 뒤, 마지막에 반환한다.

self.front.left = None 에 if self.front 조건문을 붙인 이유는
새로운 self.front 가 None 이 될 수 있으며, 이 경우
None 에는 left 속성이 없어 에러가 발생할 수 있기 때문이다.