Deque?

Java/자료구조

크크크크 2025. 3. 11. 23:18

728x90

시리즈

자바 기반 설명이며 개념에 관한 내용을 다룹니다.

큐와 스택의 장점을 취하고 단점을 보완한 자료구조로
더 유연하고 안정적인 데이터 관리가 가능합니다.
다만, 성능은 상황에 따라 달라져 구조를 알고 효율적으로 사용해야 적절합니다.

Deque(Double-ended Queue, 덱)는 큐와 스택의 단점을 보완한 자료구조로, 양쪽에서 삽입과 삭제가 가능한 형태입니다.

큐(Queue)와 스택(Stack)은 각각 단순한 선형 자료구조이지만, 다음과 같은 문제점이 존재합니다.

큐(Queue)의 문제점
- FIFO 구조로 인해 한쪽에서만 삽입(enqueue)하고 반대쪽에서만 삭제(dequeue)하므로 유연성이 부족함
- 배열 기반 큐는 크기가 고정적이며, 초과 시 원형 큐(Circular Queue)나 동적 크기 조정이 필요
- LinkedList 기반 큐는 추가적인 포인터 관리가 필요해 성능 오버헤드가 발생
스택(Stack)의 문제점
- LIFO 구조로 인해 가장 최근 요소만 접근 가능하므로, 중간 데이터 접근이 어렵고 활용성이 제한됨
- 함수 호출 스택처럼 한 방향으로만 작동하므로, 다중 방향 처리가 불가능
- 다중 프로세스 환경에서 동기화를 고려하지 않으면 경합(Race Condition) 문제가 발생 가능

이러한 문제를 해결하기 위해 Deque(덱)이 등장하였습니다.

Deque는 양쪽에서 삽입과 삭제가 가능하여, 스택과 큐의 기능을 모두 수행할 수 있습니다.

이러한 특성 덕분에 Deque는 더 안정적인 자료구조로 평가받습니다.
특히, 동기화 및 성능 측면에서 더 효율적인 자료구조를 제공할 수 있습니다.

양방향 접근 가능 → 유연성 증가
- 일반 큐와 스택은 한 방향에서만 삽입/삭제가 가능하지만
- Deque는 양쪽에서 가능하여 상황에 따라 최적화된 방식으로 사용 가능
Circular(원형) 구조 가능 → 메모리 낭비 방지
- Deque는 원형으로 연결될 수 있어 메모리 공간 활용을 최적화할 수 있음
- 일반 큐는 배열 크기를 초과하면 원형 큐를 별도로 구현해야 하지만, Deque는 기본적으로 이를 지원
Concurrency(동시성) 지원 → 멀티스레드 환경에서 안정적
- ConcurrentLinkedDeque 같은 Deque 기반 자료구조는 멀티스레드 환경에서 안전하게 사용할 수 있도록 설계됨
- BlockingDeque는 생산자-소비자 패턴에서 효율적인 데이터 흐름을 보장

운영체제(스케줄링)
- CPU 작업 스케줄러에서 Deque를 사용하여 선입선출(FIFO) 방식과 스택 기반(LIFO) 방식의 혼합 처리 가능
웹 브라우저의 앞으로/뒤로 가기
- 방문한 페이지를 Deque로 관리하여, 뒤로 가기 시 pop(), 앞으로 가기 시 push() 수행
캐시(Cache) 구현 (LRU 알고리즘)
- LinkedHashMap과 함께 Deque을 사용하여 가장 오래된 데이터를 효율적으로 제거
그래프 탐색 (BFS & DFS 혼합 사용 가능)
- BFS(너비 우선 탐색)에서는 일반 큐처럼 동작
- DFS(깊이 우선 탐색)에서는 스택처럼 동작

Deque는 큐와 스택의 단점을 보완하여 등장한 자료구조로, 더 유연하고 안정적인 데이터 관리가 가능하게 합니다.
특히, 멀티스레드 환경, 운영체제 스케줄링, 캐싱 등에서 효과적으로 활용됩니다.

그렇다면, 큐와 스택은 불필요할까?

제한된 동작 방식으로 제한된 범위 내에 특정 상황에서 효율적일 수 있을거 같은데?

728x90