데이터 구조 와 알고리즘 | 대기 열의 실현 및 응용

원본 링크:https://wangwei.one/posts/jav...
앞에서 우 리 는 스 택 의 실현 과 응용 을 배 웠 습 니 다. 이 편 에서 우 리 는 마지막 선형 표 인 대열 을 배 웠 습 니 다.
대기 열 은 우리 가 일상 개발 에서 자주 사용 하 는 데이터 구조 로 우 리 는 대기 열 을 사용 하여 비동기 처리, 시스템 디 결합, 데이터 동기 화, 데이터 삭 봉, 버퍼, 흐름 제한 등 을 자주 사용 합 니 다.예 를 들 어 모든 업무 가 실시 간 으로 처리 되 어야 하 는 것 이 아니 라 모든 요구 가 실시 간 으로 결 과 를 사용자 에 게 피드백 해 야 하 는 것 이 아니 라 모든 요구 가 100% 성공 해 야 하 는 것 이 아니 라 누가 '나' 의 처리 결과 에 의존 하 는 지 모 르 고 다른 시스템 이 후속 업 무 를 어떻게 처리 하 는 지 에 관심 이 없고 강 한 일치 성 이 필요 하지 않 으 며 최종 일치 성 만 확보 하면 된다.데이터 처리 의 질서 성 을 확보 하려 면 이 문제 들 은 모두 대기 열 을 사용 하여 해결 하 는 것 을 고려 해 야 한다.
대열
정의.
대기 열 은 스 택 과 마찬가지 로 조작 이 제 한 된 선형 표 데이터 구조 입 니 다.대기 열 은 한 끝 에서 데 이 터 를 삽입 한 다음 다른 한 끝 에서 데 이 터 를 꺼 냅 니 다.데 이 터 를 삽입 하 는 한 끝 을 '팀 끝' 이 라 고 부 르 고 데 이 터 를 꺼 내 는 한 끝 을 '팀 머리' 라 고 부 릅 니 다. 그림 과 같 습 니 다.
특징.

FIFO (First In First Out): 선진 선출 원칙

분류 하 다.
스 택 과 마찬가지 로 대기 열 도 순서 대기 열 과 체인 대기 열 로 나 뉘 어 각각 배열 과 링크 를 사용 하여 이 루어 집 니 다.
체인 큐
체인 대기 열 실현 이 비교적 간단 합 니 다. 단일 체인 표를 사용 하면 실현 할 수 있 습 니 다. 만약 에 다음 과 같 으 면:
코드 구현

package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 *     
 *
 * @param 
 * @author https://wangwei.one
 * @date 2019/03/27
 */
public class LinkedQueue implements IQueue {

    private int size = 0;
    private Node head;
    private Node tail;

    public LinkedQueue() {
    }

    /**
     *          
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        Node last = tail;
        Node newNode = new Node<>(value, null);
        tail = newNode;
        if (last == null) {
            head = newNode;
        } else {
            last.next = newNode;
        }
        size++;
        return true;
    }

    /**
     *         
     *
     * @return
     */
    @Override
    public T poll() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        Node tmpHead = head;
        head = head.next;
        tmpHead.next = null;
        size--;
        if (head == null) {
            tail = null;
        }
        return tmpHead.element;
    }

    /**
     *          
     *
     * @return
     */
    @Override
    public T peek() {
        if (head == null) {
            throw new NoSuchElementException("Queue underflow");
        }
        return head.element;
    }

    /**
     *       
     */
    @Override
    public void clear() {
        for (Node x = head; x != null; ) {
            Node next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        head = tail = null;
        size = 0;
    }

    /**
     *     
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * Node
     *
     * @param 
     */
    private static class Node {
        private T element;
        private Node next;

        private Node(T element) {
            this.element = element;
        }

        private Node(T element, Node next) {
            this.element = element;
            this.next = next;
        }
    }
}

소스 코드
링크 의 실현 방식 을 바탕 으로 무한 대기 열 을 지원 하 는 무한 대기 열 (unbounded quue) 을 실현 할 수 있 으 나 너무 많은 요청 대기 열 을 초래 할 수 있 습 니 다. 요청 처리 응답 시간 이 너무 길 어 질 수 있 습 니 다.따라서 응답 시간 이 비교적 민감 한 시스템 에 대해 링크 를 바탕 으로 하 는 무한 줄 서 는 스 레 드 탱크 는 적합 하지 않다.
순서 대기 열
순서 대기 열 은 배열 로 이 루어 지고 배열 의 실현 은 두 가지 방식 이 있 으 며 하 나 는 순서 식 이 고 하 나 는 순환 배열 로 이 루어 진다.
순서 대기 열
대기 열 끝 에 남 은 공간 이 없 으 면 데이터 이전 공간 을 집중 적 으로 진행 해 야 입 대 를 계속 할 수 있 습 니 다.그림 에서 보 듯 이:
순환 대기 열
순서 대기 열 에 데이터 이전 문제 가 존재 하여 입대 작업 에 성능 적 인 영향 을 줄 수 있 습 니 다.우 리 는 순환 배열 의 방식 으로 이 문 제 를 해결 할 수 있다. 그림 과 같다.
팀 의 끝 에 저장 공간 이 없고 대기 열 이 가득 하지 않 을 때, 우 리 는 그것 을 배열 의 앞부분 에 남 은 공간 으로 저장 할 수 있다.
코드 구현
순환 대기 열의 실현 관건 은 대기 열 이 비어 있 고 만 료 되 었 을 때의 상태 판단 에 있다.

대기 열 이 비어 있 을 때: rear == front

대기 열 이 가득 찼 을 때: front == (rear + 1) % array.length 대기 열 이 가득 찼 을 때 한 배열 의 저장 공간 을 낭비 합 니 다.

코드 는 다음 과 같 습 니 다:

package one.wangwei.algorithms.datastructures.queue.impl;

import one.wangwei.algorithms.datastructures.queue.IQueue;

import java.util.NoSuchElementException;

/**
 *     
 *
 * @param 
 * @author https://wangwei.one
 * @date 2019/02/04
 */
public class ArrayQueue implements IQueue {

    /**
     * default array size
     */
    private static final int DEFAULT_SIZE = 1024;
    /**
     *     
     */
    private T[] array;
    /**
     *       
     */
    private int front = 0;
    /**
     *       
     */
    private int rear = 0;

    public ArrayQueue() {
        this(DEFAULT_SIZE);
    }

    public ArrayQueue(int capacity) {
        array = (T[]) new Object[capacity];
    }

    /**
     *       
     *
     * @param value
     * @return
     */
    @Override
    public boolean offer(T value) {
        if (isFull()) {
            grow();
        }
        array[rear % array.length] = value;
        rear++;
        return true;
    }

    /**
     * grow queue size doubly
     */
    private void grow() {
        int growSize = array.length << 1;
        T[] tmpArray = (T[]) new Object[growSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear < front) {
            System.arraycopy(array, 0, tmpArray, array.length - adjRear, adjRear + 1);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = tmpArray;
        rear = (rear - front);
        front = 0;
    }

    /**
     *       
     *
     * @return
     */
    @Override
    public T poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }

        T element = array[front % array.length];
        array[front % array.length] = null;
        front++;
        if (isEmpty()) {
            // remove last element
            front = rear = 0;
        }

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && size() < shrinkSize) {
            shrink();
        }
        return element;
    }

    /**
     *   
     */
    private void shrink() {
        int shrinkSize = array.length >> 1;
        T[] tmpArray = (T[]) new Object[shrinkSize];
        int adjRear = rear % array.length;
        int endIndex = rear > array.length ? array.length : rear;
        if (adjRear <= front) {
            System.arraycopy(array, 0, tmpArray, array.length - front, adjRear);
        }
        System.arraycopy(array, front, tmpArray, 0, endIndex - front);
        array = null;
        array = tmpArray;
        rear = rear - front;
        front = 0;
    }

    /**
     *       
     *
     * @return
     */
    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue underflow");
        }
        return array[front % array.length];
    }

    /**
     *       
     */
    @Override
    public void clear() {
        array = null;
        front = rear = 0;
    }

    /**
     *     
     */
    @Override
    public int size() {
        return rear - front;
    }

    /**
     *        
     *
     * @return
     */
    private boolean isFull() {
        return !isEmpty() && (front == (rear + 1) % array.length);
    }

    /**
     *        
     *
     * @return
     */
    private boolean isEmpty() {
        return size() <= 0;
    }

}

소스 코드
배열 을 기반 으로 한 경계 대기 열 (bounded quue) 은 대기 열의 크기 가 제한 되 어 있 습 니 다. 요청 수량 이 대기 열 을 초과 하면 다음 요청 이 거부 되 며, 이러한 방식 은 응답 시간 에 민감 한 시스템 에 있어 서 상대 적 으로 합 리 적 입 니 다.하지만 합 리 적 인 대기 열 크기 를 설정 하 는 것 도 중요 하 다.대기 열 이 너무 커서 대기 요청 이 너무 많 고 대기 열 이 너무 작 으 면 시스템 자원 을 충분히 이용 하지 못 하고 최대 성능 을 발휘 할 수 있 습 니 다.
참고 자료

https://time.geekbang.org/col...