[알고리즘] 17. 덱(Deque)

[알고리즘] 17. 덱(Deque)

지난 글에서는 큐(Queue)에 대해 정리했습니다. 이번 글에서는 큐보다 조금 더 유연한 자료구조인 덱(Deque)에 대해 알아보겠습니다.

덱은 양쪽 끝에서 데이터를 넣고 뺄 수 있는 자료구조입니다. 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있어서 알고리즘 문제에서 꽤 자주 등장합니다.

덱은 앞과 뒤 양쪽에서 삽입과 삭제가 가능한 자료구조입니다.

---

1. 덱이란?

덱은 Double Ended Queue의 줄임말입니다. 이름 그대로 양쪽 끝을 모두 사용할 수 있는 큐입니다.

일반 큐는 뒤에서 넣고 앞에서 꺼내는 구조입니다. 하지만 덱은 앞에서도 넣을 수 있고, 뒤에서도 넣을 수 있습니다. 또 앞에서도 꺼낼 수 있고, 뒤에서도 꺼낼 수 있습니다.

일반 큐:
뒤에서 넣고 → 앞에서 꺼냄

덱:
앞에서 넣기 가능
뒤에서 넣기 가능
앞에서 꺼내기 가능
뒤에서 꺼내기 가능

그래서 덱은 큐보다 더 넓은 기능을 가진 자료구조라고 볼 수 있습니다.

덱은 양쪽 문이 모두 열려 있는 큐라고 생각하면 이해하기 쉽습니다.

---

2. 덱의 기본 구조

덱은 앞쪽과 뒤쪽을 모두 사용할 수 있습니다. 보통 앞쪽을 front, 뒤쪽을 rear라고 표현합니다.

front                          rear
  ↓                              ↓
[ 10 ][ 20 ][ 30 ][ 40 ][ 50 ]

덱에서는 아래와 같은 동작이 가능합니다.

• 앞에 값 넣기
• 뒤에 값 넣기
• 앞의 값 꺼내기
• 뒤의 값 꺼내기
• 앞의 값 확인하기
• 뒤의 값 확인하기

이처럼 덱은 데이터의 양쪽 끝을 자유롭게 다룰 수 있습니다.

---

3. 덱의 대표 연산

Java에서 덱을 사용할 때 자주 쓰는 연산은 다음과 같습니다.

연산	의미
addFirst()	앞쪽에 값을 넣는다.
addLast()	뒤쪽에 값을 넣는다.
offerFirst()	앞쪽에 값을 넣는다.
offerLast()	뒤쪽에 값을 넣는다.
pollFirst()	앞쪽 값을 꺼낸다.
pollLast()	뒤쪽 값을 꺼낸다.
peekFirst()	앞쪽 값을 확인한다.
peekLast()	뒤쪽 값을 확인한다.

알고리즘 문제에서는 실패 시 예외를 던지는 add 계열보다, 실패 시 값을 반환하는 offer, poll 계열을 자주 사용합니다.

덱에서는 First가 앞쪽, Last가 뒤쪽을 의미합니다.

---

4. Java에서 Deque 사용하기

Java에서 덱은 Deque 인터페이스로 사용할 수 있습니다. 구현체로는 보통 ArrayDeque를 많이 사용합니다.

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(10);
deque.offerLast(20);
deque.offerLast(30);

System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());

출력 결과는 다음과 같습니다.

10
20
30

뒤에 넣고 앞에서 꺼냈기 때문에 큐처럼 동작합니다.

Java에서는 Deque<타입> deque = new ArrayDeque<>(); 형태를 자주 사용합니다.

---

5. 앞쪽에 넣고 앞쪽에서 꺼내기

덱은 앞쪽에 값을 넣을 수도 있습니다. 앞쪽에 계속 값을 넣고 앞쪽에서 꺼내면 스택처럼 동작합니다.

Deque<Integer> deque = new ArrayDeque<>();

deque.offerFirst(10);
deque.offerFirst(20);
deque.offerFirst(30);

System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());

출력 결과는 다음과 같습니다.

30
20
10

10, 20, 30 순서로 넣었지만 앞쪽에 계속 넣었기 때문에 가장 마지막에 넣은 30이 먼저 나옵니다. 이 흐름은 스택의 후입선출 구조와 같습니다.

---

6. 뒤쪽에 넣고 앞쪽에서 꺼내기

뒤쪽에 값을 넣고 앞쪽에서 꺼내면 일반 큐처럼 동작합니다.

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(10);
deque.offerLast(20);
deque.offerLast(30);

System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());

출력 결과는 다음과 같습니다.

10
20
30

먼저 들어간 값이 먼저 나오므로 선입선출 구조입니다.

사용 방식	동작 구조
offerFirst + pollFirst	스택처럼 동작
offerLast + pollFirst	큐처럼 동작

덱은 사용하는 연산 조합에 따라 스택처럼도, 큐처럼도 사용할 수 있습니다.

---

7. 양쪽 값 확인하기

덱에서는 앞쪽 값과 뒤쪽 값을 모두 확인할 수 있습니다. 값을 제거하지 않고 확인만 할 때는 peekFirst(), peekLast()를 사용합니다.

Deque<Integer> deque = new ArrayDeque<>();

deque.offerLast(10);
deque.offerLast(20);
deque.offerLast(30);

System.out.println(deque.peekFirst());
System.out.println(deque.peekLast());
System.out.println(deque.size());

출력 결과는 다음과 같습니다.

10
30
3

peekFirst()는 앞쪽 값 10을 확인하고, peekLast()는 뒤쪽 값 30을 확인합니다. 값을 제거하지 않았기 때문에 덱의 크기는 그대로 3입니다.

---

8. 덱의 동작 흐름 예시

덱에 앞뒤로 값을 넣고 꺼내는 흐름을 표로 정리해보겠습니다.

초기 상태: 비어 있음

offerLast(10)  → [10]
offerLast(20)  → [10, 20]
offerFirst(5)  → [5, 10, 20]
pollLast()     → [5, 10]
pollFirst()    → [10]

동작	덱 상태
offerLast(10)	[10]
offerLast(20)	[10, 20]
offerFirst(5)	[5, 10, 20]
pollLast()	[5, 10]
pollFirst()	[10]

덱은 앞과 뒤를 모두 조작할 수 있기 때문에 일반 큐보다 표현할 수 있는 상황이 많습니다.

---

9. 덱으로 문자열 앞뒤 검사하기

덱은 문자열의 앞과 뒤를 동시에 비교할 때 유용합니다. 대표적으로 회문 검사 문제에 사용할 수 있습니다.

회문은 앞에서 읽어도, 뒤에서 읽어도 같은 문자열입니다.

level
madam
토마토

덱을 이용하면 앞 문자와 뒤 문자를 하나씩 꺼내 비교할 수 있습니다.

import java.util.ArrayDeque;
import java.util.Deque;

String word = "level";

Deque<Character> deque = new ArrayDeque<>();

for (int i = 0; i < word.length(); i++) {
    deque.offerLast(word.charAt(i));
}

boolean palindrome = true;

while (deque.size() > 1) {
    char front = deque.pollFirst();
    char back = deque.pollLast();

    if (front != back) {
        palindrome = false;
        break;
    }
}

System.out.println(palindrome);

출력 결과는 다음과 같습니다.

true

앞쪽 문자와 뒤쪽 문자를 동시에 꺼내 비교하면 회문 여부를 쉽게 확인할 수 있습니다.

---

10. 덱으로 양방향 처리하기

덱은 앞쪽과 뒤쪽 모두에서 작업이 일어나는 문제에 잘 어울립니다. 예를 들어 작업이 상황에 따라 앞에 추가되기도 하고, 뒤에 추가되기도 하는 경우입니다.

Deque<String> deque = new ArrayDeque<>();

deque.offerLast("강아지");
deque.offerLast("고양이");
deque.offerFirst("토끼");

System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());

출력 결과는 다음과 같습니다.

토끼
고양이

토끼는 앞쪽에 들어갔기 때문에 먼저 꺼냈고, 고양이는 뒤쪽에서 꺼냈습니다.

이처럼 덱은 양방향으로 순서를 조절해야 하는 문제에서 유용합니다.

---

11. 덱이 사용되는 대표 상황

덱은 아래와 같은 상황에서 자주 사용됩니다.

상황	이유
앞뒤 삽입과 삭제	양쪽 끝을 모두 사용해야 함
회문 검사	앞 문자와 뒤 문자를 비교하기 좋음
스택 대체	한쪽 끝만 사용하면 스택처럼 동작함
큐 대체	뒤에 넣고 앞에서 꺼내면 큐처럼 동작함
슬라이딩 윈도우 최댓값	필요 없는 값을 앞뒤에서 제거할 수 있음

덱은 단순한 자료구조처럼 보이지만, 양쪽 끝을 모두 다룰 수 있다는 점 때문에 다양한 문제에 활용됩니다.

---

12. 덱과 스택, 큐 비교하기

스택, 큐, 덱은 모두 데이터를 넣고 빼는 자료구조입니다. 차이는 어디에서 넣고 어디에서 꺼내는지에 있습니다.

구분	삽입	삭제	특징
스택	한쪽	한쪽	후입선출
큐	뒤쪽	앞쪽	선입선출
덱	앞쪽, 뒤쪽	앞쪽, 뒤쪽	양쪽 처리 가능

덱은 스택과 큐의 기능을 모두 표현할 수 있는 더 유연한 구조입니다.

스택은 한쪽, 큐는 정해진 방향, 덱은 양쪽을 사용합니다.

---

13. ArrayDeque를 자주 쓰는 이유

Java에서는 덱을 구현할 때 ArrayDeque를 자주 사용합니다. 스택처럼 사용할 때도 Stack 클래스 대신 ArrayDeque를 사용하는 경우가 많습니다.

이유는 ArrayDeque가 양쪽 삽입과 삭제에 효율적이고, 스택과 큐 역할을 모두 할 수 있기 때문입니다.

Deque<Integer> stack = new ArrayDeque<>();

stack.offerLast(10);
stack.offerLast(20);
stack.offerLast(30);

System.out.println(stack.pollLast());

출력 결과는 다음과 같습니다.

30

뒤쪽에 넣고 뒤쪽에서 꺼내면 스택처럼 사용할 수 있습니다.

알고리즘 문제에서는 Stack보다 Deque와 ArrayDeque 조합을 선호하는 경우가 많습니다.

---

14. 덱의 시간복잡도

덱의 기본 연산은 대부분 빠르게 처리됩니다.

연산	시간복잡도
offerFirst()	O(1)
offerLast()	O(1)
pollFirst()	O(1)
pollLast()	O(1)
peekFirst()	O(1)
peekLast()	O(1)

앞과 뒤에서 넣고 빼는 작업이 모두 O(1)에 가깝게 처리됩니다. 따라서 양쪽 끝을 자주 다루는 문제에서 덱은 매우 효율적입니다.

덱은 양쪽 끝을 다루는 연산이 빠르다는 점이 핵심입니다.

---

15. 덱에서 자주 하는 실수

덱 문제를 풀 때는 아래 실수를 조심해야 합니다.

• First와 Last의 방향을 헷갈리는 경우
• 비어 있는 덱에서 pollFirst()나 pollLast() 결과를 바로 사용하는 경우
• 스택처럼 쓸 때 넣는 방향과 꺼내는 방향을 다르게 쓰는 경우
• 큐처럼 쓸 때 pollFirst()와 pollLast()를 혼동하는 경우
• peek은 확인만 하고 제거하지 않는다는 점을 잊는 경우
• 덱이 필요한 문제를 배열 앞쪽 삭제로 처리해 비효율이 생기는 경우

특히 방향을 헷갈리지 않는 것이 중요합니다. 앞쪽을 기준으로 처리할지, 뒤쪽을 기준으로 처리할지 먼저 정한 뒤 코드를 작성하는 것이 좋습니다.

앞쪽: First
뒤쪽: Last

---

16. 정리

이번 글에서는 덱에 대해 정리했습니다.

• 덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다.
• Deque는 Double Ended Queue의 줄임말이다.
• 앞쪽은 First, 뒤쪽은 Last로 표현한다.
• offerFirst(), offerLast()로 값을 넣을 수 있다.
• pollFirst(), pollLast()로 값을 꺼낼 수 있다.
• peekFirst(), peekLast()로 양쪽 끝 값을 확인할 수 있다.
• 덱은 스택처럼도, 큐처럼도 사용할 수 있다.
• Java에서는 Deque와 ArrayDeque 조합을 자주 사용한다.
• 덱의 기본 연산은 대부분 O(1)이다.

덱은 처음에는 큐의 확장 버전처럼 보이지만, 양쪽 끝을 모두 사용할 수 있다는 점 때문에 매우 유용합니다. 스택과 큐를 모두 표현할 수 있고, 앞뒤 비교나 양방향 처리 문제에도 잘 어울립니다.

덱의 핵심은 앞과 뒤를 모두 자유롭게 사용할 수 있다는 점입니다.

---

다음 글 예고

다음 글에서는 해시맵(HashMap)에 대해 알아보겠습니다.

key와 value 구조, put과 get, getOrDefault, 빈도수 계산, 빠른 검색이 필요한 문제까지 예제로 정리해보겠습니다.