隊列本身是有序列表，若使用數(shù)組的結構來存儲隊列的數(shù)據(jù)，則隊列數(shù)組的聲明如下圖, 其中 maxSize 是該隊列的最大容量。
因為隊列的輸出、輸入是分別從前后端來處理，所以我們需要兩個變量 front 及 rear 分別記錄隊列前后端的下標， front 會隨著數(shù)據(jù)輸出而改變，而 rear 則是隨著數(shù)據(jù)輸入而改變。
當我們將數(shù)據(jù)存入隊列時稱為addQueue，addQueue 的處理需要有兩個步驟：思路分析
當 front == rear 【隊列空無數(shù)據(jù)】，將尾指針往后移：rear + 1
若尾指針 rear 小于隊列的最大下標 maxSize-1，則將數(shù)據(jù)存入 rear 所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。 rear == maxSize - 1【表示隊列滿】無法存入數(shù)據(jù)。

代碼

package com.cz.Queuearray;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.BlockingQueue;
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.Queuearray
 * @ClassName: QueueArray
 * @Author: 張晟睿
 * @Date: 2022/2/21 18:42
 * @Version: 1.0
 */
public class QueueArray {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        QueueArray1  qArray1 = new QueueArray1(3);
        Scanner scanner = new Scanner(System.in);
        char key = ' ';
        boolean f = true;
        while(f){
            System.out.println("s(show):顯示隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數(shù)據(jù)到隊列");
            System.out.println("g(get):從隊列里面取出數(shù)據(jù)");
            System.out.println("h(head):查看隊列頭部的數(shù)據(jù)");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    qArray1.getQueue();
                    break;
                case 'a':
                    System.out.println("請輸出一個數(shù)字：");
                    int value = scanner.nextInt();
                    qArray1.addQueue(value);
                case 'g':
                    try {
                        int res = qArray1.exitQueue();
                        System.out.printf("輸出的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                case 'h':
                        int res = qArray1.headQueue();
                        System.out.printf("對頭的數(shù)據(jù)是%d\n",res);
                case 'e':
                    scanner.close();
                    f=false;
                default:
            }
        }
        System.out.println("退出程序?。。。。。?！");
    }
}
//數(shù)組模擬隊列
class QueueArray1{
    private int maxSize;//最大容量、
    private int arr[]; //聲明數(shù)組
    private int front;//隊頭元素
    private int rear;//隊尾
    //構造器
    public QueueArray1(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int [maxSize];
        front = -1;//指向隊列頭部，分析出front是指向隊列頭的前一 個位置。
        rear = -1;//指向隊列尾，指向隊列尾的數(shù)據(jù)(即就是隊列最后一個數(shù)據(jù))
    //判斷隊空
    public boolean isEmety(){
        return rear==front;
    //判斷隊滿
    public boolean isFull(){
        return rear == maxSize - 1;
    //入隊
    public void addQueue(int n){
        if (isFull()) {
            System.out.println("隊列已滿，無法插入");
            return;//不加return
            //Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
            //at day1.QueueArray1.insert(QueueArray.java:89)
            //at day1.QueueArray.main(QueueArray.java:32)
        arr[++rear] = n;
    //出隊
    public int exitQueue(){
        if (isEmety()) {
            throw new RuntimeException("隊列為空，無元素");
        return arr[++front];
    //輸出全部元素
    public void getQueue(){
            System.out.println("隊列為空，無法輸出數(shù)據(jù)~~~~~~~~~~");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
    //顯示隊列的頭數(shù)據(jù)，不是取數(shù)據(jù)
    public int headQueue(){
            throw new RuntimeException("數(shù)據(jù)為空，無法取出頭元素~~~~~~~~~~");
        return arr[front+1];

隊列優(yōu)化—循環(huán)隊列

在上述的使用中，發(fā)現(xiàn)數(shù)組使用一次之后就無法使用，沒有達到復用的效果，那究竟能不能實現(xiàn)復用呢？當然可以的。

我們將這個數(shù)組使用算法，改進成一個 環(huán)形的隊列 取模：%

對前面的數(shù)組模擬隊列的優(yōu)化，充分利用數(shù)組. 因此將數(shù)組看做是一個環(huán)形的。(通過取模的方式來實現(xiàn)即可)

簡單分析一下：

尾索引的下一個為頭索引時表示隊列滿，即將隊列容量空出一個作為約定,這個在做判斷隊列滿的時候需要注意 (rear + 1) % maxSize == front 【隊列滿】
rear == front 【隊列為空】

思路如下：

front 變量的含義做一個調(diào)整： front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素，front 的初始值 = 0
rear 變量的含義做一個調(diào)整：rear 指向隊列的最后一個元素的后一個位置. 因為希望空出一個空間做為約定，rear 的初始值 = 0
當隊列滿時，條件是 (rear + 1) % maxSize == front 【滿】
對隊列為空的條件， rear == front 空
當我們這樣分析，隊列中有效的數(shù)據(jù)的個數(shù) (rear - front + maxSize) % maxSize
我們就可以在原來的隊列上修改得到，一個環(huán)形隊列

代碼

package com.cz.Queuearray;

import java.util.Scanner;
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.Queuearray
 * @ClassName: CircleQueueArray
 * @Author: 張晟睿
 * @Date: 2022/2/22 14:58
 * @Version: 1.0
 */
public class CircleQueueArray {
    public static void main(String[] args) {
        CircleQueueArray1  circlequeue = new CircleQueueArray1(3);
        Scanner scanner = new Scanner(System.in);
        char key = ' ';
        boolean f = true;
        while(f){
            System.out.println("s(show):顯示隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數(shù)據(jù)到隊列");
            System.out.println("g(get):從隊列里面取出數(shù)據(jù)");
            System.out.println("h(head):查看隊列頭部的數(shù)據(jù)");
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    circlequeue.showQueue();
                    break;
                case 'a':
                    System.out.println("請輸出一個數(shù)字：");
                    int value = scanner.nextInt();
                    circlequeue.addQueue(value);
                case 'g':
                    try {
                        int res = circlequeue.getQueue();
                        System.out.printf("輸出的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                case 'h':
                        int res = circlequeue.headQueue();
                        System.out.printf("對頭的數(shù)據(jù)是%d\n",res);
                case 'e':
                    scanner.close();
                    f=false;
                default:
            }
        }
        System.out.println("退出程序?。。。。。?！");
    }
}
class CircleQueueArray1{
    private int maxSize; // 表示數(shù)組的最大容量
    //front 變量的含義做一個調(diào)整： front 就指向隊列的第一個元素, 也就是說 arr[front] 就是隊列的第一個元素
    //front 的初始值 = 0
    private int front;
    //rear 變量的含義做一個調(diào)整：rear 指向隊列的最后一個元素的后一個位置. 因為希望空出一個空間做為約定. //rear 的初始值 = 0
    private int rear; // 隊列尾
    private int[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊列
    public CircleQueueArray1(int MaxSize){
        maxSize = MaxSize;
        arr = new int [maxSize];
    //判斷隊滿
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    //判斷隊列空
    public boolean isEmpty(){
        return rear == front;
    // 添加數(shù)據(jù)到隊列
    public void addQueue(int n) {
        if (isFull()){
            System.out.println("隊列滿，不能加入數(shù)據(jù)~");
            return;
        //將數(shù)據(jù)直接插入到數(shù)組，用隊尾rear來進行位置的確定
        arr[rear] = n;
        //將 rear 后移, 這里必須考慮取
        rear = (rear + 1) % maxSize;
    //獲取隊列的數(shù)據(jù), 出隊列
    public int getQueue() {
        if (isEmpty()) throw new RuntimeException("隊列空，不能取數(shù)據(jù)");
        // 這里需要分析出 front 是指向隊列的第一個元素,因為這里是循環(huán)的，所以我們考慮用一個臨時變量來獲取當前的隊頭
        // 1. 先把 front 對應的值保留到一個臨時變量
        // 2. 將 front 后移, 考慮取模
        // 3. 將臨時保存的變量返回
        int value = front;
        front = (front + 1) % maxSize;
        return arr[value];
    // 求出當前隊列有效數(shù)據(jù)的個數(shù)
    public int size() {
        return (rear - front + maxSize) % maxSize;
    // 顯示隊列的所有數(shù)據(jù)
    public void showQueue() {
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
    // 顯示隊列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
    public int headQueue() {
        // 判斷隊列是空
        if (isEmpty()) {
            throw new RuntimeException("隊列空的，沒有數(shù)據(jù)~~");
        return arr[front];

使用java內(nèi)部隊列

LinkedList 類實現(xiàn)了 Queue 接口，因此我們可以把 LinkedList 當成 Queue 來用。

代碼

package com.cz.Queuearray;

import java.util.LinkedList;
import java.util.Queue;
/**
 * @ProjectName: Data_structure
 * @Package: com.cz.Queuearray
 * @ClassName: LinkedListDemo
 * @Author: 張晟睿
 * @Date: 2022/2/22 15:43
 * @Version: 1.0
 */
public class LinkedListDemo {
    public static void main(String[] args) {
        //add()和remove()方法在失敗的時候會拋出異常(不推薦)
        Queue<Integer> queue = new LinkedList<>();
        //offer() 將指定的元素添加為此列表的尾部（最后一個元素）。
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        for (Integer nums:queue) {
            System.out.println(nums);
        }
        //poll() 檢索并刪除此列表的頭（第一個元素）。
        //當集合為空時，返回 null
        queue.poll();
        //queue.poll();
        //remove() 檢索并刪除此列表的頭（第一個元素）。
        //當集合為空時，出現(xiàn)異常 java.util.NoSuchElementException;
        queue.remove();
        //element() 檢索但不刪除此列表的頭（第一個元素）。
        //當隊列為空時，java.util.NoSuchElementException
        //System.out.println("隊列的頭部：" + queue.element());
        //peek() 檢索但不刪除此列表的頭（第一個元素）。
        //當隊列為空時，返回null
        System.out.println("隊列的頭部：" + queue.peek());
    }
}

poll，remove 區(qū)別：

remove() 和 poll() 方法都是從隊列中刪除第一個元素。remove() 的行為與 Collection 接口的版本相似，但是新的 poll() 方法在用空集合調(diào)用時不是拋出異常，只是返回 null。因此新的方法更適合容易出現(xiàn)異常條件的情況。

peek，element區(qū)別：

element() 和 peek() 用于在隊列的頭部查詢元素。與 remove() 方法類似，在隊列為空時， element() 拋出一個異常，而 peek() 返回 null。

所以推薦大家使用peek() 和 poll()。

到此這篇關于Java語言通過三種方法來實現(xiàn)隊列的文章就介紹到這了,更多相關Java實現(xiàn)隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: