ArrayDeque : 자바에서 Stack, Queue, Deque를 구현할 수 있는 클래스

Java에서는 기본적인(우선순위가 없는) Stack, Queue, Deque를 구현하기 위해서 가장 많이 사용하는 클래스는 ArrayDeque이다.

그 이유는, Java에서는 Stack 클래스가 오래된 구현체이기 때문에, 좋은 성능을 보이지 못한다. 따라서, Java에서는 Stack 자료구조를 사용할 때 Deque를 대신해서 사용한다.

또한 ArrayDeque를 충분히 Queue처럼 사용이 가능하기 때문에, 범용적으로 사용한다.

Deque 인터페이스의 대표적인 구현체

특징	ArrayDeque	LinkedList
기반 구조	배열	연결 리스트
성능	삽입/삭제/조회 대부분이 O(1).	삽입/삭제: O(1), 조회: O(n).
메모리 사용량	적음(배열 사용).	많음(노드 객체 추가).
null 허용 여부	허용하지 않음.	허용.
스레드 안전성	스레드 안전하지 않음.	스레드 안전하지 않음.
주요 사용 사례	일반적인 큐, 스택, 덱 구현.	삽입/삭제가 많은 작업이 필요한 경우.

💡결론적으로, 간단한 Stack, Queue, Deque를 구현하고 싶다면 ArrayDeque를 사용해서 구하면 손쉽게 구현을 할 수 있다.

---

ArrayDeque에서 사용하는 함수

ArrayDeque는 Stack, Queue, Deque 로 사용할 수 있다. 물론 아래처럼 경우에 따라 나누어서 이용해야지만 그 자료구조 처럼 사용할 수 있는 것은 아니다.

그렇지만, 구현할 때 경우에 따라서 함수를 다르게 나누어서 사용할 수 있다는 것을 인지하면 좋겠다는 생각에 나누어 정리했다.

1. 큐(Queue)처럼 사용

FIFO(First-In-First-Out) 구조로, 요소를 뒤에 추가하고 앞에서 제거

메서드	역할	동작 설명	시간 복잡도
add(E e)	요소 추가	큐의 뒤쪽에 요소 추가	O(1)
offer(E e)	요소 추가	큐의 뒤쪽에 추가(실패 시 false)	O(1)
remove()	요소 제거	큐의 앞쪽 요소 제거	O(1)
poll()	요소 제거	큐의 앞쪽 요소 제거(비어 있으면 null)	O(1)
peek()	요소 확인	큐의 앞쪽 요소 반환(제거 X)	O(1)

2. 덱(Deque)처럼 사용

양쪽에서 삽입 및 제거가 가능한 구조로, 양방향 작업을 제공

메서드	역할	동작 설명	시간 복잡도
addFirst(E e)	앞에 요소 추가	덱의 앞쪽에 요소 추가	O(1)
addLast(E e)	뒤에 요소 추가	덱의 뒤쪽에 요소 추가	O(1)
offerFirst(E e)	앞에 요소 추가	덱의 앞쪽에 요소 추가(실패 시 false)	O(1)
offerLast(E e)	뒤에 요소 추가	덱의 뒤쪽에 요소 추가(실패 시 false)	O(1)
removeFirst()	앞의 요소 제거	덱의 앞쪽 요소 제거	O(1)
removeLast()	뒤의 요소 제거	덱의 뒤쪽 요소 제거	O(1)
pollFirst()	앞의 요소 제거	덱의 앞쪽 요소 제거(비어 있으면 null)	O(1)
pollLast()	뒤의 요소 제거	덱의 뒤쪽 요소 제거(비어 있으면 null)	O(1)
getFirst()	앞의 요소 확인	덱의 앞쪽 요소 반환(제거 X)	O(1)
getLast()	뒤의 요소 확인	덱의 뒤쪽 요소 반환(제거 X)	O(1)
peekFirst()	앞의 요소 확인	덱의 앞쪽 요소 반환(제거 X)	O(1)
peekLast()	뒤의 요소 확인	덱의 뒤쪽 요소 반환(제거 X)	O(1)

3. 스택(Stack)처럼 사용

LIFO(Last-In-First-Out) 구조로, 요소를 앞에 추가하고 앞에서 제거

메서드	역할	동작 설명	시간 복잡도
push(E e)	요소 추가	스택의 위쪽(앞쪽)에 요소 추가	O(1)
pop()	요소 제거	스택의 위쪽(앞쪽) 요소 제거	O(1)
peek()	요소 확인	스택의 위쪽(앞쪽) 요소 확인	O(1)

Summary

• 큐(Queue): FIFO, 뒤에 추가 → 앞에서 제거
  • 주요 메서드: add, offer, remove, poll, peek.
• 덱(Deque): 양방향 삽입/삭제
  • 주요 메서드: addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast.
• 스택(Stack): LIFO, 앞에 추가 → 앞에서 제거
  • 주요 메서드: push, pop, peek

---

예시

선언 방법

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

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

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

메서드 사용

deque.addFirst("hello");
deque.removeFirst();
deque.removeLast();

stack.pop();
stack.push("hello");

queue.add("hello");
queue.remove();

총정리

public class ArrayDequeExample {
    public static void main(String[] args) {
        // Deque를 양방향 큐처럼 사용
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("hello");   // 앞에 추가
        System.out.println(deque); // [hello]
        deque.removeFirst();       // 앞에서 제거
        System.out.println(deque); // []

        // Deque를 스택처럼 사용
        Deque<String> stack = new ArrayDeque<>();
        stack.push("hello");   // 스택에 추가
        System.out.println(stack); // [hello]
        stack.pop();           // 스택에서 제거
        System.out.println(stack); // []

        // Deque를 큐처럼 사용
        Deque<String> queue = new ArrayDeque<>();
        queue.add("hello");    // 큐에 추가
        System.out.println(queue); // [hello]
        queue.remove();        // 큐에서 제거
        System.out.println(queue); // []
    }
}