덱 (Deque)
프로그래밍에서 덱(Deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이다. Double-Ended Queue의 약자로, 큐와 스택의 기능을 모두 포함한다. 덱은 슬라이딩 윈도우, 회전 큐, 작업 스케줄링 등 다양한 상황에서 활용된다. 덱의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.
덱을 이해하면 양방향 데이터 처리가 가능해지고 복잡한 문제를 효율적으로 해결할 수 있다.
덱의 정의와 특징
덱은 양쪽 끝에서 데이터를 추가하고 제거할 수 있는 자료구조이다. 앞쪽 끝을 프론트(front), 뒤쪽 끝을 리어(rear)라고 부른다. 큐처럼 FIFO(First In, First Out) 방식으로 동작하거나, 스택처럼 LIFO(Last In, First Out) 방식으로 동작할 수 있다.
덱의 장점은 다음과 같다:
- 양방향 접근: 프론트와 리어에서 삽입과 삭제가 가능하다.
- 유연성: 큐와 스택의 기능을 모두 제공한다.
- 빠른 연산: 대부분의 연산이 O(1) 시간에 수행된다.
단점은 다음과 같다:
- 제한된 접근: 중간 요소에 직접 접근할 수 없다.
- 고정 크기 배열 사용 시 제한: 동적 크기 조정이 필요하다.
- 비연속적 메모리: 연결 리스트 기반 덱은 캐시 활용도가 낮다.
덱의 종류
덱은 구현 방식에 따라 두 가지로 나뉜다.
1. 배열 기반 덱(Array-based Deque)
고정 크기 배열을 사용한다. 메모리 효율이 높지만 크기 제한이 있다.
[Front] [1] [2] [3] [Rear]
↑ ↑
Front Rear
2. 연결 리스트 기반 덱(Linked List-based Deque)
이중 연결 리스트를 사용해 동적으로 크기를 조정한다.
[Front] ↔ [Node|data:1] ↔ [Node|data:2] ↔ [Node|data:3] ↔ [Rear]
배열 기반 덱과 연결 리스트 기반 덱을 중심으로 설명한다.
자바에서 덱 구현
덱은 배열과 연결 리스트로 구현할 수 있다. 두 가지 방법을 아래에 제시한다.
배열 기반 덱 구현
원형 배열을 사용해 공간을 효율적으로 관리한다.
class ArrayDeque {
private int[] arr;
private int front;
private int rear;
private int capacity;
private int size;
public ArrayDeque(int capacity) {
this.capacity = capacity;
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
// 앞에 삽입
public void addFront(int data) {
if (size == capacity) {
System.out.println("Deque is Full");
return;
}
front = (front - 1 + capacity) % capacity;
arr[front] = data;
if (size == 0) rear = front;
size++;
}
// 뒤에 삽입
public void addRear(int data) {
if (size == capacity) {
System.out.println("Deque is Full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
if (size == 0) front = rear;
size++;
}
// 앞에서 삭제
public int removeFront() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
// 뒤에서 삭제
public int removeRear() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
int data = arr[rear];
rear = (rear - 1 + capacity) % capacity;
size--;
return data;
}
// 앞 데이터 조회
public int peekFront() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
return arr[front];
}
// 뒤 데이터 조회
public int peekRear() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
return arr[rear];
}
// 비어 있는지 확인
public boolean isEmpty() {
return size == 0;
}
}
연결 리스트 기반 덱 구현
이중 연결 리스트를 사용해 동적 크기 조정이 가능하다.
class LinkedDeque {
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node front;
private Node rear;
private int size;
public LinkedDeque() {
front = null;
rear = null;
size = 0;
}
// 앞에 삽입
public void addFront(int data) {
Node newNode = new Node(data);
if (front == null) {
front = rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
size++;
}
// 뒤에 삽입
public void addRear(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
} else {
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
size++;
}
// 앞에서 삭제
public int removeFront() {
if (front == null) {
System.out.println("Deque is Empty");
return -1;
}
int data = front.data;
front = front.next;
if (front == null) rear = null;
else front.prev = null;
size--;
return data;
}
// 뒤에서 삭제
public int removeRear() {
if (rear == null) {
System.out.println("Deque is Empty");
return -1;
}
int data = rear.data;
rear = rear.prev;
if (rear == null) front = null;
else rear.next = null;
size--;
return data;
}
// 앞 데이터 조회
public int peekFront() {
if (front == null) {
System.out.println("Deque is Empty");
return -1;
}
return front.data;
}
// 뒤 데이터 조회
public int peekRear() {
if (rear == null) {
System.out.println("Deque is Empty");
return -1;
}
return rear.data;
}
// 비어 있는지 확인
public boolean isEmpty() {
return size == 0;
}
}
덱의 기본 연산
덱의 주요 연산은 다음과 같다:
1. 앞에 삽입(addFront)
덱의 프론트에 데이터를 추가한다.
public void addFront(int data) {
if (size == capacity) {
System.out.println("Deque is Full");
return;
}
front = (front - 1 + capacity) % capacity;
arr[front] = data;
if (size == 0) rear = front;
size++;
}
2. 뒤에 삽입(addRear)
덱의 리어에 데이터를 추가한다.
public void addRear(int data) {
if (size == capacity) {
System.out.println("Deque is Full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
if (size == 0) front = rear;
size++;
}
3. 앞에서 삭제(removeFront)
덱의 프론트에서 데이터를 제거하고 반환한다.
public int removeFront() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
4. 뒤에서 삭제(removeRear)
덱의 리어에서 데이터를 제거하고 반환한다.
public int removeRear() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
int data = arr[rear];
rear = (rear - 1 + capacity) % capacity;
size--;
return data;
}
5. 앞 데이터 조회(peekFront)
덱의 프론트 데이터를 제거하지 않고 반환한다.
public int peekFront() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
return arr[front];
}
6. 뒤 데이터 조회(peekRear)
덱의 리어 데이터를 제거하지 않고 반환한다.
public int peekRear() {
if (size == 0) {
System.out.println("Deque is Empty");
return -1;
}
return arr[rear];
}
7. 비어 있음 확인(isEmpty)
덱이 비어 있는지 확인한다.
public boolean isEmpty() {
return size == 0;
}
덱의 시간 복잡도
덱의 주요 연산의 시간 복잡도는 다음과 같다:
- 앞에 삽입(addFront): O(1)
- 뒤에 삽입(addRear): O(1)
- 앞에서 삭제(removeFront): O(1)
- 뒤에서 삭제(removeRear): O(1)
- 앞 데이터 조회(peekFront): O(1)
- 뒤 데이터 조회(peekRear): O(1)
- 비어 있음 확인(isEmpty): O(1)
연결 리스트 기반 덱도 동일한 시간 복잡도를 가지지만, 노드 생성/삭제 비용이 추가된다.
덱을 활용한 알고리즘
덱은 슬라이딩 윈도우, 회전 큐 등에서 사용된다.
슬라이딩 윈도우
고정 크기의 윈도우를 이동하며 윈도우 내 최대값이나 최소값을 찾는다.
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
LinkedDeque deque = new LinkedDeque();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peekFront() < i - k + 1) {
deque.removeFront();
}
while (!deque.isEmpty() && nums[deque.peekRear()] < nums[i]) {
deque.removeRear();
}
deque.addRear(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFront()];
}
}
return result;
}
회전 큐
덱의 요소를 회전시킨다.
public void rotateDeque(LinkedDeque deque, int k) {
for (int i = 0; i < k; i++) {
int front = deque.removeFront();
deque.addRear(front);
}
}
심화 주제: 덱 최적화
덱의 성능을 향상시키는 기법을 다룬다.
동적 배열 사용
배열 기반 덱에서 크기를 동적으로 조정한다.
public void addFront(int data) {
if (size == capacity) {
resize();
}
front = (front - 1 + capacity) % capacity;
arr[front] = data;
size++;
}
private void resize() {
int newCapacity = capacity * 2;
int[] newArr = new int[newCapacity];
for (int i = 0; i < size; i++) {
newArr[i] = arr[(front + i) % capacity];
}
arr = newArr;
front = 0;
rear = size - 1;
capacity = newCapacity;
}
메모리 관리
연결 리스트 기반 덱에서 노드 재사용을 고려할 수 있다. 자바에서는 가비지 컬렉터가 이를 처리한다.
덱의 한계와 대안
덱은 중간 요소 접근이 불가능하다. 자바에서는 ArrayDeque와 LinkedList를 제공한다.
import java.util.ArrayDeque;
ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
int front = deque.removeFirst(); // 1
int rear = deque.removeLast(); // 2
ArrayDeque는 성능이 우수하며, LinkedList는 동적 크기 조정이 가능하다.
문제
덱을 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시한다.
난이도 하: 덱 연산
시간 제한: 1 초 | 메모리 제한: 256 MB |
덱에 대한 연산을 수행한다. 연산은 “addFront x”, “addRear x”, “removeFront”, “removeRear”로 구성된다.
입력
첫째 줄에 연산 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N줄에 연산이 주어진다.
출력
“removeFront”와 “removeRear” 연산의 결과를 한 줄에 하나씩 출력한다. 덱이 비어 있으면 -1을 출력한다.
입력 예시
5
addFront 1
addRear 2
removeFront
addRear 3
removeRear
출력 예시
1
3
문제 출처: 자체 제작
해답
해답 펼치기
import java.util.Scanner;
public class DequeOperations {
static class ArrayDeque {
private int[] arr;
private int front;
private int rear;
private int capacity;
private int size;
ArrayDeque(int capacity) {
this.capacity = capacity;
arr = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
void addFront(int data) {
if (size == capacity) return;
front = (front - 1 + capacity) % capacity;
arr[front] = data;
if (size == 0) rear = front;
size++;
}
void addRear(int data) {
if (size == capacity) return;
rear = (rear + 1) % capacity;
arr[rear] = data;
if (size == 0) front = rear;
size++;
}
int removeFront() {
if (size == 0) return -1;
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
int removeRear() {
if (size == 0) return -1;
int data = arr[rear];
rear = (rear - 1 + capacity) % capacity;
size--;
return data;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
ArrayDeque deque = new ArrayDeque(N);
sc.nextLine();
for (int i = 0; i < N; i++) {
String operation = sc.nextLine();
if (operation.startsWith("addFront")) {
int x = Integer.parseInt(operation.split(" ")[1]);
deque.addFront(x);
} else if (operation.startsWith("addRear")) {
int x = Integer.parseInt(operation.split(" ")[1]);
deque.addRear(x);
} else if (operation.equals("removeFront")) {
System.out.println(deque.removeFront());
} else if (operation.equals("removeRear")) {
System.out.println(deque.removeRear());
}
}
sc.close();
}
}
난이도 중: 슬라이딩 윈도우 최대값
정수 배열과 윈도우 크기 k가 주어진다. 크기 k의 슬라이딩 윈도우가 배열을 이동하며 각 윈도우의 최대값을 구한다.
입력
첫째 줄에 N과 k가 주어진다. 둘째 줄에 N개의 정수가 주어진다.
출력
각 윈도우의 최대값을 공백으로 구분해 출력한다.
입력 예시
8 3
1 3 -1 -3 5 3 6 7
출력 예시
3 3 5 5 6 7
문제 출처: LeetCode "Sliding Window Maximum"
해답
해답 펼치기
import java.util.Scanner;
public class SlidingWindowMax {
static class LinkedDeque {
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node front;
private Node rear;
LinkedDeque() {
front = null;
rear = null;
}
void addRear(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
} else {
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
}
int removeFront() {
if (front == null) return -1;
int data = front.data;
front = front.next;
if (front == null) rear = null;
else front.prev = null;
return data;
}
int removeRear() {
if (rear == null) return -1;
int data = rear.data;
rear = rear.prev;
if (rear == null) front = null;
else rear.next = null;
return data;
}
int peekFront() {
if (front == null) return -1;
return front.data;
}
int peekRear() {
if (rear == null) return -1;
return rear.data;
}
boolean isEmpty() {
return front == null;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.nextInt();
}
int[] result = new int[N - k + 1];
LinkedDeque deque = new LinkedDeque();
for (int i = 0; i < N; i++) {
while (!deque.isEmpty() && deque.peekFront() < i - k + 1) {
deque.removeFront();
}
while (!deque.isEmpty() && nums[deque.peekRear()] < nums[i]) {
deque.removeRear();
}
deque.addRear(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFront()];
}
}
for (int max : result) {
System.out.print(max + " ");
}
System.out.println();
sc.close();
}
}
난이도 상: 회전 큐
덱에 N개의 정수가 주어진다. M개의 연산이 주어지며, 각 연산은 덱을 왼쪽 또는 오른쪽으로 회전시킨다. 모든 연산을 수행한 후 덱의 상태를 출력한다.
입력
첫째 줄에 N과 M이 주어진다. 둘째 줄에 N개의 정수가 주어진다. 다음 M줄에 “left” 또는 “right”가 주어진다.
출력
모든 연산을 수행한 후 덱의 요소를 앞에서부터 순서대로 출력한다.
입력 예시
5 2
1 2 3 4 5
left
right
출력 예시
1 2 3 4 5
문제 출처: 자체 제작
해답
해답 펼치기
import java.util.Scanner;
public class RotateDeque {
static class LinkedDeque {
class Node {
int data;
Node prev;
Node next;
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
private Node front;
private Node rear;
LinkedDeque() {
front = null;
rear = null;
}
void addRear(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
} else {
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
}
int removeFront() {
if (front == null) return -1;
int data = front.data;
front = front.next;
if (front == null) rear = null;
else front.prev = null;
return data;
}
int removeRear() {
if (rear == null) return -1;
int data = rear.data;
rear = rear.prev;
if (rear == null) front = null;
else rear.next = null;
return data;
}
void addFront(int data) {
Node newNode = new Node(data);
if (front == null) {
front = rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
}
boolean isEmpty() {
return front == null;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
LinkedDeque deque = new LinkedDeque();
for (int i = 0; i < N; i++) {
deque.addRear(sc.nextInt());
}
sc.nextLine();
for (int i = 0; i < M; i++) {
String operation = sc.nextLine();
if (operation.equals("left")) {
int front = deque.removeFront();
deque.addRear(front);
} else if (operation.equals("right")) {
int rear = deque.removeRear();
deque.addFront(rear);
}
}
while (!deque.isEmpty()) {
System.out.print(deque.removeFront() + " ");
}
System.out.println();
sc.close();
}
}
마무리
덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 큐와 스택의 기능을 모두 제공한다. 배열 기반과 연결 리스트 기반의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 ArrayDeque와 LinkedList를 통해 대안을 살펴봤다.
'코딩 공부 > 알고리즘(자바)' 카테고리의 다른 글
| 기본 자료구조 - 집합 (Set) (0) | 2025.05.09 |
|---|---|
| 기본 자료구조 - 해시 테이블 (Hash Table) (0) | 2025.05.08 |
| 기본 자료구조 - 큐 (Queue) (1) | 2025.05.04 |
| 기본 자료구조 - 스택 (Stack) (0) | 2025.05.03 |
| 기본 자료구조 - 연결 리스트 (Linked List) (1) | 2025.05.03 |