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

원본 링크: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...
  • 좋은 웹페이지 즐겨찾기