데이터 구조 (2) - 대기 열

글 목록

1. 대열 구조의 분류

2. 자바 로 일반 대기 열 구조 실현

2.1. 배열 기반

2.2. 링크 기반

대기 열 구조의 특별한 점 은 표 의 전단 (front) 에서 만 삭제 작업 을 할 수 있 고 표 의 백 엔 드 (rear) 에서 삽입 작업 을 할 수 있 습 니 다. 스 택 과 마찬가지 로 대기 열 은 조작 이 제 한 된 선형 표 입 니 다.삽입 작업 을 하 는 끝 을 팀 꼬리 라 고 하고 삭제 작업 을 하 는 끝 을 팀 머리 라 고 합 니 다.
1. 대열 구조의 분류

일반 대열 구조 (quene)

양 끝 대 열 구조 (de - que)

우선 순위 대기 열 구조 (pri - que)

2. 자바 로 일반 대기 열 구 조 를 실현 합 니 다.
2.1 배열 기반

public class Quene {
    private int size;//    
    private int front;//    
    private int rear;//    
    private int[] theQuene;//         
    private int items;//        

    public Quene(int size){
        this.size = size;
        theQuene = new int[size];
        front = 0;
        rear = -1;
        items = 0;
    }

    //  
    public void  insert(int value){
         if(rear == size - 1){
             //    ,    -1，     
            rear = -1;
         }
         theQuene[++rear] = value;
         items++;
    }

    //  
    public int remove(){
        int temp = theQuene[front++];
        if(front == size){
            front = 0;
        }
        items--;
        return  temp;
    }

    //    
    public int peek(){
        return theQuene[front];
    }

    //     
    public boolean isEmpty(){
        return (items == 0);
    }

    //     
    public boolean isFull(){
        return (items == size);
    }

    //       
    public int sizeOf(){
        return items;
    }
}

2.2 링크 기반

public class LinkedListQuene<T> {
    //    
    private int queneLength = 0;
    //  
    private Node first;
    //  
    private Node last;

    //    
    private class Node {
        //      
        Node next;
        //       
        T value;
        private Node(T value) {
            this.value = value;
        }
    }

    
    public boolean isEmpty() {
        return queneLength == 0;
    }


 
    public int depth() {
        return queneLength;
    }
  
    public int enquene(T value) {
        Node node = new Node(value);
        //     ，        
        if (isEmpty()) {
            first = node;
            last = node;
            queneLength++;
            return 1;
        } else {
             Node oldNode = last;
            oldNode.next = node;
            last = node;
            queneLength++;
            return 1;
        }
    }

 
    public T dequene() {
        if (isEmpty()) {
            return null;
        } else {
            T value = first.value;
            first = first.next;
            queneLength--;
            return value;
        }
    }
 
    public T peek() {
        if (isEmpty()) {
            return null;
        } else {
            return first.value;
        }
    }
}