[Java] ArrayDeque

📌 Java의 ArrayDeque란?

 

ArrayDeque(배열 기반 덱, Double-Ended Queue)은 양쪽에서 삽입과 삭제가 가능한 자료구조로, 배열(Array) 기반으로 동작하는 덱(Deque) 임.

 

✅ 특징

• 양방향 삽입/삭제 가능 → addFirst(), addLast(), removeFirst(), removeLast()

• 빠른 성능 → ArrayList보다 요소 추가/삭제가 빠름 (LinkedList보다도 빠를 수 있음)

• 크기 제한 없음 → 동적으로 크기 조절 가능

• 스택(LIFO), 큐(FIFO)로 모두 사용 가능

• null 저장 불가 → NullPointerException 발생

 

---

1️⃣ ArrayDeque 선언 및 기본 사용법

 

📌 ArrayDeque 선언

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // 요소 추가 (맨 앞 & 맨 뒤)
        deque.addFirst(1);  // [1]
        deque.addLast(2);   // [1, 2]
        deque.addLast(3);   // [1, 2, 3]

        System.out.println(deque); // 출력: [1, 2, 3]

        // 요소 제거
        System.out.println(deque.removeFirst()); // 1 제거
        System.out.println(deque.removeLast());  // 3 제거

        System.out.println(deque); // 출력: [2]
    }
}

 

 

---

2️⃣ ArrayDeque 주요 메서드

 

📌 Deque의 핵심 메서드 정리

메서드	설명
addFirst(E e)	맨 앞에 요소 추가
addLast(E e)	맨 뒤에 요소 추가
removeFirst()	맨 앞 요소 제거
removeLast()	맨 뒤 요소 제거
peekFirst()	맨 앞 요소 확인 (삭제 X)
peekLast()	맨 뒤 요소 확인 (삭제 X)
pollFirst()	맨 앞 요소 가져오고 제거 (비어있으면 null 반환)
pollLast()	맨 뒤 요소 가져오고 제거 (비어있으면 null 반환)

 

 

---

3️⃣ ArrayDeque를 스택(Stack)처럼 사용 (LIFO)

 

📌 후입선출(LIFO: Last-In-First-Out) 구조

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

public class StackExample {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();

        // 스택처럼 사용 (push, pop)
        stack.push("A"); // [A]
        stack.push("B"); // [B, A]
        stack.push("C"); // [C, B, A]

        System.out.println(stack.pop()); // C 제거
        System.out.println(stack.pop()); // B 제거
        System.out.println(stack);       // 출력: [A]
    }
}

 

✅ 결과

C
B
[A]

push() → addFirst()와 동일

pop() → removeFirst()와 동일

 

---

4️⃣ ArrayDeque를 큐(Queue)처럼 사용 (FIFO)

 

📌 선입선출(FIFO: First-In-First-Out) 구조

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

public class QueueExample {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();

        // 큐처럼 사용 (offer, poll)
        queue.offer("A"); // [A]
        queue.offer("B"); // [A, B]
        queue.offer("C"); // [A, B, C]

        System.out.println(queue.poll()); // A 제거
        System.out.println(queue.poll()); // B 제거
        System.out.println(queue);        // 출력: [C]
    }
}

 

✅ 결과

A
B
[C]

offer(E e) → addLast(E e)와 동일

poll() → removeFirst()와 동일

 

---

5️⃣ ArrayDeque vs LinkedList vs Stack 비교

비교 항목	ArrayDeque	LinkedList	Stack
구조	배열 기반 덱(Deque)	이중 연결 리스트	벡터(Vector) 기반
삽입 속도	빠름	느림 (노드 할당 필요)	느림
삭제 속도	빠름	느림	느림
메모리 사용	적음	많음 (노드마다 포인터 필요)	많음
스택 사용 가능?	✅ 가능 (push, pop)	✅ 가능	✅ 가능
큐 사용 가능?	✅ 가능 (offer, poll)	✅ 가능	❌ 불가능
멀티스레드 안전성	❌ (동기화 없음)	❌	✅ (Vector 기반)

 

✅ 정리하면

• 빠른 성능이 필요하면 → ArrayDeque

• 리스트처럼 사용할 경우 → LinkedList

• 멀티스레드 환경이면 → Stack 대신 ConcurrentLinkedDeque 사용 추천

 

---

6️⃣ ArrayDeque의 장점과 단점

 

✅ 장점

• 빠른 삽입/삭제 연산 (O(1)) → 배열 기반이라 LinkedList보다 빠름.

• 동적 크기 조절 가능 → 크기가 자동 증가됨.

• Stack, Queue 대체 가능 → 하나의 자료구조로 여러 기능 수행 가능.

 

❌ 단점

• 멀티스레드 환경에서 안전하지 않음 → 동기화 필요.

• 중간 삽입/삭제가 비효율적 → LinkedList보다 중간 삽입/삭제가 느림.

• null을 저장할 수 없음 → NullPointerException 발생 가능.

 

---

7️⃣ ArrayDeque의 실제 활용 예시

 

✅ BFS (너비 우선 탐색) 구현

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class BFSExample {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();

        queue.offer("Start");

        while (!queue.isEmpty()) {
            String node = queue.poll();
            if (visited.contains(node)) continue;

            System.out.println("방문: " + node);
            visited.add(node);

            // 임의의 다음 노드 추가 (예제)
            queue.offer("A");
            queue.offer("B");
        }
    }
}

 

✅ 결과

방문: Start
방문: A
방문: B

 

 

---

🔎 결론: 언제 ArrayDeque을 사용해야 할까?

 

✅ 사용하면 좋은 경우

• 스택(Stack) 또는 큐(Queue)로 활용할 때 (push/pop, offer/poll 지원)

• 빠른 삽입/삭제가 필요한 경우 (LinkedList보다 성능이 우수함)

• 멀티스레드가 필요 없는 환경에서 성능 최적화가 필요할 때

 

❌ 사용하면 비효율적인 경우

• 중간 삽입/삭제가 빈번한 경우 (LinkedList가 더 적합)

• 멀티스레드 환경에서 안전하게 사용하려면 → ConcurrentLinkedDeque 사용 추천

 

 

 

 

출처 : ChatGPT