Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「隊(duì)列」

作者：Java精髓 2021-03-09 06:30:32

開發(fā) 后端算法

隊(duì)列是一個有序列表,可以用數(shù)組或者鏈表來實(shí)現(xiàn),遵循先入先出的原則,即先存入隊(duì)列的數(shù)據(jù),要先取出.后存入的要后取出.

[[386219]]

基本介紹

隊(duì)列是一個有序列表,可以用數(shù)組或者鏈表來實(shí)現(xiàn)

遵循先入先出的原則,即先存入隊(duì)列的數(shù)據(jù),要先取出.后存入的要后取出

數(shù)組模擬隊(duì)列

隊(duì)列本身是有序列表,若使用數(shù)組的結(jié)構(gòu)來存儲隊(duì)列的數(shù)據(jù),則隊(duì)列數(shù)組的聲明如下圖,其中maxSize是該隊(duì)列的最大容量.

因?yàn)殛?duì)列的輸入\輸出是分別從前后端來處理,因此需要兩個變量front及rear分別記錄隊(duì)列前后端的下標(biāo),front會隨著數(shù)據(jù)輸出而改變,而rear則是隨著數(shù)據(jù)輸入而改變.

代碼案例

package com.structures.queue; 
 
import java.util.Scanner; 
 
public class ArrayQueueDemo { 
    public static void main(String[] args) { 
        ArrayQueue arrayQueue = new ArrayQueue(3); 
        char key = ' ';//接受用戶輸入 
        Scanner scanner = new Scanner(System.in); 
        boolean loop = true; 
        //輸出一個菜單 
        while (loop) { 
            System.out.println("s(show):顯示隊(duì)列"); 
            System.out.println("e(exit):退出程序"); 
            System.out.println("a(add):添加數(shù)據(jù)到隊(duì)列"); 
            System.out.println("g(get):從隊(duì)列取出數(shù)據(jù)"); 
            System.out.println("h(head):查看隊(duì)列頭的數(shù)據(jù)"); 
            key = scanner.next().charAt(0); 
            switch (key) { 
                case 's': 
                    arrayQueue.showQueue(); 
                    break; 
                case 'a': 
                    System.out.println("輸入一個整數(shù)"); 
                    int value = scanner.nextInt(); 
                    arrayQueue.addQueue(value); 
                    break; 
                case 'g': 
                    try { 
                        int queue = arrayQueue.getQueue(); 
                        System.out.printf("取出的數(shù)據(jù)是%d", queue); 
                    }catch (Exception e){ 
                        System.out.println(e.getMessage()); 
                    } 
                    break; 
                case 'e': 
                    scanner.close(); 
                    loop = false; 
                    break; 
                case 'h': 
                    try { 
                        int head = arrayQueue.headQueue(); 
                        System.out.printf("取出隊(duì)列頭的數(shù)據(jù)是%d", head); 
                    }catch (Exception e){ 
                        System.out.println(e.getMessage()); 
                    } 
                default: 
                    break; 
            } 
        } 
        System.out.println("程序退出"); 
    } 
} 
 
//使用數(shù)組模擬隊(duì)列-編寫一個ArrayQueue類 
class ArrayQueue { 
    //表示數(shù)組最大容量 
    private int maxSize; 
    //隊(duì)列頭 
    private int front; 
    //隊(duì)列尾 
    private int rear; 
    //用于存放數(shù)據(jù),模擬隊(duì)列 
    private int[] arr; 
 
    //創(chuàng)建隊(duì)列構(gòu)造器 
    public ArrayQueue(int arrMaxSize) { 
        maxSize = arrMaxSize; 
        arr = new int[maxSize]; 
        front = -1;//指向隊(duì)列頭的前一個位置 
        rear = -1;//指向隊(duì)列尾的數(shù)據(jù),即就是隊(duì)列最后一個數(shù)據(jù) 
    } 
 
    //判斷隊(duì)列是否滿 
    public boolean isFull() { 
        return rear == maxSize - 1; 
    } 
 
    //判斷隊(duì)列是否為空 
    public boolean isEmpty() { 
        return rear == front; 
    } 
 
    //添加數(shù)據(jù)到隊(duì)列 
    public void addQueue(int n) { 
        if (isFull()) { 
            System.out.println("隊(duì)列不能加入數(shù)據(jù)"); 
            return; 
        } 
        rear++;//讓rear 后移 
        arr[rear] = n; 
    } 
 
    //獲取隊(duì)列數(shù)據(jù),出隊(duì)列 
    public int getQueue() { 
        if (isEmpty()) { 
            throw new RuntimeException("隊(duì)列為空,不能取數(shù)據(jù)"); 
        } 
        front++; 
        return arr[front]; 
    } 
 
    //顯示隊(duì)列所有數(shù)據(jù) 
    public void showQueue() { 
        if (isEmpty()) { 
            System.out.println("隊(duì)列為空,沒有數(shù)據(jù)"); 
        } 
        for (int i = 0; i < this.arr.length; i++) { 
            System.out.printf("arr[%d]=%d\n", i, arr[i]); 
        } 
    } 
 
    //顯示隊(duì)列的頭數(shù)據(jù),注意不是取數(shù)據(jù) 
    public int headQueue() { 
        if (isEmpty()) { 
            throw new RuntimeException("隊(duì)列為空,沒有數(shù)據(jù)"); 
        } 
        return arr[front + 1]; 
    } 
 
}

問題分析

目前這個數(shù)組使用一次就不能用,沒有達(dá)到復(fù)用的效果.
將這個數(shù)組使用算法,改進(jìn)成一個環(huán)形的隊(duì)列:取模%

改進(jìn)成環(huán)形隊(duì)列的思路分析

front變量的含義做一個調(diào)整:front 就指向隊(duì)列的第一個元素,也就是arr[front]就是隊(duì)列的第一個元素,front的初始值=0
rear變量的含義做一個調(diào)整:rear 指向隊(duì)列的最后一個元素的后一個位置,因?yàn)橄Ｍ粘鲆粋€空間作為約定.rear初始值=0
當(dāng)隊(duì)列滿時,條件是(rear+1)%maxSize = front.
當(dāng)隊(duì)列為空時條件,rear == front 空.
當(dāng)我們這樣分析,隊(duì)列中有效的數(shù)據(jù)的個數(shù)=(rear+maxSize-front)%maxSize.

環(huán)形隊(duì)列代碼案例

package com.structures.queue; 
 
import java.util.Scanner; 
 
public class CircleArrayQueue { 
    public static void main(String[] args) { 
        CircleArray arrayQueue = new CircleArray(4);//這里設(shè)置4,其隊(duì)列的有效數(shù)據(jù)最大是3 
        char key = ' ';//接受用戶輸入 
        Scanner scanner = new Scanner(System.in); 
        boolean loop = true; 
        //輸出一個菜單 
        while (loop) { 
            System.out.println("s(show):顯示隊(duì)列"); 
            System.out.println("e(exit):退出程序"); 
            System.out.println("a(add):添加數(shù)據(jù)到隊(duì)列"); 
            System.out.println("g(get):從隊(duì)列取出數(shù)據(jù)"); 
            System.out.println("h(head):查看隊(duì)列頭的數(shù)據(jù)"); 
            key = scanner.next().charAt(0); 
            switch (key) { 
                case 's': 
                    arrayQueue.showQueue(); 
                    break; 
                case 'a': 
                    System.out.println("輸入一個整數(shù)"); 
                    int value = scanner.nextInt(); 
                    arrayQueue.addQueue(value); 
                    break; 
                case 'g': 
                    try { 
                        int queue = arrayQueue.getQueue(); 
                        System.out.printf("取出的數(shù)據(jù)是%d", queue); 
                    }catch (Exception e){ 
                        System.out.println(e.getMessage()); 
                    } 
                    break; 
                case 'e': 
                    scanner.close(); 
                    loop = false; 
                    break; 
                case 'h': 
                    try { 
                        int head = arrayQueue.headQueue(); 
                        System.out.printf("取出隊(duì)列頭的數(shù)據(jù)是%d", head); 
                    }catch (Exception e){ 
                        System.out.println(e.getMessage()); 
                    } 
                default: 
                    break; 
            } 
        } 
        System.out.println("程序退出"); 
    } 
 
} 
 
class CircleArray { 
    //表示數(shù)組最大容量 
    private int maxSize; 
    //front變量的含義做一個調(diào)整:front 就指向隊(duì)列的第一個元素,也就是arr[front]就是隊(duì)列的第一個元素,front的初始值=0 
    private int front; 
    //rear變量的含義做一個調(diào)整:rear 指向隊(duì)列的最后一個元素的后一個位置,因?yàn)橄Ｍ粘鲆粋€空間作為約定.rear初始值=0 
    private int rear; 
    //用于存放數(shù)據(jù),模擬隊(duì)列 
    private int[] arr; 
 
    public CircleArray(int arrMaxSize) { 
        maxSize = arrMaxSize; 
        arr = new int[maxSize]; 
    } 
 
    //判斷隊(duì)列是否滿 
    public boolean isFull() { 
        return (rear + 1) % maxSize == front; 
    } 
 
    //判斷隊(duì)列是否為空 
    public boolean isEmpty() { 
        return rear == front; 
    } 
 
    //添加數(shù)據(jù)到隊(duì)列 
    public void addQueue(int n) { 
        if (isFull()) { 
            System.out.println("隊(duì)列滿,隊(duì)列不能加入數(shù)據(jù)"); 
            return; 
        } 
        //直接將數(shù)據(jù)加入 
        arr[rear] = n; 
        //將rear后移,這里必須考慮取模 
        rear = (rear + 1) % maxSize; 
    } 
 
    //獲取隊(duì)列數(shù)據(jù),出隊(duì)列 
    public int getQueue() { 
        if (isEmpty()) { 
            throw new RuntimeException("隊(duì)列為空,不能取數(shù)據(jù)"); 
        } 
        //這里需要分析front是指向隊(duì)列的第一個元素, 
        //1.先把front對應(yīng)的值保存到一個臨時變量, 
        //2.將front后移,考慮取模 
        //3.將臨時保存的變量返回 
        int value = arr[front]; 
        front = (front + 1) % maxSize; 
        return value; 
    } 
 
    //顯示隊(duì)列所有數(shù)據(jù) 
    public void showQueue() { 
        if (isEmpty()) { 
            System.out.println("隊(duì)列為空,沒有數(shù)據(jù)"); 
        } 
        //從front開始遍歷 
        for (int i = front; i < front + size(); i++) { 
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]); 
        } 
    } 
 
    //求出當(dāng)前隊(duì)列有效數(shù)據(jù)的個數(shù) 
    public int size() { 
        return (rear + maxSize - front) % maxSize; 
    } 
 
    //顯示隊(duì)列的頭數(shù)據(jù),注意不是取數(shù)據(jù) 
    public int headQueue() { 
        if (isEmpty()) { 
            throw new RuntimeException("隊(duì)列為空,沒有數(shù)據(jù)"); 
        } 
        return arr[front]; 
    } 
}