파이썬 알고리즘 인터뷰 26번 문제 : 원형데크디자인

문제설명

이문제는 원형 데크를 디자인하는 문제이다. 데크는 파이썬의 모듈로서 양쪽 끝을 모두 추출할 수 있는 큐이다. 파이썬의 데크의 기능을 하는 클래스를 이중연결리스트로 구현해보자

 

class MyCircularDeque:

    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.k, self.len = k, 0 #k는 원형데크의 최대길이, len은 원형데크의 현재 길이이다.
        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:
        if self.len == self.k :
            return False
        self.len +=1
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.k :
            return False
        self.len += 1
        self._add(self.tail.left, ListNode(value))
        return True

    def deleteFront(self) -> bool:
        if self.len == 0 :
            return False
        self.len -=1
        self._del(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0 :
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True

    def getFront(self) -> int:
        if self.len :
            return self.head.right.val
        else :
            return -1

    def getRear(self) -> int:
        if self.len :
            return self.tail.left.val
        else :
            return -1

    def isEmpty(self) -> bool:
        return self.len == 0

    def isFull(self) -> bool:
        return self.len == self.k

 

 

출처  : 파이썬 알고리즘 인터뷰 (95가지 알고리즘 문제풀이로 완성하는 코딩테스트, 박상길 지음)