ArrayDeque 개요 ArrayDeque는 双端큐(Double-Ended Queue)의 구현체로, 내부적으로 배열을 사용하여 데이터를 저장합니다. 내부 배열은 환형(cyclic) 구조로 동작하여 효율적인 메모리 활용이 가능합니다.
상속 구조 ArrayDeque 클래스는 Deque 인터페이스를 구현합니다. Deque 인터페이스는 양쪽 끝에서 자유롭게 데이터를 추가하고 제거할 수 있는 연산을 제공합니다.
Deque 인터페이스 Deque는 Queue를 확장한 인터페이스로, 양단에서의 삽입과 삭제를 지원합니다.
public interface Deque<E> extends Queue<E> {
// 앞쪽에 요소 추가
void addFirst(E e);
// 뒤쪽에 요소 추가
void addLast(E e);
// 앞쪽에 요소 추가 (성공 시 true,容量不足 시 false)
boolean offerFirst(E e);
// 뒤쪽에 요소 추가 (성공 시 true,容量不足 시 false)
boolean offerLast(E e);
// 앞쪽에서 요소 제거
E removeFirst();
// 뒤쪽에서 요소 제거
E removeLast();
// 앞쪽에서 요소 제거 (비어있으면 null 반환)
E pollFirst();
// 뒤쪽에서 요소 제거 (비어있으면 null 반환)
E pollLast();
// 앞쪽 요소 조회
E getFirst();
// 뒤쪽 요소 조회
E getLast();
// 앞쪽 요소 조회 (비어있으면 null)
E peekFirst();
// 뒤쪽 요소 조회 (비어있으면 null)
E peekLast();
// 앞쪽부터 특정 요소 제거
boolean removeFirstOccurrence(Object o);
// 뒤쪽부터 특정 요소 제거
boolean removeLastOccurrence(Object o);
// 요소 추가 (addLast와 동일)
boolean add(E e);
// 요소 추가 (offerLast와 동일)
boolean offer(E e);
// 요소 제거 (removeFirst와 동일)
E remove();
// 요소 제거 (pollFirst와 동일)
E poll();
// 요소 조회 (getFirst와 동일)
E element();
// 요소 조회 (peekFirst와 동일)
E peek();
// 스택 연산
void push(E e);
E pop();
}
Queue 인터페이스는 다음과 같습니다:
public interface Queue<E> extends Collection<E> {
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
}
Queue 인터페이스의 메서드는 두 가지 관점으로 나뉩니다:
- 리스트 관점: add, remove, element - 실패 시 예외 발생
- 큐 관점: offer, poll,peek - 실패 시 false 또는 null 반환
Deque는 여기에 양쪽 끝操作的 개념을 추가하여, 모든 메서드가 first와 last 버전으로 나뉩니다:
요소 추가 메서드
- addFirst(E e): 배열 시작 위치에 요소 추가
- addLast(E e): 배열 끝 위치에 요소 추가
- offerFirst(E e): 배열 시작에 추가, 성공 여부 반환
- offerLast(E e): 배열 끝에 추가, 성공 여부 반환
요소 제거 메서드
- removeFirst(): 시작 요소 제거 및 반환, 비어있으면 예외
- removeLast(): 끝 요소 제거 및 반환, 비어있으면 예외
- pollFirst(): 시작 요소 제거 및 반환, 비어있으면 null
- pollLast(): 끝 요소 제거 및 반환, 비어있으면 null
요소 조회 메서드
- getFirst(): 시작 요소 반환, 비어있으면 예외
- getLast(): 끝 요소 반환, 비어있으면 예외
- peekFirst(): 시작 요소 반환, 비어있으면 null
- peekLast(): 끝 요소 반환, 비어있으면 null
주요 필드
// 요소를 저장하는 배열
transient Object[] data;
transient int front;
transient int rear;
private static final int INIT_CAPACITY = 8;
ArrayDeque는 front와 rear 두 개의 포인터를 사용하여 큐의 양쪽 끝을 관리합니다. rear 포인터는 front보다 앞에 위치할 수 있으며, 이는 환형 배열을 통해 논리적으로 표현됩니다.
생성자
// 기본 생성자, 초기容量 16
public ArrayDeque() {
data = new Object[16];
}
// 指定容量으로 초기화
public ArrayDeque(int capacity) {
allocate(capacity);
}
// 컬렉션으로 초기화
public ArrayDeque(Collection<? extends E> collection) {
allocate(collection.size());
addAll(collection);
}
// 배열 할당
private void allocate(int size) {
data = new Object[computeCapacity(size)];
}
// 주어진 크기 이상의 최소 2의 거듭제곱 계산
private static int computeCapacity(int size) {
int capacity = INIT_CAPACITY;
if (size >= capacity) {
capacity = size;
capacity |= (capacity >>> 1);
capacity |= (capacity >>> 2);
capacity |= (capacity >>> 4);
capacity |= (capacity >>> 8);
capacity |= (capacity >>> 16);
capacity++;
if (capacity < 0) {
capacity >>>= 1;
}
}
return capacity;
}
핵심 메서드
삽입 메서드 Queue 인터페이스의 add/offer 메서드는 내부적으로 Deque의 해당 메서드를 호출합니다:
public boolean add(E element) {
addLast(element);
return true;
}
public boolean offer(E element) {
return offerLast(element);
}
public boolean offerFirst(E element) {
addFirst(element);
return true;
}
public boolean offerLast(E element) {
addLast(element);
return true;
}
//_front에서_Enqueue
public void addFirst(E element) {
if (element == null) {
throw new NullPointerException();
}
data[front = (front - 1) & (data.length - 1)] = element;
if (front == rear) {
expandCapacity();
}
}
// rear에서_Enqueue
public void addLast(E element) {
if (element == null) {
throw new NullPointerException();
}
data[rear] = element;
if ((rear = (rear + 1) & (data.length - 1)) == front) {
expandCapacity();
}
}
배열扩容 로직:
private void expandCapacity() {
assert front == rear;
int position = front;
int length = data.length;
int rightSide = length - position;
int newLength = length << 1;
if (newLength < 0) {
throw new IllegalStateException("Deque capacity overflow");
}
Object[] newArray = new Object[newLength];
System.arraycopy(data, position, newArray, 0, rightSide);
System.arraycopy(data, 0, newArray, rightSide, position);
data = newArray;
front = 0;
rear = length;
}
제거 메서드
public E remove() {
return removeFirst();
}
public E poll() {
return pollFirst();
}
public E removeFirst() {
E item = pollFirst();
if (item == null) {
throw new NoSuchElementException();
}
return item;
}
public E removeLast() {
E item = pollLast();
if (item == null) {
throw new NoSuchElementException();
}
return item;
}
// front에서 Dequeue
public E pollFirst() {
int f = front;
@SuppressWarnings("unchecked")
E result = (E) data[f];
if (result == null) {
return null;
}
data[f] = null;
front = (f + 1) & (data.length - 1);
return result;
}
// rear에서 Dequeue
public E pollLast() {
int r = (rear - 1) & (data.length - 1);
@SuppressWarnings("unchecked")
E result = (E) data[r];
if (result == null) {
return null;
}
data[r] = null;
rear = r;
return result;
}
조회 메서드
public E element() {
return getFirst();
}
public E peek() {
return peekFirst();
}
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) data[front];
if (result == null) {
throw new NoSuchElementException();
}
return result;
}
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) data[(rear - 1) & (data.length - 1)];
if (result == null) {
throw new NoSuchElementException();
}
return result;
}
public E peekFirst() {
return (E) data[front];
}
public E peekLast() {
return (E) data[(rear - 1) & (data.length - 1)];
}
특징 정리 ArrayDeque는 Deque 인터페이스를 구현하여 큐의 양쪽 끝에서 자유롭게 데이터를 조작할 수 있습니다. 내부적으로 배열을 사용하며, 환형 버퍼 방식을 통해 front와 rear 포인터로 관리합니다. rear가 front를追赶하는 경우容量을 두 배로 확장하며, 성능 최적화를 위해容量은 항상 2의 거듭제곱을 유지합니다. null 요소는 허용하지 않습니다.