[자료구조] 데크(Deque)

데크(Deque)는 Double-Ended Queue의 줄임말로, 양쪽 끝에서 데이터를 추가/반환/삭제할 수 있는 형태의 자료구조이다.
다시 말해 스택(Stack)과 큐(Queue)의 특징을 모두 갖고 있다.
배열(Array)로도 구현 가능하지만 이중 연결 리스트(Double Linked List)로 구현하는 것이 더 잘 어울린다.

핵심 연산

• push_front(item) : 데크 맨앞에 데이터 삽입
• push_back(item) : 데크 맨뒤에 데이터 삽입
• pop_front() : 데크 맨앞 데이터 삭제 및 반환
• pop_back() : 데크 맨뒤 데이터 삭제 및 반환
• front() : 데크 맨앞 데이터 반환
• back() : 데크 맨뒤 데이터 반환
• insert(i, item) : i번째 인덱스에 데이터 삽입
• erase(i) : i번째 인덱스 데이터 삭제
• size() : 데크 크기 반환
• empty() : 데크가 비었는지 여부 반환
• full() : 데크가 가득 찼는지 여부 반환

구현 [Python]

class Node:
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

class Deque:
    maxlen = 10

    def __init__(self):
        self.head, self.tail = Node(None), Node(None)
        self.length = 0
        self.head.right, self.tail.left = self.tail, self.head

    def _push(self, prev: Node, new: Node):
        new.left, new.right = prev, prev.right
        new.left.right = new.right.left = new
        self.length += 1

    def _pop(self, prev: Node):
        link = prev.right.right
        ret = prev.right.item
        prev.right, link.left = link, prev
        self.length -= 1
        return ret

    def _previous(self, i: int) -> Node:
        prev = self.head
        for _ in range(i):
            prev = prev.right
        return prev

    def push_front(self, item):
        if not self.full():
            self._push(self.head, Node(item))

    def push_back(self, item):
        if not self.full():
            self._push(self.tail.left, Node(item))

    def pop_front(self):
        if not self.empty():
            return self._pop(self.head)

    def pop_back(self):
        if not self.empty():
            return self._pop(self.tail.left.left)

    def front(self):
        if not self.empty():
            return self.head.right.item

    def back(self):
        if not self.empty():
            return self.tail.left.item

    def insert(self, i: int, item):
        self._push(self._previous(i), Node(item))

    def erase(self, i: int):
        self._pop(self._previous(i))

    def size(self):
        return self.length

    def empty(self):
        return self.size() == 0

    def full(self):
        return self.size() == self.maxlen