덱(Deque)의 구조와 연산

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 구조

대상자

- 프로그래밍 초보자 및 중급자

- 자료구조 학습자

- 배열 기반 데이터 구조의 구현 원리 이해가 필요한 개발자

- 난이도: 중간 (배열의 경계 조건 처리와 예외 처리 논리 분석 필요)

핵심 요약

• Deque는 양 끝에서 데이터 삽입/삭제가 가능한 선형 자료구조
• Circular Array를 기반으로 구현 (front와 rear 포인터 사용)
• Overflow/Underflow 예외 처리 및 포인터 재설정 로직 포함

섹션별 세부 요약

1. Deque의 정의 및 특징

• FIFO 원칙을 따르지 않음 (양 끝에서 삽입/삭제 가능)
• 두 가지 유형 존재

- Input Restricted Deque: 삽입 제한 (하나의 끝), 삭제 가능 (양 끝)

- Output Restricted Deque: 삭제 제한 (하나의 끝), 삽입 가능 (양 끝)

• Circular Array 구현 시 배열이 가득 차면 시작점으로 이동

2. 삽입 연산 (insertFront / insertRear)

• insertFront

- front == 0 시 front = size - 1 (배열 끝으로 이동)

- front == rear + 1 또는 front == 0 && rear == size - 1 시 Overflow

• insertRear

- rear == size - 1 시 rear = 0 (배열 시작점으로 이동)

- 동일한 조건으로 Overflow 발생

• 코드 예시: insertFront(key) 메서드는 this.arr[this.front] = key로 값 삽입

3. 삭제 연산 (deleteFront / deleteRear)

• deleteFront

- front == -1 시 Underflow

- front == rear 시 front = rear = -1

- front == size - 1 시 front = 0

• deleteRear

- rear == 0 시 rear = size - 1

- rear == front 시 front = rear = -1

• 코드 예시: deleteFront()는 this.arr[this.front] = null로 메모리 해제

4. 상태 확인 및 예외 처리

• isFull(): front == 0 && rear == size - 1 또는 front == rear + 1
• isEmpty(): front == -1
• Overflow/Underflow 예외 처리

- console.log('Overflow! Cannot insert...') 또는 console.log('Underflow! Cannot delete...')

5. 예제 실행 및 출력

• 예시: new Deque(4) 생성 후 insertFront(5), insertRear(6) 실행
• 출력 예: Deque contents: 5 -> 6 -> 7 -> 8
• 삭제 후: deleteRear() → 20 삭제, deleteFront() → 2 삭제

결론

• Deque 연산은 O(1) 시간 복잡도를 유지
• 배열 경계 조건 처리 및 포인터 재설정 로직이 핵심
• Overflow/Underflow 예외 처리는 안정적인 구현을 위해 필수
• 실무 적용 시 circular array 구현 방식을 우선 고려