jdk 8 소스 의 Queue

대기 열 이라는 데이터 구조 에 대해 서 는 모두 가 비교적 잘 알 고 있 을 것 이다.대열 은 선진 선 출 (FIFO) 의 데이터 구조 다.삭제 작업 은 표 의 머리 에 만 있 고 삽입 작업 은 표 의 끝 에 만 있 습 니 다.Queue 는 일반적으로 버퍼 대기 열 로 사 용 됩 니 다. 간단 한 예 를 들 어 생산 업 체 의 생산 속 도 는 가끔 소비 업 체 의 소비 속도 보다 클 수 있 지만 상대방 을 기다 리 고 싶 지 않 습 니 다. 이때 캐 시 대기 열 같은 문제 가 있 으 면 해 결 됩 니 다.생산 단 에서 생산 하 는 것 은 캐 시 대기 열 에 만 넣 고 소비 단 은 캐 시 대기 열 에서 물건 을 가 져 와 버퍼 의 목적 을 달성 합 니 다.LinkedList 는 링크 를 바탕 으로 이 루어 지고 Array Queue 는 배열 을 바탕 으로 이 루어 집 니 다.다음은 이 Array Queue 자의 소스 코드 실현 에 대해 말씀 드 리 겠 습 니 다.
ArrayQueue

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
 //         
 transient Object[] elements; 
 //   
 transient int head;
 //   
 transient int tail;
 //      
 private static final int MIN_INITIAL_CAPACITY = 8;

 }

ArrayQueue 초기 화

//      ，   16
public ArrayDeque() {
        elements = new Object[16];
    }
//      
public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
//     
public ArrayDeque(Collection extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }
//      8 ，  8
//  ，  initialCapacity=2^n，2^n   ，  2^30
private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = new Object[initialCapacity];
    }

ArrayQueue-offer()

 //         true，      ，   false
 public boolean offer(E e) {
        return offerLast(e);
    }
 public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
 //         
 public void addLast(E e) {
     if (e == null)
         throw new NullPointerException();
     //       
     elements[tail] = e;
     //   tail+1,  tail elements    
     //  ：    8，tail+1=8， tail=0
     // tail==head ，       ，      
     if ( (tail = (tail + 1) & (elements.length - 1)) == head)
         doubleCapacity();
  }
 //    
 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
    //   =    *2
    int newCapacity = n << 1;
    //     ，  
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    //            
    Object[] a = new Object[newCapacity];
    // elements   a 
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    //  ：         ，  tail=n
    //         ，       
    tail = n;
}

ArrayQueue-poll()

 //          ，      ，  null
 public E poll() {
        return pollFirst();
    }
 public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        //   ‘  ’       null
        elements[h] = null;     
        head = (h + 1) & (elements.length - 1);
        return result;
    }

ArrayQueue-peek()

 //      ，      ，  null
 public E peek() {
        return peekFirst();
    }
 public E peekFirst() {
        //   head     ，   null
        return (E) elements[head];
    }
 //      ,   null，  
 public E element() {
        return getFirst();
    }
 public E getFirst() {
  //      
  @SuppressWarnings("unchecked")
  E result = (E) elements[head];
  //   null，  
  if (result == null)
      throw new NoSuchElementException();
  return result;
 }

ArrayQueue-remove(e)

   //         ，   null，   
   //  poll()  ，           
   public E remove() {
        return removeFirst();
    }
  public E removeFirst() {
       E x = pollFirst();
       if (x == null)
           throw new NoSuchElementException();
       return x;
   }

ArrayQueu-add(e)

  //         （   ，   ）
  public boolean add(E e) {
        addLast(e);
        return true;
    }
 public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        //tail    
        //      ，  
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

ArrayQueu-push(e)

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

ArrayQueue-spliterator()
Array Queue 의 병렬 스 트 리밍 이 어떻게 이 루어 졌 는 지

 public Spliterator spliterator() {
        return new DeqSpliterator(this, -1, -1);
    }
static final class DeqSpliterator<E> implements Spliterator<E> {
        private final ArrayDeque deq;
        //   ，index        
        private int fence;  // -1        
        //      
        private int index;  // current index, modified on traverse/split

        DeqSpliterator(ArrayDeque deq, int origin, int fence) {
            this.deq = deq;
            this.index = origin;
            this.fence = fence;
        }
        //      
        private int getFence() { // force initialization
            int t;
            if ((t = fence) < 0) {
            //       ，  index fence  
                t = fence = deq.tail;
                index = deq.head;
            }
            return t;
        }
        //  ，  head   tail ，            
        public DeqSpliterator trySplit() {
            int t = getFence(), h = index, n = deq.elements.length;
            //h == t       
            //(h + 1) & (n - 1)) == t         
            if (h != t && ((h + 1) & (n - 1)) != t) {
                //h > t   head>tail 
                if (h > t)
                    t += n;
                //  m   
                //  ：n：8，head：6，tail:4
                //   t=4+8=12
                // m =（（6+12）>>>1)&（8-1）=1
                int m = ((h + t) >>> 1) & (n - 1);
                return new DeqSpliterator<>(deq, h, index = m);
            }
            return null;
        }
        public void forEachRemaining(Consumer super E> consumer) {
                    if (consumer == null)
                        throw new NullPointerException();
                    Object[] a = deq.elements;
                    int m = a.length - 1, f = getFence(), i = index;
                    index = f;
                    while (i != f) {
                        @SuppressWarnings("unchecked") E e = (E)a[i];
                        i = (i + 1) & m;
                        //   ，  ‘    ’，e   null
                        if (e == null)
                            throw new ConcurrentModificationException();
                        consumer.accept(e);
                    }
                }
        ...
       //   
        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED |
                Spliterator.NONNULL | Spliterator.SUBSIZED;
        }
    }

}

Array Queue 의 병렬 교체 기 는 특별한 것 이 없 음 을 볼 수 있 습 니 다. 다만 우리 가 예전 에 본 Array List, HashMap 등 데이터 구 조 는 모두 modCount 를 통 해 빠 른 실 패 를 보장 하 는 것 이 고 Array Queue 는 여러 번 겪 었 지만 구조 가 변경 되 어 반드시 잘못 던 지 는 것 은 아 닙 니 다!
Array Queue 소결
이 를 통 해 알 수 있 듯 이 Array Queue 의 내 부 는 하나의 배열 을 바탕 으로 이 루어 진 것 으로 두 개의 포인터 head 와 tail 을 통 해 각각 머리 끝 과 끝 을 가리 키 며 head 와 tail 이 같 을 때 용량 이 가득 찼 음 을 설명 하 며 이때 확장 작업 을 할 것 이다.또한, Array Queue 의 사용 장면 을 생각해 볼 수 있 습 니 다!

jdk 8 소스 의 Queue - Array Queue

좋은 웹페이지 즐겨찾기