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

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

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

隊列的特點

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

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

3.屬于有序列表。

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

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

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

3.即first會因為出隊操作而增加，last會因為入隊操作而增加

代碼實現(xiàn)：

package 隊列;

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

隊列缺點：

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

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

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

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

3.隊列滿的條件：

(last + 1) % maxSize == first

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

4.隊列為空的條件：

first == last

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

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

1.隊列初始化：

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

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

2.判斷隊列是否為空：

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

3.判斷隊列是否滿：

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

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

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

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

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

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

public void showAllData(){
        if (isEmpty()) {
            System.out.println("隊列為空，沒有數(shù)據(jù)~~");
            return;
        }
		//此處i不為0，是因為有可能之前有過popData()操作，使得firs不為0，所以最好使用
    	//first給i動態(tài)賦值，
        for (int i = first; i < first+size() ; i++) {
            System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]);
        }

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

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

8.查看隊首數(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("--------測試環(huán)形隊列--------");
        char key = ' ';
        Scanner scanner = new Scanner(System.in);

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

            switch (key){
                case 's':
                    circleQueue.showAllData();
                    break;
                case 'p':
                    System.out.println("輸入一個數(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ù)組長度，即隊列最大容量
    private int first; 	  //頭指針，控制出隊操作
    private int last;	  //尾指針，控制入隊操作
    private int[] arr;	  //數(shù)組類型，可以換其他的。

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

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

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

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

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

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