집 > 기사 > Java > Java에서 대기열의 배열 및 연결 목록 구현

Java에서 대기열의 배열 및 연결 목록 구현

王林앞으로: 2019-11-28 13:44:591812검색

큐 소개

큐는 선입선출(FIFO) 선형입니다. 데이터 구조에서 큐의 주요 작업은 대기열에 넣기와 대기열에서 빼기입니다.

대기열의 선두: 대기열의 출구 끝, 대기열의 꼬리: 대기열의 입구 끝. 일반적으로 대기열에 입력된 마지막 요소의 다음 위치로 배열에 표시됩니다.

배열로 구현할 때 주의할 점: 요소가 대기열의 선두에서 계속해서 제거되면 대기열의 사용 가능한 공간이 작아지므로 일반적으로 원형을 사용합니다. 이때 팀장 앞에 팀의 꼬리가 나타날 수도 있습니다.

추천 관련 학습 비디오 튜토리얼: javalearning

큐의 배열 구현 #🎜 🎜 #

대기열 배열 구현 여기의 대기열은 일반적으로 순환 대기열입니다!

특별 참고:

(1) 큐가 가득 찼을 때의 판단 조건은 (큐 테일 첨자 + 1) % 배열 길이 = 큐 헤드 첨자# 🎜🎜#

(2) 큐 테일 포인터가 가리키는 위치에는 빈 공간이 하나 있으므로 큐의 최대 용량은 배열 길이보다 1이 적습니다.

public class MyQueue {
    private int[] array;
    private int front;
    private int rear;
    public MyQueue(int capacity){
        array = new int[capacity];
    }
 
    /*
    入队时，只需判断队列是否已满，若队列已满，则抛出异常，其他情况（包括队列为空）都正常插入
     */
    public void enQueue(int data) throws Exception{
        if((rear+1) % array.length  == front)
            throw new Exception("队列已满，不能入队！");
        array[rear] = data;
        rear = (rear+1) % array.length;
    }
 
    /*
    出队时，判断队列是否为空，若队列为空，抛出异常
     */
    public int deQueue() throws Exception{
        if(front == rear)
            throw new Exception("队列为空，不能出队！");
        int temp = array[front];
        front = (front+1) % array.length;
        return temp;
    }
 
//    public void output(){
//        for(int i = front; ((i+1) % array.length) <= rear; i++){
//一直在循环输出，严重错误！不能把取模判断语句写在条件里面！
//            i %= array.length;
//            System.out.println(array[i]);
//        }
//    }
 
    public void output(){
        for(int i = front; i != rear; i = (i+1) % array.length){
            System.out.println(array[i]);
        }
    }
    public static void main(String[] args) throws Exception{
        MyQueue myQueue = new MyQueue(5);//长度为5的队列只能插入4个元素
        myQueue.enQueue(1);
        myQueue.enQueue(3);
        myQueue.enQueue(2);
        myQueue.enQueue(4);
        myQueue.deQueue();
        myQueue.deQueue();
        myQueue.enQueue(5);
        myQueue.enQueue(6);
        myQueue.output();
    }
 
}

Queue 연결리스트 구현 큐를 연결리스트로 구현하는 경우 , 헤드 포인터를 사용하여 대기열의 첫 번째 노드를 가리키고 꼬리 포인터를 사용하여 대기열의 마지막 노드를 가리킵니다.

public class MyQueue_LinkList {
    private static class Node{
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
 
    private Node front;
    private Node rear;
    private int size;//队列中实际元素的个数
    private int maxsize;
 
    public MyQueue_LinkList(int capacity){
        maxsize = capacity;
    }
 
    public void enQueue(int data) throws Exception{
        if(size >= maxsize)
            throw new Exception("队列已满，无法入队");
        Node insertedNode = new Node(data);
        if(size == 0){
            front = insertedNode;
            rear = insertedNode;
        }
        else{
            rear.next = insertedNode;
            rear = insertedNode;
        }
        size++;
    }
 
    public int deQueue() throws Exception{
        if(front == null)
            throw new Exception("队列为空，无法出队！");
        int temp;
        if(front == rear)//队列中只有一个节点
            rear = null;
        temp = front.data;
        front = front.next;
        size--;
        return temp;
    }
 
    public void output(){
        Node temp = front;
        for(int i = 0 ; i < size; i++){
            System.out.println(temp.data);
            temp = temp.next;
        }
    }
 
    public static void main(String[] args) throws Exception{
        MyQueue_LinkList myQueue_linkList = new MyQueue_LinkList(5);
        myQueue_linkList.enQueue(1);
        myQueue_linkList.enQueue(3);
        myQueue_linkList.enQueue(2);
        myQueue_linkList.deQueue();
        myQueue_linkList.deQueue();
        myQueue_linkList.enQueue(5);
        myQueue_linkList.enQueue(7);
        myQueue_linkList.output();
 
    }
}

대기열 적용 시나리오 (1) 은행 대기열, 선착순.

(2) 멀티스레딩에서는 공정한 잠금을 위해 경쟁하는 대기 대기열이 액세스 순서에 따라 대기열의 스레드 순서를 결정합니다.

(3) 웹 크롤러는 크롤링할 웹사이트 URL을 대기열에 저장한 후 대기열에 저장된 순서대로 크롤링 및 파싱하는 방식으로 웹사이트 크롤링을 구현합니다.

Java에서 대기열의 배열 및 연결 목록 구현

관련 기사