Deque?

시리즈

2025.03.11 - [Java/자료구조] - 스택? 큐?

2025.03.11 - [Java/자료구조] - Deque?

 

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

📌 핵심내용

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

---

Deque(덱)가 등장한 배경과 필요성

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

1. Deque가 등장한 이유

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

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

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

2. Deque의 장점과 해결책

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

• 앞쪽에서 삽입/삭제 → 큐의 add()/poll() 기능
• 뒤쪽에서 삽입/삭제 → 스택의 push()/pop() 기능

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

3. Deque가 안정적인 이유

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

4. 실제 사용 사례

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

5. 결론

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

 

6. 의문점

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

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