26. Design Circular Deque

리트코드

• 다음 연산을 제공하는 원형 데크를 디자인 하라

  • MyCircularDeque(k): 데크 사이즈를 k로 지정하는 생성자다

  • insertFront(): 데크 처음에 아이템을 추가하고, 성공할 경우 true를 리턴한다.

  • insertLast(): 데크 마지막에 아이템을 추가하고 성공할 경우 true를 리턴한다.

  • deleteFront(): 데크 처음에 아이템을 삭제하고 성공할 경우 true를 리턴한다.

  • deleteLast(): 데크 마지막에 아이템을 삭제하고 성공할 경우 true를 리턴한다.

  • getFront(): 데크의 첫 번째 아이템을 가져온다. 데크가 비어 있다면 -1을 리턴한다.

  • getRear(): 데크의 마지막 아이템을 가져온다. 데크가 비어 있다면 -1을 리턴한다.

  • isEmpty(): 데크가 비어 있는지 여부를 판별한다.

  • isFull(): 데크가 가득 차 있는지 여부를 판별한다.

1. 이중 연결 리스트를 이용한 데크 구현

class MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head
    
    #이중 연결 리스트에 신규 노드 삽입
    def _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new
        
    def _del(self, node:ListNode):
        n = node.right.right
        node.right = n
        n.left = node
        

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True
        
        

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.tail.left, ListNode(value))
        return True
        

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        
        if self.len == 0:
            return False
        
        self.len -= 1
        self._del(self.head)
        return True
        

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True
        

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        return self.head.right.val if self.len else -1
        

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        return self.tail.left.val if self.len else -1
        

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return self.len == 0
        

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return self.len == self.k
        


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

• 이 문제는 원형 큐 구현 문제와 달리, 맨 앞에 노드를 추가하는 insertFront()연산도 있다.

• 먼저 초기화 함수 init을 구현하자.

  • 구현하려는 데크는 CPython의 구현과 유사하게 왼쪽, 오른쪽 인덱스 역할을 하는 head, tail을 정의하고, 최대 길이 정보를 k로 설정한다.

  • 현재 길이 정보를 담는 변수가 될 len을 self.len = 0으로 따로 정의해둔다.

• 다음으로 앞쪽에 노드를 추가하는 연산 insertFront()를 구현해보자

  • 새로운 노드 삽입 시 최대 길이에 도달했을 때는 False를 리턴

  • 이외에는 _add()메소드를 이용해 head 위치에 노드를 삽입한다.

• insertLast()도 마찬가지로, 한 가지 다른 점은 head가 아닌 tail.left에 삽입한다는 점이다.

• 실제 삽입을 수행하는 내부 함수 _add() 메소드를 구현해보자

  • 내부에서만 사용한다는 의미로 PEP8 명명 규칙 기준에 따라 밑줄(_) 하나로 시작하도록 메소드 명을 다음과 같이 _add()로 정했다.

• 삭제의 경우 앞쪽 삭제는 head의 노드를, 뒤쪽 삭제는 tail위치의 노드를 처리한다.

  • 뒤쪽의 경우 정확히는 tail.left.left를 _del()메소드로 처리하게 된다.

<이중 연결 리스트의 노드에 신규 노드를 삽입하는 과정>

• _add() 메소드는 다음과 같이 이미 있는 노드를 찢어내고, 그 사이에 새로운 노드 new를 삽입하는 형태가 된다.

➕

• 사실 원형 데크를 이중 연결 리스트로 구현하게 되면 원형의 이점을 전혀 살릴 수 없게 된다.

  • 실제로 원형의 이점을 살리기 위해서라면 원래 이 문제는 연결 리스트가 아닌 배열로 풀이해야 한다.

• 원형으로 구현하는 이유는 뒤쪽을 요소를 채우다가 공간이 다 차게되면 tail과 head를 연결해 앞쪽의 빈 공간을 활용하려는 의도인데, 연결 리스트는 애초에 빈 공간이라는 개념이 존재하지 않기 때문에 원형은 아무런 의미가 없다.

  • 또한, 데크의 연산은 맨 처음과 맨 끝의 값을 추출할 뿐이며, 맨 끝의 다음 값을 추출하는지 등의 연산은 존재하지 않기 때문에, 서로 연결되어 있을 필요 또한 없다.

  • 이 경우, 사실상 아무런 의미 없이 tail과 head가 서로 이중 연결 리스트로 연결되어 있으며, 단순히 풀이를 위해 구현되어 있는 셈이다.

✔ 데크

• 데크(Deque)

  • 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.

• 데크는 양쪽에서 삽입과 삭제를 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 가지고 있다.

  • 이 추상 자료형(ADT)의 구현은 배열이나 연결리스트 모두 가능하지만, 특별히 다음과 같이 이중 연결 리스트(Doubly Linked List)로 구현하는 편이 가장 잘 어울린다.

<이중 연결 리스트로 구현한 데크 구조>

• 이중 연결 리스트로 구현하게 되면, 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜주기만 하면 된다.

  • 당연히 연결 후에는 포인터를 이동하면 된다.

Collections 모듈

• 파이썬은 데크 자료형을 collections 모듈에서 deque라는 이름을 지원한다.

>>> import collections
>>> d = collections.deque()
>>> type(d)
<class collections.deque'>

• 이 collections.deque는 마찬가지로 이중 연결 리스트로 구현되어 있다.

• CPython에서는 고정 길이 하위 배열(Subarray)을 지닌 이중 연결 리스트로 구현되어 있으며, 내부 구현을 살펴보면 마찬가지로 다음과 같이 구조체인 dequeobject가 block 노드의 이중 연결 리스트로 구현되어 있는 것을 확인할 수 있다.

• dequeobject는 왼쪽, 오른쪽 인덱스 정보와 최대 길이 등 여러 가지 부가 정보를 함께 보관하고 있는 푸웁한 구조체임을 알 수 있다.

// cpython/Modules/_collectionsmodule.c

typedef struct BLOCK{
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
}block;

typedef struct{
    ...
    block *leftblock;
    block *rightblock;
    
    Py_ssize_t leftindex;
    Py_ssize_t rightindex;
    Py_ssize_t maxlen;
    
    ...
}dequeobject;