這篇文章主要介紹了Java語言通過三種方法來實(shí)現(xiàn)隊(duì)列的實(shí)例代碼，數(shù)組模擬隊(duì)列，通過對(duì)定義的了解，發(fā)現(xiàn)隊(duì)列很像我們的數(shù)組，下面我們通過實(shí)踐給大家詳細(xì)介紹,需要的朋友可以參考下

隊(duì)列

隊(duì)列是一種特殊的線性表，只允許在表的前端進(jìn)行刪除操作，在表的后端進(jìn)行插入操作。
隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來實(shí)現(xiàn)。
遵循先入先出的原則。即：先存入隊(duì)列的數(shù)據(jù)，要先取出。后存入的要后取出。
就相當(dāng)于我們?nèi)粘Ｉ钪械呐抨?duì)，先來先服務(wù)，后來的只能在后面進(jìn)行排隊(duì)等待。

圖解

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

通過對(duì)定義的了解，發(fā)現(xiàn)隊(duì)列很像我們的數(shù)組，那我們是不是可以通過數(shù)組來模擬隊(duì)列，下面我們來實(shí)踐一下。

首先先分析一下：

隊(duì)列本身是有序列表，若使用數(shù)組的結(jié)構(gòu)來存儲(chǔ)隊(duì)列的數(shù)據(jù)，則隊(duì)列數(shù)組的聲明如下圖, 其中 maxSize 是該隊(duì) 列的最大容量。
因?yàn)殛?duì)列的輸出、輸入是分別從前后端來處理，所以我們需要兩個(gè)變量 front 及 rear 分別記錄隊(duì)列前后端的下標(biāo)， front 會(huì)隨著數(shù)據(jù)輸出而改變，而 rear 則是隨著數(shù)據(jù)輸入而改變。
當(dāng)我們將數(shù)據(jù)存入隊(duì)列時(shí)稱為addQueue，addQueue 的處理需要有兩個(gè)步驟：思路分析
當(dāng) front == rear 【隊(duì)列空無數(shù)據(jù)】，將尾指針往后移：rear + 1
若尾指針 rear 小于隊(duì)列的最大下標(biāo) maxSize-1，則將數(shù)據(jù)存入 rear 所指的數(shù)組元素中，否則無法存入數(shù)據(jù)。 rear == maxSize - 1【表示隊(duì)列滿】無法存入數(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):顯示隊(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':
                    qArray1.getQueue();
                    break;
                case 'a':
                    System.out.println("請(qǐng)輸出一個(gè)數(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("對(duì)頭的數(shù)據(jù)是%d\n",res);
                case 'e':
                    scanner.close();
                    f=false;
                default:
            }
        }
        System.out.println("退出程序?。。。。。?！");
    }
}
//數(shù)組模擬隊(duì)列
class QueueArray1{
    private int maxSize;//最大容量、
    private int arr[]; //聲明數(shù)組
    private int front;//隊(duì)頭元素
    private int rear;//隊(duì)尾
    //構(gòu)造器
    public QueueArray1(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int [maxSize];
        front = -1;//指向隊(duì)列頭部，分析出front是指向隊(duì)列頭的前一 個(gè)位置。
        rear = -1;//指向隊(duì)列尾，指向隊(duì)列尾的數(shù)據(jù)(即就是隊(duì)列最后一個(gè)數(shù)據(jù))
    //判斷隊(duì)空
    public boolean isEmety(){
        return rear==front;
    //判斷隊(duì)滿
    public boolean isFull(){
        return rear == maxSize - 1;
    //入隊(duì)
    public void addQueue(int n){
        if (isFull()) {
            System.out.println("隊(duì)列已滿，無法插入");
            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;
    //出隊(duì)
    public int exitQueue(){
        if (isEmety()) {
            throw new RuntimeException("隊(duì)列為空，無元素");
        return arr[++front];
    //輸出全部元素
    public void getQueue(){
            System.out.println("隊(duì)列為空，無法輸出數(shù)據(jù)~~~~~~~~~~");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);
    //顯示隊(duì)列的頭數(shù)據(jù)，不是取數(shù)據(jù)
    public int headQueue(){
            throw new RuntimeException("數(shù)據(jù)為空，無法取出頭元素~~~~~~~~~~");
        return arr[front+1];

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

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

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

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

簡單分析一下：

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

思路如下：

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

代碼

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):顯示隊(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':
                    circlequeue.showQueue();
                    break;
                case 'a':
                    System.out.println("請(qǐng)輸出一個(gè)數(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("對(duì)頭的數(shù)據(jù)是%d\n",res);
                case 'e':
                    scanner.close();
                    f=false;
                default:
            }
        }
        System.out.println("退出程序?。。。。。。?);
    }
}
class CircleQueueArray1{
    private int maxSize; // 表示數(shù)組的最大容量
    //front 變量的含義做一個(gè)調(diào)整： front 就指向隊(duì)列的第一個(gè)元素, 也就是說 arr[front] 就是隊(duì)列的第一個(gè)元素
    //front 的初始值 = 0
    private int front;
    //rear 變量的含義做一個(gè)調(diào)整：rear 指向隊(duì)列的最后一個(gè)元素的后一個(gè)位置. 因?yàn)橄Ｍ粘鲆粋€(gè)空間做為約定. //rear 的初始值 = 0
    private int rear; // 隊(duì)列尾
    private int[] arr; // 該數(shù)據(jù)用于存放數(shù)據(jù), 模擬隊(duì)列
    public CircleQueueArray1(int MaxSize){
        maxSize = MaxSize;
        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ì)列滿，不能加入數(shù)據(jù)~");
            return;
        //將數(shù)據(jù)直接插入到數(shù)組，用隊(duì)尾rear來進(jìn)行位置的確定
        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ì)列的第一個(gè)元素,因?yàn)檫@里是循環(huán)的，所以我們考慮用一個(gè)臨時(shí)變量來獲取當(dāng)前的隊(duì)頭
        // 1. 先把 front 對(duì)應(yīng)的值保留到一個(gè)臨時(shí)變量
        // 2. 將 front 后移, 考慮取模
        // 3. 將臨時(shí)保存的變量返回
        int value = front;
        front = (front + 1) % maxSize;
        return arr[value];
    // 求出當(dāng)前隊(duì)列有效數(shù)據(jù)的個(gè)數(shù)
    public int size() {
        return (rear - front + maxSize) % maxSize;
    // 顯示隊(duì)列的所有數(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]);
    // 顯示隊(duì)列的頭數(shù)據(jù)， 注意不是取出數(shù)據(jù)
    public int headQueue() {
        // 判斷隊(duì)列是空
        if (isEmpty()) {
            throw new RuntimeException("隊(duì)列空的，沒有數(shù)據(jù)~~");
        return arr[front];

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

LinkedList 類實(shí)現(xiàn)了 Queue 接口，因此我們可以把 LinkedList 當(dāng)成 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()方法在失敗的時(shí)候會(huì)拋出異常(不推薦)
        Queue<Integer> queue = new LinkedList<>();
        //offer() 將指定的元素添加為此列表的尾部（最后一個(gè)元素）。
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        for (Integer nums:queue) {
            System.out.println(nums);
        }
        //poll() 檢索并刪除此列表的頭（第一個(gè)元素）。
        //當(dāng)集合為空時(shí)，返回 null
        queue.poll();
        //queue.poll();
        //remove() 檢索并刪除此列表的頭（第一個(gè)元素）。
        //當(dāng)集合為空時(shí)，出現(xiàn)異常 java.util.NoSuchElementException;
        queue.remove();
        //element() 檢索但不刪除此列表的頭（第一個(gè)元素）。
        //當(dāng)隊(duì)列為空時(shí)，java.util.NoSuchElementException
        //System.out.println("隊(duì)列的頭部：" + queue.element());
        //peek() 檢索但不刪除此列表的頭（第一個(gè)元素）。
        //當(dāng)隊(duì)列為空時(shí)，返回null
        System.out.println("隊(duì)列的頭部：" + queue.peek());
    }
}

poll，remove 區(qū)別：

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

peek，element區(qū)別：

element() 和 peek() 用于在隊(duì)列的頭部查詢?cè)亍Ｅc remove() 方法類似，在隊(duì)列為空時(shí)， element() 拋出一個(gè)異常，而 peek() 返回 null。

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

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

您可能感興趣的文章: