데이터 구조 - 3 - 대기 열

38130 단어 데이터 구조
대열
1. 개념
대기 열 은 FIFO (first - in - first - out) 의 집합 데이터 구 조 를 따 르 는 것 입 니 다. 즉, 대기 열 에 가장 먼저 놓 인 요소 이자 가장 먼저 얻 은 것 입 니 다.
그것 의 밑바닥 은 수조 로 이 루어 질 수도 있 고 체인 시계 로 이 루어 질 수도 있다.이 는 두 개의 지침 이 있 는데 각각 머리 노드 와 꼬리 노드 를 가리 키 고 요 소 를 추가 할 때 꼬리 노드 를 뒤로 이동 하 며 요 소 를 제거 할 때 머리 노드 를 뒤로 이동 합 니 다.
2. 상용 방법
  • put 요 소 를 대기 열 에 추가 합 니 다
  • take 대기 열의 첫 번 째 요소 (뒤로 이동 헤드 노드)
  • peek 추출 대기 열의 첫 번 째 요소 (헤드 노드 이동 하지 않 음)
  • 3. 예시
    1) 배열 대기 열
    class ArrayQueue<T> {
        private final int length;
        private Object[] array;
        private int head; //                 
        private int tail; //                 
    
        public ArrayQueue(int length) {
            this.length = length;
            this.array = new Object[this.length];
            this.head = -1;
            this.tail = -1;
        }
    
        public void put(T element) {
            if (isFull()) {
                return;
            }
    
            this.tail++;
            array[tail] = element;
        }
    
        public T take() {
            if (isEmpty()) {
                return null;
            }
    
            this.head++;
            @SuppressWarnings("unchecked")
            T element = (T)array[head];
            if (head == tail) {
                head = -1;
                tail = -1;
            }
            return element;
        }
    
        @SuppressWarnings("unchecked")
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return (T)array[head + 1];
        }
    
        public int size() {
            return tail - head;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "[]";
            }
    
            StringBuilder sBuilder = new StringBuilder("[");
            for (int i = head + 1, size = i + size(); i < size; i++) {
                sBuilder.append(array[i]);
                if (i != size - 1) {
                    sBuilder.append(", ");
                } else {
                    sBuilder.append("]");
                }
            }
            return sBuilder.toString();
        }
    
        public boolean isFull() {
            return tail == length - 1;
        }
    
        public boolean isEmpty() {
            return -1 == head && head == tail;
        }
    
    }
    

    2) 링크 대기 열
    class LinkedQueue<T> {
        private final int length;
        private Node<T> head; //               
        private Node<T> tail; //            
        private int size;
    
        public LinkedQueue(int length) {
            this.length = length;
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
    
        public void put(T element) {
            if (isFull()) {
                return;
            }
    
            Node<T> add = new Node<T>(element);
            if (null == head) {
                this.head = add;
            }
            if (null != tail) {
                tail.next = add;
            }
            this.tail = add;
            this.size++;
        }
    
        public T take() {
            if (isEmpty()) {
                return null;
            }
    
            T element = head.element;
            if (head == tail) { //       ,        
                this.tail = null;
            }
            this.head = head.next;
            this.size--;
            return element;
        }
    
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return head.element;
        }
    
        public int size() {
            return size;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "[]";
            }
    
            StringBuilder sBuilder = new StringBuilder("[");
            Node<T> node = this.head;
            while (true) {
                sBuilder.append(node.element);
                if (null == node.next) {
                    break;
                }
                sBuilder.append(", ");
                node = node.next;
            }
            sBuilder.append("]");
            return sBuilder.toString();
        }
    
        public boolean isFull() {
            return size == length;
        }
    
        public boolean isEmpty() {
            return 0 == size;
        }
    
        private static class Node<T> {
            private final T element;
            private Node<T> next;
    
            private Node(T element) {
                this.element = element;
            }
    
            @Override
            public String toString() {
                return (null != element) ? element.toString() : "null";
            }
        }
    
    }
    

    3) 순환 대기 열
    class CircleQueue<T> {
        private final int length;
        private Object[] array;
        private int head; //     
        private int tail; //     
    
        public CircleQueue(int length) {
            this.length = length + 1; //       ,            。          
            this.array = new Object[this.length];
            this.head = 0;
            this.tail = 0;
        }
    
        public void put(T element) {
            if (isFull()) {
                return;
            }
    
            array[tail] = element;
            tail = (tail + 1) % length;
        }
    
        public T take() {
            if (isEmpty()) {
                return null;
            }
    
            @SuppressWarnings("unchecked")
            T element = (T)array[head];
            head = (head + 1) % length;
            return element;
        }
    
        @SuppressWarnings("unchecked")
        public T peek() {
            if (isEmpty()) {
                return null;
            }
    
            return (T)array[head];
        }
    
        public int size() {
            return (tail + length - head) % length;
        }
    
        public boolean isFull() {
            return (tail + 1) % length == head;
        }
    
        public boolean isEmpty() {
            return head == tail;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "[]";
            }
    
            StringBuilder sBuilder = new StringBuilder("[");
            for (int i = head, size = i + size(); i < size; i++) {
                sBuilder.append(array[i % length]);
                if (i != size - 1) {
                    sBuilder.append(',').append(' ');
                }
            }
            sBuilder.append(']');
            return sBuilder.toString();
        }
    
    }
    

    좋은 웹페이지 즐겨찾기