Python 자료구조 5.2. 덱(deque)

덱이란?

• 덱의 구조
• 덱 ADT
• 덱의 연산
• 덱을 스택이나 큐로 사용할 수 있다.

덱의 구조

1. 스택이나 큐보다 입출력이 자유로운 자료구조
2. 덱(deque)은 double - ended - queue의 줄임말
3. 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

덱 ADT

• 데이터: 전단과 후단을 통한 접근을 허용하는 항목들의 모음
• 연산
• Deque(): 비어 있는 새로운 덱을 만든다.
• isEmpty(): 덱이 비어있으면 True 아니면 False를 반환한다.
• addFront(x): 항목 x를 덱의 맨 앞에 추가한다.
• deleteFront(): 맨 앞의 항목을 꺼내서 반환한다.
• getFront(): 맨 앞의 항목을 꺼내지 않고 반환한다.
• addRear(x): 항목 x를 덱의 맨 뒤에 추가한다.
• deleteRear(): 맨 뒤의 항목을 꺼내서 반환한다.
• getRear(): 맨 뒤의 항목을 꺼내지 않고 반환한다.
• isFull(): 덱이 가득 차 있으면 True를 아니면 False를 반환한다.
• size(): 덱의 모든 항목들의 개수를 반환한다.
• clear(): 덱을 공백상태로 만든다.

원형 덱의 연산

• 큐와 데이터는 동일함

• 연산은 유사함

• 큐와 알고리즘이 동일한 연산

• addRear(), deleteFront(), gerFront()
  -> 큐의 enqueue, dequeue, peek 연산과 동일

• 덱의 후단(rear)을 스택의 상단(top)으로 사용
  -> addRear(),deleteRear(),getRear() 연산은 스택의 push,pop,peek 연산과 정확하게 동일

<추가된 연산 by 원형 큐>

• delete_rear(), add_front(), get_rear()
  -> 반시계 방향 회전 필요

front = (front -1 + MAX_QSIZE) % MAX_QSIZE
rear = (rear -1 + MAX_QSIZE) % MAX_QSIZE

덱의 구현

< 덱은 구조상 큐와 비슷>

• 원형 덱으로 구현하는 것이 연산들의 시간 복잡도를 O(1)로 만들 수 있는 좋은 방법이다.

• 원형 큐를 상속하여 원형 덱 클래스를 구현해보자(중요!!)

# 덱의 구현

class CirCularDeque(CircularQueue): # CircularQueue 에서 상속
    def __init__(self):
        super().__init__()
        
    def addRear(self.item):
        self.enqueue(item)
    
    def deleteFront(self):
        return self.dequeue()
    
    def getFront(self):
        return self.peek()
    
    
    def addFront(self,item):
        if not self.isFull():
            self.items[self.front] = item
            self.front = self.front -1 
            if self.front < 0 :
                self.front = MAX_QSIZE -1
                
    def deleteRear(self):
        if not self.isEmpty():
            item = self.items[self.rear];
            self.rear = self.rear -1
            if self.rear < 0 :
                self.rear = MAX_QSIZE - 1
            
            return item
        
    def getRear(self):
        return self.items[self.rear]