環形佇列

超強決議環形佇列(陣列實作)

public class CircleQueueByArray {
    private int front;//指向佇列首元素的前一個位置
    private int rear;//指向佇列的最后一個元素
    private int[] arr;
    private int size;
    public CircleQueueByArray(int size){}//構造器初始化陣列
    public boolean isFull(){}//判斷佇列是否滿
    public boolean isEmpty(){}//判斷佇列是否空
    public void add(int data){}//入隊
    public int delete(){}//出隊
    public void ergodic(){}遍歷環形佇列

接下來一一決議各方法實作

構造方法

這里陣列能放進的資料數量為size，但陣列真實容量為size+1，所空出的一格用來判斷陣列是否為空，

    public CircleQueueByArray(int size){
        this.size=size;
        arr=new int[this.size+1];
        front=0;
        rear=0;
    }

判斷佇列是否滿

在這里插入圖片描述
這里以size=3為例，當其為3時，陣列實際大小為4，由上圖可易知
(rear+1)%(size+1)=0;而front為0，所以可以判斷當(rear+1)%(size+1)==front時，佇列為滿，以后增加或洗掉元素是此條件仍成立，

    public boolean isFull(){
        return (rear+1)%(size+1)==front;
    }

判斷佇列是否為空

有上面的圖片可易知，佇列為初值時或將佇列中的元素刪減完時，rear==front，

    public boolean isEmpty(){
        return rear==front;
    }

入隊

多次入隊時環形佇列需要rear從起始位置繞到終點位置在繞到起始位置，需要重復利用，故：rear=(rear+1)%(size+1);

    //入隊
    public void add(int data){
        if(isFull()){
            System.out.println("佇列已滿，無法入隊");
            return;
        }else{
            rear=(rear+1)%(size+1);
            arr[rear]=data;
        }
    }

出隊

同rear一樣，多次出隊時環形佇列需要front從起始位置繞到終點位置在繞到起始位置，需要重復利用，故：front=(front+1)%(size+1);

    public int delete(){
        if(isEmpty()){
            throw new RuntimeException("佇列為空，無法出列");
        }else{

            front=(front+1)%(size+1);
            return arr[front-1];
        }
    }

遍歷環形佇列

front指向佇列首元素的前一個位置，所以cur=(front+1)%(size+1)是讓cur指向首元素地址，在遍歷程序中有可能出現front=3，rear=1類似于這樣的情況，所以遍歷是需要將cur%=size+1 以保證無論何時cur都能完整的遍歷陣列，

    public void ergodic(){
        if(isEmpty()){
            System.out.println("佇列為空，無法遍歷");
            return;
        }
        int cur=(front+1)%(size+1);
        while(cur!=rear){
            System.out.print(arr[cur]+" ");
            cur++;
            cur%=size+1;
        }
        System.out.print(arr[rear]);
        System.out.println();
    }

單項佇列

陣列實作單項佇列

public class QueueByArray {
    private int front=-1;
    private int rear=-1;
    private int[] arr;
   public  int size;
    //建構式中初始化陣列容量
    public QueueByArray(int s){
        this.size=s;
        arr=new int[this.size];
    }
    //入隊
    public void add(int data){
        if(rear==this.size-1){
            System.out.println("佇列已滿，無法添加資料");
            return;
        }else{
            arr[++rear]=data;
        }
    }
    //出隊
    public int delete(){
        if(front>=rear){
            throw new RuntimeException("佇列為空，無法添加資料");
        }else{
            int tmp=arr[front+1];
            for(int i=0;i<rear;i++)
                arr[i]=arr[i+1];
            rear--;
            return tmp;
            //return arr[++front];
        }
    }
    //遍歷佇列
    public void ergodic(){
        if(front>=rear){
            System.out.println("佇列為空，無法添加資料");
            return;
        }
        int cur=front+1;
        while(true){
            System.out.println(arr[cur]);
            if(cur==rear)
                break;
            cur++;
        }
    }
}

鏈表實作單項佇列

先創建一個節點類

public class Node {
    int data;
    Node next;
    public Node(){}
    public Node(int data){
        this.data=data;
        next=null;
    }
}

再創建一個用鏈表實作的佇列類

public class QueueByLink {
    private Node front;
    private Node rear;
    public QueueByLink(){
        front=null;
        rear=null;
    }
    //入隊
    public void add(int data){
        Node newNode=new Node(data);
        if(rear==null){
            front=newNode;
            rear=newNode;
        }else{
            rear.next=newNode;
            rear=newNode;
        }
    }
    //出列
    public Node delete(){
        if(rear==null) {
            throw new RuntimeException("佇列為空，無法洗掉資料");
        }else if(rear!=front){
            Node cur=front.next;
            front=front.next;
            return cur;
        }else{
            front=null;
            rear=null;
            return null;
        }
    }
    //便利佇列
    public void ergodic(){
        if(rear==null){
            System.out.println("佇列為空，無法遍歷");
            return;
        }
        Node cur=front;
        while(cur!=null){
            System.out.println(cur.data);
            cur=cur.next;
        }
    }
}

雙向對列

鏈表實作雙向佇列