Java 대기 열 큐,Deque,AbstractQueue 소스 코드 분석

소스 코드 는 모두 JDK 8 을 참고 로 한다.
JDK 1.5Collection 집합 프레임 재 구성 에 서 는 큐(Queue)라 는 개념 을 도입 하 는 한편 JDK 1.6 에 서 는 양 끝 큐(Deque)라 는 개념 을 도입 했다.
1.Queue 프로필:
Queue:Queue 는 선진 적 인 선 출(FIFO)대기 열의 약속 을 실 현 했 고 Queue 역시 Collection 인 터 페 이 스 를 실 현 했 으 며 인터페이스 에서 일련의 FIFO 대기 열의 기본 동작 을 정의 했다.
Queue 의 조작 은 두 가지 로 나 뉘 는데 이 두 가지 방법 은 실패 조작 을 처리 하 는 데 차이 가 있 습 니 다.구체 적 으로 다음 과 같 습 니 다.
boolean add(E e) boolean offer(E e):：
대기 열 끝 에 요 소 를 추가 합 니 다.크기 를 제한 하 는 대기 열 에 대해 서 는 대기 열 이 가득 찼 을 때 요소 의 가입 을 거부 합 니 다.add 는 이상 을 던 지고 offer 는 false 로 돌아 가지 만 이상 을 던 지지 않 습 니 다.
E remove() E poll()：
하나의 요 소 를 제거 합 니 다.빈 대기 열 을 조작 할 때 reove 는 이상 을 던 지고 poll 은 null 로 돌아 가 이상 을 던 지지 않 습 니 다.
E element() E peek()：
대기 열 머리 요 소 를 가 져 옵 니 다.빈 대기 열 을 조작 할 때 element 는 이상 을 던 지고 peek 는 null 로 돌아 가 이상 을 던 지지 않 습 니 다.
2.Deque 프로필:
양 끝 에 요 소 를 삽입 하고 제거 하 는 선형 collection이름 Deque 는'double ended quue',즉 양 끝 대기 열 이라는 뜻 입 니 다.Deque 는 Queue 인터페이스 에서 계승 하기 때문에 이 연결 을 합 니 다.
입 은 용량 제한 이 있 는 양단 대기 열 일 수도 있 고,고정 크기 제한 이 없 는 양단 대기 열 일 수도 있다.
이 인 터 페 이 스 는 주로 양 단 대기 열 양쪽 에서 요 소 를 방문 하 는 방법 을 정의 합 니 다.요 소 를 삽입,제거,검사 하 는 방법 을 제공 합 니 다.Queue 인터페이스의 디자인 형식 에 따라 모든 방법 에는 두 가지 형식 이 존재 합 니 다.하 나 는 조작 실패 입 니 다.
이상 을 던 지고 다른 하 나 는 특수 값(null 또는 false)을 되 돌려 줍 니 다.이러한 메커니즘 에 대해 다음 글 은 더 이상 군말 하지 않 습 니 다.
Deque 의 방법 약정 안내:
addFirst(E)offerFirst(E):양 끝 대기 열 머리 에 요 소 를 추가 합 니 다.
addLast(E)offerLast(E):양 끝 대기 열 끝 에 요소 추가
removeFirst()pollFirst():양 끝 대기 열 머리 제거 요소
removeLast()pollLast():양 끝 대기 열 끝 에서 요 소 를 제거 합 니 다.
getFirst()peekFirst():양쪽 대기 열 머리 요 소 를 가 져 옵 니 다.
getLast()peekLast():양 끝 대기 열 꼬리 요 소 를 가 져 옵 니 다.
removeFirstOccurrence(Object):이 두 단 대기 열 에서 처음 나타 난 지정 요 소 를 제거 합 니 다.
removeLastOccurrence(Object):이 두 단 대기 열 에서 마지막 으로 나타 난 지정 요 소 를 제거 합 니 다.
다시 정의 Queue 인터페이스 방법 정의:
boolean add(E e) boolean offer(E e)：
E remove() E poll(): 
E element() E peek(): 
창고 의 조작 을 모방 하여 후진 선 출(LIFO)하고 다음 과 같은 방법 을 제공 합 니 다.
push(E):이 양 끝 대기 열 에 표 시 된 스 택 에 요 소 를 밀어 넣 습 니 다.(다시 말 하면 이 양 끝 대기 열의 머리)용량 제한 을 위반 하지 않 고 직접 이렇게 할 수 있다 면;성공 하면 true 로 돌아 갑 니 다.
현재 사용 가능 한 공간 이 없 으 면 IllegalState Exception 을 던 집 니 다.
pop(E):이 두 단 대기 열 에 표 시 된 스 택 에서 원 소 를 팝 업 합 니 다.팝 업 요소 의 위 치 는 두 단 대기 열의 머리 입 니 다.
Collection 인터페이스 에서 방법 정의:
remove(Object):양 끝 대기 열 에서 요 소 를 제거 합 니 다.
contains(Object):양 끝 대기 열 에 요소 가 포함 되 어 있 는 지 판단 합 니 다.
size():양 끝 대기 열 요소 갯 수 를 되 돌려 줍 니 다.
iterator():양 끝 대기 열 교체 기 를 되 돌려 줍 니 다.
descendingIterator():이 deque 대기 열의 순서 가 반대 되 는 요 소 를 되 돌려 줍 니 다.
3.AbstractQueue 소개:
이 동시에 Queue 인터페이스 에서 AbstractQueue 는 Queue 인 터 페 이 스 를 실현 했다.이 추상 류 에서 Queue 에서 정 의 된 방법 서명 에 대해 간단 한 실현 을 했다.예 를 들 어:
    이 를 통 해 알 수 있 듯 이 Queue 가 가지 고 있 는 두 가지 형식의 조작 방법 에 대해 서로 호출 되 었 다.
add：

public boolean add(E e) {
    if (offer(e))
        return true;
    else
        throw new IllegalStateException("Queue full");
}

remove：

public E remove() {
    E x = poll();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

element：

public E element() {
    E x = peek();
    if (x != null)
        return x;
    else
        throw new NoSuchElementException();
}

요약:주로 대기 열(Queue)과 쌍 단 대기 열(Deque)의 인터페이스 약속 을 소개 하 는 동시에 AbstractQueue 에서 Queue 의 방법 약속 에 대해 간단 한 실현 을 소개 했다.Queue 가 제공 합 니 다.
   하위 인터페이스 Deque 에서 쌍 단 대기 열과 창고(LIFO)의 실현 을 실현 하 는 고전적 인 대기 열(FIFO)
   이러한 데이터 구조의 실현 은 자바 가 실현 하 는 집합 구조 에 기본 적 인 실현 이 더 많아 졌 다.
다음 편:대기 열의 구체 적 인 실현 클래스 인 Array Deque 와 Priority Queue 를 소개 합 니 다.