데이터 구조의 창고 와 대기 열

스 택 이나 대기 열 은 전형 적 인 데이터 구조 로 평소에 사용 하지만 모두 다른 사람 이 포장 한 집합 이다. 우 리 는 손 으로 쓸 필요 가 없 지만 이런 내공 은 개발 자로 서 반드시 파악 해 야 한다.
창고.
배열 에서 데이터 항목 의 아래 표 시 를 알 면 이 데이터 항목 에 즉시 접근 하거나 데이터 항목 을 순서대로 검색 하여 배열 의 각 데이터 항목 에 접근 할 수 있다 는 것 을 알 고 있 습 니 다.그러나 스 택 은 대기 열 과 달리 접근 이 제한 되 어 있 습 니 다. 즉, 특정한 시간 에 하나의 데이터 항목 만 읽 거나 삭제 할 수 있 습 니 다.알다 시 피 스 택 은 선진 적 인 후에 나 오고 스 택 꼭대기 의 데이터 만 방문 할 수 있 으 며 대기 열 은 선진 적 인 것 이 고 머리 데이터 만 방문 할 수 있 습 니 다.여 기 는 더 이상 군말 하지 않 겠 다.
창고 의 주요 메커니즘 은 수조 로 실현 할 수도 있 고 체인 테이블 로 실현 할 수도 있다. 다음은 수조 로 창고 의 기본 조작 을 실현 한다.

public class ArrayStack {
    private long[] a;
    //     
    private int size;
    //  
    private int top;

    //    
    public ArrayStack(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        //    
        top = -1;
    }

    //  
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is Full!");
            return;
        }
        a[++top] = value;
    }

    //  ，         
    public long pop() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return 0;
        }
        return a[top--];
    }

    //         
    public long peak() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return 0;
        }
        return a[top];
    }

    public boolean isFull() {
        return top == size - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    //     
    public void display() {
        if (isEmpty()) {
            System.out.println("Stack is Empty!");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

데이터 항목 이 스 택 에 들 어 가 는 시간 과 스 택 을 나 가 는 시간 복잡 도 는 모두 O (1) 입 니 다.스 택 작업 에 소요 되 는 시간 은 스 택 의 데이터 항목 의 개수 에 의존 하지 않 기 때문에 작업 시간 이 짧다 는 것 이다.스 택 은 비교 와 이동 작업 이 필요 없습니다.
대열
대기 열 도 배열 로 이 루어 질 수 있 습 니 다. 그러나 여기 문제 가 있 습 니 다. 배열 아래 에 표 시 된 것 이 가득 차 면 더 이상 추가 할 수 없습니다. 그러나 배열 앞 에는 대기 열 헤더 의 데 이 터 를 삭 제 했 기 때문에 비어 있 습 니 다.그래서 대기 열 은 순환 배열 로 이 루어 질 수 있 습 니 다. 아래 코드 를 보십시오.

public class RoundQueue {
    private long[] a;
    //    
    private int size;
    //  
    private int front;
    //  
    private int rear;
    //        
    private int nItems;

    //     
    public RoundQueue(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        front = 0;
        rear = -1;
        nItems = 0;
    }

    //    
    public void insert(int value) {
        if (isFull()) {
            System.out.println("Queue is Full!");
            return;
        }
        //         0 
        rear = ++rear % size;
        a[rear] = value;
        nItems++;
        /*if (rear == size - 1) {
            rear = -1;
        }
        a[++rear] = value;*/
    }

    //    
    public long remove() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        nItems--;
        front = front % size;
        return a[front++];
    }

    //      
    public long peak() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        return a[front];
    }

    public boolean isFull() {
        return nItems == size;
    }

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

    public void display() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return;
        }
        int item = front;
        for (int i = 0; i < nItems; i++) {
            System.out.print(a[item++ % size] + " ");
        }
        System.out.println();

    }
}

스 택 과 마찬가지 로 대기 열 에 데이터 항목 을 삽입 하고 데이터 항목 을 삭제 하 는 시간 복잡 도 는 모두 O (1) 입 니 다.
우선 순위 대기 열 이 있 습 니 다. 우선 순위 대기 열 은 스 택 과 대기 열 보다 더 전용 데이터 구조 입 니 다.우선 순위 대기 열 은 위의 일반적인 대기 열 에 비해 대기 열 에 있 는 요소 가 질서 가 있 고 키워드 가 가장 작 거나 가장 큰 데이터 항목 이 항상 팀 머리 에 있 습 니 다.데이터 항목 을 삽입 할 때 대기 열의 순 서 를 확보 하기 위해 순서대로 적당 한 위치 에 삽입 합 니 다.우선 순위 대기 열의 내부 구현 은 배열 이나 특별한 나무 더미 로 이 루어 질 수 있 습 니 다.

public class PriorityQueue {
    private long[] a;
    //    
    private int size;
    //        
    private int nItems;

    public PriorityQueue(int maxSize) {
        this.size = maxSize;
        a = new long[size];
        nItems = 0;
    }

    public void insert(int value) {
        if (isFull()) {
            System.out.println("Queue is Full!");
            return;
        }
        int j;
        //       
        if (nItems == 0) {
            a[nItems++] = value;
        } else {
            //           
            for (j = nItems - 1; j >= 0; j--) {
                if (value > a[j]) {
                    a[j + 1] = a[j];
                } else {
                    break;
                }
            }
            a[j + 1] = value;
            nItems++;
        }

    }

    public long remove() {
        if (isEmpty()) {
            System.out.println("Queue is Empty!");
            return 0;
        }
        return a[--nItems];
    }

    public long peekMin() {
        return a[nItems - 1];
    }

    public boolean isFull() {
        return nItems == size;
    }

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

    public int size() {
        return nItems;
    }

    public void display() {
        for (int i = nItems - 1; i >= 0; i--) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}

여기 서 실 현 된 우선 순위 대기 열 에 삽입 작업 은 O (N) 의 시간 이 필요 하고 삭제 작업 은 O (1) 의 시간 이 필요 합 니 다.
 
 
원문 참고 [자바 지음 망]