자바 집합 Array Deque 클래스 해독

머리말
Array Deque 류 는 양 끝 대기 열의 실현 유형 으로 다음 과 같은 계승 구 조 는 AbastractCollection(이 종 류 는 일부 집합 이 통용 되 는 방법 을 실 습 했 고 Collection 인 터 페 이 스 를 실현 했다)에서 계승 되 었 다.이 를 실현 하 는 인터페이스 Deque 인터페이스 에서 양 끝 대기 열의 주요 방법 을 정의 했다.예 를 들 어 처음부터 삭제 하고 꼬리 에서 삭제 하 며 머리 데 이 터 를 얻 고 꼬리 데 이 터 를 얻 는 등 이다.

public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable

ArrayDeque 기본 특징
이 를 실현 하 는 데 있어 Array Deque 는 순환 배열 방식 으로 쌍 단 대기 열 을 완성 하 는 기능 을 사용 했다.1.무한 확장,자동 으로 대기 열 크기 를 확장 합 니 다.(물론 메모리 가 넘 치지 않 는 상황 에서.)2.비 스 레 드 가 안전 하고 동시 방문 과 수정 은 지원 되 지 않 습 니 다.3.fast-fail 을 지원 합 니 다.4.스 택 으로 사용 하면 스 택 보다 빠 릅 니 다.5.대기 열 에서 사용 하 는 것 이 linklist 보다 빠 릅 니 다.6.null 요 소 는 사용 이 금지 되 어 있 습 니 다.
Array Deque 실현 방법 해독
최소 초기 화 용량 제한

    /** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */
    private static final int MIN_INITIAL_CAPACITY = 8;

여기에 주석 에서 언급 한 바 에 의 하면 반드시 2 의 幂 次 여야 한다.단지 이곳 을 통 해서 만 왜 이렇게 설정 해 야 하 는 지 알 수 없다.

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

addFirst 방법 에 서 는 head-1 과 length-1 이 일치 하 는 형식 으로 계산 되 었 습 니 다.그러면 length-1 은 여기 가 얼마 인지 규정 되 어 있 습 니 다.length 는 반드시 2 의 멱 차 가 되 어야 하기 때문에 length-1 후 이 진 저 위 는 모두 1 이 고 그 다음 에 head-1 과 함께 모델 링 을 하 는 것 과 같 습 니 다.
용량 을 늘리다
이 Array Deque 용량 이 무제 한 이 라 고 말 하 는 이 유 는 head=tail 이 감지 되면 doubleCapacity 방법 을 직접 호출 하여 확장 하기 때문이다.이 럴 때 배열 을 펼 칩 니 다.head 와 tail 은 같은 위 치 를 가리 키 고 있 습 니 다.그러면 순환 배열 이기 때문에 head 왼쪽 에 일부 요소 가 p 개 로 존재 할 수 있 습 니 다.오른쪽 에 일부 데이터 r=n-p 개가 존재 할 수도 있 습 니 다.오른쪽 부분 은 0 에서 r 로 복사 되 고 왼쪽 부분 은 r 에서 끝까지 복사 할 수 있 습 니 다.이렇게 원래 의 데 이 터 는 0 부터 아래로 배열 된다.

    private void doubleCapacity() {
        assert head == tail; 
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
    }

요소 삭제
요 소 를 삭제 하 는 기본 적 인 사 고 는 그 측의 데이터 가 적 고 적은 측 이동 요소 의 위 치 를 확인 하기 위해 효율 이 비교적 높 지 않다.그 다음 에 head 가 최대 치 를 뛰 어 넘 는 지,아니면 최대 치 를 뛰 어 넘 는 지 판단 한 다음 에 두 가지 서로 다른 상황 으로 나 누 어 복사 할 수 있다.그러나 이 방법 은 배열 의 복사 가 존재 하기 때문에 비교적 느리다.

    private boolean delete(int i) {
        checkInvariants();
        final E[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        final int front = (i - h) & mask;
        final int back  = (t - i) & mask;

        // Invariant: head <= i < tail mod circularity
        if (front >= ((t - h) & mask))
            throw new ConcurrentModificationException();

        // Optimize for least element motion
        //          
        if (front < back) {
            //       
            if (h <= i) {
                //            
                System.arraycopy(elements, h, elements, h + 1, front);
            } else { // Wrap around
                //         
                //      
                System.arraycopy(elements, 0, elements, 1, i);
                //          
                elements[0] = elements[mask];
                //            
                System.arraycopy(elements, h, elements, h + 1, mask - h);
            }
            elements[h] = null;
            head = (h + 1) & mask;
            return false;
        } else {
            //       
            if (i < t) { // Copy the null tail as well
                //   i         
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } else { // Wrap around
                //           
                //       
                // 0               
                //       1        ，   1 0 
                System.arraycopy(elements, i + 1, elements, i, mask - i);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, t);
                tail = (t - 1) & mask;
            }
            return true;
        }
    }

요소 가 져 오기 및 삭제
여기 서 간단 한 예 를 들 어 중간 에 null 인지 아 닌 지 를 판단 하면 이 대기 열 은 null 을 지원 하지 않 음 을 알 수 있 습 니 다.그 값 을 null 로 설정 하면 삭제 하 더 라 도.그리고 헤드 는 점점 늘 어 나 는 방향 으로 한 명 만 물 러 나 면 됩 니 다.

    public E pollFirst() {
        int h = head;
        E result = elements[h]; // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }