Java 單向隊(duì)列及環(huán)形隊(duì)列的實(shí)現(xiàn)原理

更新時(shí)間：2021年10月31日 16:21:31 作者：沐雨橙風(fēng)~~

本文主要介紹了Java 單向隊(duì)列及環(huán)形隊(duì)列的實(shí)現(xiàn)原理，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

隊(duì)列的特點(diǎn)

1.可以使用數(shù)組和鏈表兩種方式來實(shí)現(xiàn)。

2.遵循先入先出(FIFO)的規(guī)則，即先進(jìn)入的數(shù)據(jù)先出。

3.屬于有序列表。

圖解實(shí)現(xiàn)過程：

1.定義一個(gè)固定長(zhǎng)度的數(shù)組，長(zhǎng)度為maxSize。

2.設(shè)置兩個(gè)指針first = -1（指向隊(duì)列第一個(gè)數(shù)據(jù)的前一位，這樣保證在添加第一個(gè)數(shù)據(jù)以后頭指針為0，和數(shù)組的下標(biāo)一樣，且用于操作出隊(duì)）和last = -1(指向隊(duì)尾，用于操作入隊(duì))。

3.即first會(huì)因?yàn)槌鲫?duì)操作而增加，last會(huì)因?yàn)槿腙?duì)操作而增加

代碼實(shí)現(xiàn)：

package 隊(duì)列;

public class ArrayQueueTest {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
        arrayQueue.addQueue("瓊");
        arrayQueue.addQueue("赟");
        arrayQueue.addQueue("瓏");
        arrayQueue.showAllQueueData();
        System.out.println(arrayQueue.getQueue());   
    }
}
class ArrayQueue{
    private int maxSize;//定義隊(duì)列的最大長(zhǎng)度
    private int first ;//指向隊(duì)列頭的前一個(gè)位置?。∏耙粋€(gè)位置??！出隊(duì)方向
    private int last ;//指向隊(duì)列尾部!!即最后一個(gè)數(shù)據(jù)?。。∪腙?duì)方向
    private String[] arr; //先建一個(gè)空的數(shù)組，具體長(zhǎng)度未知，需要maxSize來確定。
	
    //構(gòu)造器初始化隊(duì)列信息
    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.first = -1;
        this.last = -1;
        arr = new String[maxSize];
    }
	
    //判斷是否為空
    public boolean isEmpty(){
        if (first == last) {
            System.out.println("隊(duì)列為空~~");
            return true;
        }else {
            System.out.println("隊(duì)列不為空~~");
            return false;
        }
    }
    
    //判斷隊(duì)列是否滿
    public boolean isFull(){
        if (last == maxSize-1) {
            System.out.println("隊(duì)列已滿~~");
            return true;
        }else {
            System.out.println("隊(duì)列未滿~~");
            return false;
        }
    }
	
    //入隊(duì)
    public void addQueue(String data){
        if (last == maxSize-1){
            System.out.println("隊(duì)列已滿，不能再添加??！");
            return;
        }else {
            last++; //添加數(shù)據(jù)只和末尾下標(biāo)有關(guān)
            arr[last] = data;
            return;
        }
    }
	
    //出隊(duì)
    public String getQueue(){
        if (isEmpty()) {
            //因?yàn)間etQueue方法是int型，需要返回?cái)?shù)據(jù)，如果無數(shù)據(jù)，也需要返回
            //如果返回-1或者其他數(shù)據(jù)，會(huì)讓人誤解獲取到的數(shù)就是-1或者其他
            //所以用拋出異常來處理
            throw new RuntimeException("隊(duì)列為空，無數(shù)據(jù)~~");
        }
        else {
            first++;
            return arr[first];
        }
    }
	
    //遍歷隊(duì)列所有信息
    public void showAllQueueData(){
        if (first == last){
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr["+i+"]"+"="+arr[i]);
        }
    }
	
    //獲取隊(duì)列頭數(shù)據(jù)
    public String headQueueData(){
        if (isEmpty()){
            throw new RuntimeException("無數(shù)據(jù)~~~");
        }
        return arr[++first];
    }
}

隊(duì)列缺點(diǎn)：

由于出隊(duì)操作，使得first指針上移變大，導(dǎo)致數(shù)組前面空出來的位置就不能再繼續(xù)添加數(shù)據(jù)，即不能再被重復(fù)使用，這樣一個(gè)隊(duì)列只能使用一次，內(nèi)存效率太低，所以需要使用環(huán)形隊(duì)列來優(yōu)化解決。

優(yōu)化解決——環(huán)形隊(duì)列實(shí)現(xiàn)思路

1.first指針初始默認(rèn)設(shè)置為0，指向隊(duì)列頭部，則arr[first] 就是第一個(gè)數(shù)據(jù)。

2.last指針初始默認(rèn)也為0，但是會(huì)隨著增加數(shù)據(jù)而后移。

3.隊(duì)列滿的條件：

(last + 1) % maxSize == first

last+1是為了讓指針后移，而且如果不設(shè)置為 last+1 那么一開始的時(shí)候last為0 ， last % maxSize == 0，且first也為0，還沒加數(shù)據(jù)就滿了。

4.隊(duì)列為空的條件：

first == last

5.由于判斷是否滿的時(shí)候： last+1 ，導(dǎo)致實(shí)際上可以裝的數(shù)據(jù)比數(shù)組長(zhǎng)度少 1

環(huán)形隊(duì)列各步驟及各方法實(shí)現(xiàn)講解

1.隊(duì)列初始化：

class CircleArryQueue{
    private int maxSize ; //數(shù)組長(zhǎng)度，即隊(duì)列最大容量
    private int first; 	  //頭指針，控制出隊(duì)操作
    private int last;	  //尾指針，控制入隊(duì)操作
    private int[] arr;	  //數(shù)組類型，可以換其他的。

    //構(gòu)造器初始化信息
    public CircleArryQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.first = 0;		//這兩個(gè)可以不加，不叫也是默認(rèn)為0
        this.last = 0;
    }
}

2.判斷隊(duì)列是否為空：

 public boolean isEmpty(){
        //頭指針和尾指針一樣 則說明為空
        return last == first;
    }

3.判斷隊(duì)列是否滿：

/*
*這里的 last+1 主要是為了讓指針后移，特別是在隊(duì)列尾部添加數(shù)據(jù)的時(shí)候，本來用last也可以判斷，但
*是一開始還沒加數(shù)據(jù)的時(shí)候，如果直接用last % maxSize == first，結(jié)果是true，所以為了解決指針后*移和判斷是否滿，用來last+1。其次，因?yàn)閘ast+1可能會(huì)導(dǎo)致數(shù)組指針越界，所以用取模來控制它的范  * 圍，同時(shí)保證他會(huì)在一個(gè)固定的范圍循環(huán)變換，也利于環(huán)形隊(duì)列的實(shí)現(xiàn)。
*/
public boolean isFull(){
    return (last + 1) % maxSize == first;
}

4.添加數(shù)據(jù)到隊(duì)列尾部：入隊(duì)

public void pushData(int data){
    //先判斷是否滿了
    if(isFull()){
        System.out.println("隊(duì)列已經(jīng)滿啦~~");
        return;
    }
    arr[last] = data;
    //last+1是為了后移，取模是為了避免指針越界，同時(shí)可以讓指針循環(huán)
    last = (last + 1) % maxSize;
}

5.取出隊(duì)首數(shù)據(jù)：出隊(duì)

public int popData(){
        if (isEmpty()) {
            //拋異常就可以不用返回?cái)?shù)據(jù)了
            new RuntimeException("隊(duì)列為空，沒有獲取到數(shù)據(jù)~~");
        }
    
 		//要先把first對(duì)應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回?cái)?shù)據(jù)
        int value = arr[first];
		//first+1的操作和last+1是一樣的，取模也是 
        first = (first+1) % maxSize;
        System.out.println(value);
        return value;
    	//如果不保存first指針 那么返回的數(shù)據(jù)就不對(duì)了
		//如果直接返回?cái)?shù)據(jù)，那first指針還沒后移 也不對(duì)，所以需要使用第三方變量
    }

6.展示隊(duì)列中所有數(shù)據(jù)：

public void showAllData(){
        if (isEmpty()) {
            System.out.println("隊(duì)列為空，沒有數(shù)據(jù)~~");
            return;
        }
		//此處i不為0，是因?yàn)橛锌赡苤坝羞^popData()操作，使得firs不為0，所以最好使用
    	//first給i動(dòng)態(tài)賦值，
        for (int i = first; i < first+size() ; i++) {
            System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]);
        }

7.獲取隊(duì)列中數(shù)據(jù)的總個(gè)數(shù)：

public int dataNum(){
	//韓順平老師的教程上是這樣寫，但是我理解不了..........。
	return (last+maxSize-first) % maxSize;   
}

8.查看隊(duì)首數(shù)據(jù)但不彈出：

public void seeFirstData(){
    return arr[first];
}

全部代碼整合：

package 練習(xí);

import java.util.Scanner;

public class CircleArryQueue {
    public static void main(String[] args){
        CircleQueue circleQueue = new CircleQueue(4);
        System.out.println("--------測(cè)試環(huán)形隊(duì)列--------");
        char key = ' ';
        Scanner scanner = new Scanner(System.in);

        boolean flag = true;
        while (flag){
            System.out.println("s(showAllData):查看隊(duì)列數(shù)據(jù)");
            System.out.println("p(pushData):隊(duì)尾添加數(shù)據(jù)");
            System.out.println("g(popData):彈出隊(duì)頭數(shù)據(jù)");
            System.out.println("h(seefirstData)：獲取隊(duì)頭數(shù)據(jù)");
            System.out.println("e(exit):退出程序");
            key = scanner.next().charAt(0);

            switch (key){
                case 's':
                    circleQueue.showAllData();
                    break;
                case 'p':
                    System.out.println("輸入一個(gè)數(shù)據(jù)：");
                    int obj = scanner.nextInt();
                    circleQueue.pushData(obj);
                    break;
                case 'g':
                    circleQueue.popData();
                    break;
                case 'h':
                    circleQueue.seeFirstData();
                    break;
                case 'e':
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }

        }

        System.out.println("程序結(jié)束~~~");

    }

}

class CircleQueue {
    private int maxSize ; //數(shù)組長(zhǎng)度，即隊(duì)列最大容量
    private int first; 	  //頭指針，控制出隊(duì)操作
    private int last;	  //尾指針，控制入隊(duì)操作
    private int[] arr;	  //數(shù)組類型，可以換其他的。

    //構(gòu)造器初始化信息
    public CircleQueue(int maxSize){
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.first = 0;		//這兩個(gè)可以不加，不叫也是默認(rèn)為0
        this.last = 0;
    }

    public boolean isEmpty(){
        //頭指針和尾指針一樣 則說明為空
        return last == first;
    }

/*
*這里的 last+1 主要是為了讓指針后移，特別是在隊(duì)列尾部添加數(shù)據(jù)的時(shí)候，本來用last也可以判斷但
*是一開始還沒加數(shù)據(jù)的時(shí)候，如果直接用last % maxSize == first，結(jié)果是true，所以為了解決指針
*后移和判斷是否滿，用來last+1。其次，因?yàn)閘ast+1可能會(huì)導(dǎo)致數(shù)組指針越界，所以用取模來控制它
*的范圍，同時(shí)保證他會(huì)在一個(gè)固定的范圍循環(huán)變換，也利于環(huán)形隊(duì)列的實(shí)現(xiàn)。
*/
    public boolean isFull(){
        return (last + 1) % maxSize == first;
    }

    public void pushData(int data){
        //先判斷是否滿了
        if(isFull()){
            System.out.println("隊(duì)列已經(jīng)滿啦~~");
            return;
        }
        arr[last] = data;
        //last+1是為了后移，取模是為了避免指針越界，同時(shí)可以讓指針循環(huán)
        last = (last + 1) % maxSize;
    }

    public int popData(){
        if (isEmpty()) {
            //拋異常就可以不用返回?cái)?shù)據(jù)了
            throw new RuntimeException("隊(duì)列為空，沒有獲取到數(shù)據(jù)~~");
        }

        //要先把first對(duì)應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回?cái)?shù)據(jù)
        int value = arr[first];
        //first+1的操作和last+1是一樣的，取模也是
        first = (first+1) % maxSize;
        System.out.println(value);
        return value;
        //如果不保存first指針 那么返回的數(shù)據(jù)就不對(duì)了
        //如果直接返回?cái)?shù)據(jù)，那first指針還沒后移 也不對(duì)，所以需要使用第三方變量
    }
    
	//查看所有數(shù)據(jù)
    public void showAllData(){
        if (isEmpty()) {
            System.out.println("隊(duì)列為空，沒有數(shù)據(jù)~~");
        }
        //此處i不為0，是因?yàn)橛锌赡苤坝羞^popData()操作，使得firs不為0，所以最好使用
        //first給i動(dòng)態(tài)賦值，
        for (int i = first; i < first+dataNum() ; i++) {
            System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]);
        }
    }
	//查看有效數(shù)據(jù)個(gè)數(shù)
    public int dataNum(){
        //韓順平老師的教程上是這樣寫，但是我理解不了..........。
        return (last+maxSize-first) % maxSize;
    }
	//查看隊(duì)列第一個(gè)數(shù)據(jù)
    public int seeFirstData(){    
        System.out.println(arr[first]);
        return arr[first];
        
    }
}

最后：

部分內(nèi)容參考自B站韓順平老師java數(shù)據(jù)結(jié)構(gòu)課程

到此這篇關(guān)于Java 單向隊(duì)列及環(huán)形隊(duì)列的實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)Java 單向隊(duì)列及環(huán)形隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: