Deque / Deque Python 구현

Deque

---

선입선출의 자료구조는 큐이다. 양방향 큐를 덱(Deque)이라고 한다.

• 양 방향에서 데이터의 삽입과 삭제가 이루어진다.
• 스택과 큐의 연산을 모두 구현할 수 있다.
• 보통 LinkedList로 구현하는 만큼 삽입과 삭제 속도가 빠르다. → O(1)
  

Deque 코드

---

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

class Deque():
    def __init__(self):
        self.head = Node(None, None, None)
        self.tail = Node(None, self.head, None)
        self.head.next = self.tail
        self.length = 0
    
    def ft_push_front(self, X):
        if self.length == 0:
            newNode = Node(X, self.head, self.tail)
            self.head.next = newNode
            self.tail.prev = newNode
            self.length += 1
        else:
            newNode = Node(X, self.head, self.head.next)
            self.head.next = newNode
            newNode.next.prev = newNode
            self.length += 1
    
    def ft_push_back(self, X):
        if self.length == 0:
            newNode = Node(X, self.head, self.tail)
            self.head.next = newNode
            self.tail.prev = newNode
            self.length += 1
        else:
            newNode = Node(X, self.tail.prev, self.tail)
            self.tail.prev = newNode
            newNode.prev.next = newNode
            self.length += 1

    def ft_size(self):
        print(self.length)
    
    def ft_empty(self):
        if self.length == 0:
            print(1)
        else:
            print(0)
    
    def ft_front(self):
        if self.length == 0:
            print(-1)
        else:
            print(self.head.next.data)
    
    def ft_back(self):
        if self.length == 0:
            print(-1)
        else:
            print(self.tail.prev.data)

    def ft_pop_front(self):
        if self.length == 0:
            print(-1)
        else:
            print(self.head.next.data)
            self.head.next = self.head.next.next
            self.head.next.prev = self.head
            self.length -= 1

    def ft_pop_back(self):
        if self.length == 0:
            print(-1)
        else:
            print(self.tail.prev.data)
            self.tail.prev = self.tail.prev.prev
            self.tail.prev.next = self.tail
            self.length -= 1

• 덱은 양쪽 끝에서 데이터의 삽입과 삭제 연산이 가능해야 하기 때문에, 왼쪽 끝과 오른쪽 끝의 정보를 가진 노드를 사용하는 이중 연결 리스트를 이용하여 구현했다.