덱(Deque)

Deque (Double-Ended Queue) 완전 가이드

1. 정의 (Definition)

덱(Deque, Double-Ended Queue)은 선형 자료구조의 세 번째 추상 자료형(ADT)으로, 양쪽 끝(front와 back)에서 모두 데이터를 삽입하고 삭제할 수 있는 자료구조입니다.

기본 특징

• 양방향 접근: 앞쪽(front)과 뒤쪽(back) 모두에서 데이터 조작 가능
• 유연성: 스택(LIFO)이나 큐(FIFO)와 달리 양방향으로의 접근과 수정이 자유로움
• 효율성: 모든 핵심 연산이 상수 시간 복잡도 Θ(1)로 수행

다른 자료구조와의 비교

자료 구조	삽입 위치	삭제 위치	특성
스택(Stack)	한쪽 끝	한쪽 끝	LIFO
큐(Queue)	한쪽 끝	다른 쪽 끝	FIFO
덱(Deque)	양쪽 끝	양쪽 끝	양방향

2. 추상 자료형 (Abstract Data Type)

덱의 핵심 ADT 연산들은 다음과 같습니다:

핵심 연산 (Core Operations)

삽입 연산

• push_front(data): 데이터를 덱의 앞쪽에 삽입
• push_back(data): 데이터를 덱의 뒤쪽에 삽입

삭제 연산

• pop_front(): 덱의 앞쪽에서 데이터를 삭제하고 반환
• pop_back(): 덱의 뒤쪽에서 데이터를 삭제하고 반환

조회 연산

• front(): 덱의 가장 앞쪽 데이터를 조회 (삭제하지 않음)
• back(): 덱의 가장 뒤쪽 데이터를 조회 (삭제하지 않음)

상태 확인 연산

• empty(): 덱이 비어있는지 확인
• size(): 덱에 저장된 데이터의 개수를 반환

시간 복잡도 요구사항

모든 핵심 연산(push, pop 포함)은 상수 시간 복잡도 Θ(1)으로 수행되어야 합니다.

3. 구현 방법 (Implementation Methods)

3.1 이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 덱 구현의 가장 일반적인 방법입니다.

장점

• 양쪽 끝에서 삽입 및 삭제를 Θ(1) 시간에 수행 가능
• 동적 메모리 할당으로 크기 제한 없음
• 구현이 직관적이고 이해하기 쉬움

구현 특징

• 각 노드는 데이터와 이전/다음 노드에 대한 포인터를 가짐
• head와 tail 포인터를 유지하여 양쪽 끝 접근을 효율화
• 래퍼(wrapper) 클래스 형태로 구현하여 캡슐화 제공

[head] ←→ [노드1] ←→ [노드2] ←→ [노드3] ←→ [tail]

구현

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None
        
class DoubleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        newNode = Node(data)
        if not self.head:
            self.head = newNode
            self.tail = newNode
            self.size += 1
        else:
            self.tail.next = newNode
            newNode.prev = self.tail
            self.tail = newNode
            self.size += 1
    
    def preAppend(self, data):
        newNode = Node(data)
        if not self.head:
            self.head = newNode
            self.tail = newNode
            self.size += 1
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
            self.size += 1
    
    def findFirst(self):
        if not self.head:
            return None
        else:
            return self.head.data
    
    def findLast(self):
        if not self.head:
            return None
        else:
            return self.tail.data
    
    def eraseFirst(self):
        if not self.head:
            return None
        else:
            current = self.head
            self.head = current.next
            if self.head == None:
                self.tail = self.head
            else:
                self.head.prev = None
            self.size -= 1
            return current.data
    
    def eraseLast(self):
        if not self.head:
            return None
        else:
            current = self.tail
            self.tail = current.prev
            if self.tail == None:
                self.head = self.tail
            else:
                self.tail.next = None
            self.size -= 1
            return current.data
            
    def display(self):
        if not self.head:
            return
        else:
            current = self.head
            answer = []
            while current:
                answer.append(current.data)
                current = current.next
            print(answer, self.size)
            
class Deque:
    def __init__(self):
        self.list = DoubleLinkedList()

    def push_front(self, data):
        self.list.preAppend(data)
            
    def push_back(self, data):
        self.list.append(data)
    
    def pop_front(self):
        answer = self.list.eraseFirst()
        if not answer:
            return '-1'
        else:
            return answer
        
    def pop_back(self):
        answer = self.list.eraseLast()
        if not answer:
            return '-1'
        else:
            return answer
    
    def front(self):
        answer = self.list.findFirst()
        if not answer:
            return '-1'
        else:
            return answer
    
    def back(self):
        answer = self.list.findLast()
        if not answer:
            return '-1'
        else:
            return answer
        
    def isEmpty(self):
        if self.list.size == 0:
            return '1'
        else:
            return '0'
    
    def getSize(self):
        return self.list.size
    
    def display(self):
        self.list.display()

3.2 원형 배열 (Circular Array)

원형 배열을 사용한 구현은 비교적 직관적인 방법입니다.

장점

• 메모리 효율성이 높음
• 캐시 지역성이 좋아 성능 향상 가능
• 고정 크기로 메모리 관리가 단순

구현 특징

• front와 rear 인덱스를 사용하여 덱의 시작과 끝을 추적
• 배열의 끝에 도달하면 처음으로 돌아가는 원형 구조
• 배열 크기 관리와 오버플로우 처리 필요

4. 활용 방법 (Applications)

4.1 다목적 자료구조로 활용

덱의 유연성으로 인해 다양한 용도로 사용 가능합니다:

• 스택으로 사용: push_back()과 pop_back()만 사용
• 큐로 사용: push_back()과 pop_front() 조합 사용

4.2 경로 탐색 알고리즘

미로 탐색과 같은 경로 탐색 문제에서 효과적으로 활용됩니다:

사용 패턴

1. 현재 위치까지의 경로를 덱에 저장
2. 앞으로 나아갈 때: push_front() 사용
3. 뒤로 되돌아갈 때: pop_front() 사용
4. 최종 경로 발견 시: 덱의 뒤쪽에서 경로를 순서대로 읽기

장점

• 백트래킹 구현이 간단
• 경로 저장과 복원이 효율적
• 메모리 사용량 최적화

4.3 기타 응용 분야

• 슬라이딩 윈도우 알고리즘: 윈도우의 양쪽 끝에서 요소 추가/제거
• 팰린드롬 검사: 양쪽 끝에서 문자를 비교
• 작업 스케줄링: 우선순위에 따라 양쪽 끝에서 작업 처리

5. 성능 특성 및 고려사항

시간 복잡도

연산	시간 복잡도
push_front/push_back	Θ(1)
pop_front/pop_back	Θ(1)
front/back	Θ(1)

공간 복잡도

• 이중 연결 리스트: O(n) + 포인터 오버헤드
• 원형 배열: O(n) + 고정 크기 제약

선택 기준

• 메모리 효율성 중시: 원형 배열 구현
• 동적 크기 필요: 이중 연결 리스트 구현

결론

덱(Deque)은 양쪽 끝에서의 삽입과 삭제가 모두 가능한 유연한 선형 자료구조로, 스택과 큐의 기능을 모두 포함하면서도 더 강력한 기능을 제공합니다. 모든 핵심 연산이 상수 시간에 수행되어야 한다는 효율성 요구사항을 만족하며, 이중 연결 리스트나 원형 배열을 통해 구현할 수 있습니다.

 

특히 경로 탐색, 슬라이딩 윈도우 알고리즘 등 다양한 분야에서 활용되며, C++ STL의 deque는 임의 접근과 반복자 기능까지 제공하여 실무에서 강력한 도구로 사용됩니다.