天天看點
傳回

資料結構與算法--003-隊列數組實作--Java

隊列介紹

目錄

  • ​​隊列介紹​​
  • ​​數組模拟隊列思路​​
  • ​​存入資料的思路,addQueue​​
  • ​​取出資料getQueue​​
  • ​​建立隊列​​
  • ​​判斷隊列是否滿​​
  • ​​判斷是否為空​​
  • ​​顯示所有資料​​
  • ​​檢視頭元素​​
  • ​​完整代碼​​
  • ​​數組的循環隊列​​
  • ​​概述​​
  • ​​說明​​
  • ​​代碼實作​​
  • ​​顯示所有資料​​
  • ​​取出資料​​
  • ​​添加元素​​
  • ​​完整代碼​​
  • 隊列是一個有序清單,可以用數組或者連結清單實作
  • 先進先出,先存入隊列的資料， 要先取出。 後存入的要後取出

數組模拟隊列思路

  • 隊列本身就是有序清單,若使用數組的結構來儲存隊列的資料,則maxSize是從該隊列的最大容量
  • 因為隊列的輸出,輸入是分别從前後端來處理,是以需要兩個變量front以及rear分别記錄隊列前後端的下标,front 會随着資料輸出而改變， 而 rear 則是随着資料輸入而改變，
資料結構與算法--003-隊列數組實作--Java

存入資料的思路,addQueue

  1. 将尾指針後移:rear+1,當front == rear 為空
  2. 若尾指針 rear 小于隊列的最大下标 maxSize-1， 則将資料存入 rear 所指的數組元素中， 否則無法存入資料。rear == maxSize - 1[隊列滿] 
public void addQueue(int n) {
        //判斷隊列是否滿
        if (isFull()) {
            System.out.println("隊列已滿");
            return;
        }
        rear++;
        arr[rear] = n;
    }

取出資料getQueue

  1. 将頭指針後移 front++;當front == rear 為空 
public int getQueue() {
        //判斷是否為空
        if (isEmpty()) {
            //抛出異常
            throw new RuntimeException("為空");
        }
        front++;
        return arr[front];
    }

建立隊列 

public ArrayQueue(int arrmaxSize) {
        maxSize = arrmaxSize;
        arr = new int[maxSize];
        front = -1;//指向隊列頭部,分析出front是指向隊列頭的一個位置
        rear = -1;//指向尾部,
    }

判斷隊列是否滿 

public boolean isFull() {
        return rear == maxSize - 1;
    }

判斷是否為空 

public boolean isEmpty() {
        return rear == front;
    }

顯示所有資料 

public void showQueue() {
        //周遊
        if (isEmpty()) {
            System.out.println("隊列為空");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("第" + i + "元素未:\t" + arr[i]);
        }

    }

檢視頭元素 

public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("為空");
        }
        return arr[front + 1];
    }

完整代碼 

package com.nie.queue;

import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //測試
        //4個資料
        ArrayQueue arrayQueue = new ArrayQueue(4);
        Scanner scanner = new Scanner(System.in);
        boolean tag = true;//标簽
        while (tag) {
            System.out.println("輸入[s]\t 顯示隊列");
            System.out.println("輸入[e]\t 退出");
            System.out.println("輸入[a]\t 增添元素到隊列");
            System.out.println("輸入[g]\t 由隊列中取出資料");
            System.out.println("輸入[h]\t 檢視頭部的一個資料");
            char key = scanner.next().charAt(0);//接收一個字元
            switch (key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'e':
                    //退出
                    scanner.close();
                    tag = false;
                    break;
                case 'a':
                    System.out.println("輸入一個資料");
                    int val=scanner.nextInt();
                    arrayQueue.addQueue(val);
                    break;
                case 'g':
                    try {
                        int res=arrayQueue.getQueue();
                        System.out.println("取數的資料為\t:"+res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h':
                    int res = arrayQueue.headQueue();
                    System.out.printf("隊列頭的資料是%d\n", res);
                    break;
                default:
                    break;
            }
        }
    }


}


class ArrayQueue {
    private int maxSize;//表示最大的總量
    private int front;//頭
    private int rear;//尾部
    private int[] arr;//利用數組存放資料,模拟隊列

    /**
     * 建立隊列
     *
     * @param arrmaxSize
     */
    public ArrayQueue(int arrmaxSize) {
        maxSize = arrmaxSize;
        arr = new int[maxSize];
        front = -1;//指向隊列頭部,分析出front是指向隊列頭的一個位置
        rear = -1;//指向尾部,
    }

    /**
     * 判斷隊列是否滿
     */
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    /**
     * 判斷是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }


    /**
     * 添加元素
     */
    public void addQueue(int n) {
        //判斷隊列是否滿
        if (isFull()) {
            System.out.println("隊列已滿");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    /**
     * 取出資料
     * @return
     */
    public int getQueue() {
        //判斷是否為空
        if (isEmpty()) {
            //抛出異常
            throw new RuntimeException("為空");
        }
        front++;
        return arr[front];
    }

    /**
     * 顯示所有資料
     */
    public void showQueue() {
        //周遊
        if (isEmpty()) {
            System.out.println("隊列為空");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("第" + i + "元素未:\t" + arr[i]);
        }

    }

    /**
     * 檢視頭元素
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("為空");
        }
        return arr[front + 1];
    }

}
資料結構與算法--003-隊列數組實作--Java
資料結構與算法--003-隊列數組實作--Java

數組的循環隊列

概述

利用數組,将數組看成為一個環形,(通過取模來實作)

說明

  1. 尾索引的下一個為頭索引時表示隊列滿， (rear + 1) % maxSize == front 滿
  2. rear == front隊空
資料結構與算法--003-隊列數組實作--Java
  • ront 指向隊列元素的一個元素,初始值為 0
  • rear 指向隊列的最後一個元素的後一個位置. 空出一個空間,以便控制是否滿. 初始值為 0
  • 判斷隊列滿 (rear + 1) % maxSize == front
  • rear == front 隊空
  • 有效的元素為:(rear+maxSize-front)%maxSize

代碼實作

顯示所有資料

通過取模 i%maxSize 擷取資料

System.out.println(“第” + i%maxSize + “元素未:\t” + arr[i%maxSize]);

public void showQueue() {
        //周遊
        if (isEmpty()) {
            System.out.println("隊列為空");
            return;
        }
        for (int i = front; i < front+size(); i++) {
            System.out.println("第" + i%maxSize + "元素未:\t" + arr[i%maxSize]);
        }

    }

取出資料

  • 這裡需要分析出 front 是指向隊列的第一個元素

    先把 front 對應的值保留到一個臨時變量 int val=arr[front];

  • 将 front 後移, 考慮取模 front=(front+1)%maxSize;
  • 将臨時儲存的變量傳回 return val; 
public int getQueue() {
        //判斷是否為空
        if (isEmpty()) {
            //抛出異常
            throw new RuntimeException("為空");
        }
        //将頭部元素指派
        int val=arr[front];
        front=(front+1)%maxSize;
        return val;
    }

添加元素

  • 直接将資料加入 arr[rear] = n;
  • 将 rear 後移, 這裡必須考慮取模 rear = (rear + 1) % maxSize; 
public void addQueue(int n) {
        //判斷隊列是否滿
        if (isFull()) {
            System.out.println("隊列已滿");
            return;
        }
        //直接将資料加入
        arr[rear] = n;
        //将 rear 後移, 這裡必須考慮取模
        rear = (rear + 1) % maxSize;
    }

完整代碼 

package com.nie.queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {
        //測試
        //4個資料
        CircleArray circleArray = new CircleArray(3);
        Scanner scanner =new Scanner(System.in);
        boolean tag = true;//标簽
        while (tag) {
            System.out.println("目前的資料個數為:\t"+circleArray.size());
            System.out.println("輸入[s]\t 顯示隊列");
            System.out.println("輸入[e]\t 退出");
            System.out.println("輸入[a]\t 增添元素到隊列");
            System.out.println("輸入[g]\t 由隊列中取出資料");
            System.out.println("輸入[h]\t 檢視頭部的一個資料");
            char key = scanner.next().charAt(0);//接收一個字元
            switch (key){
                case 's':
                    circleArray.showQueue();
                    break;
                case 'e':
                    //退出
                    scanner.close();
                    tag = false;
                    break;
                case 'a':
                    System.out.println("輸入一個資料");
                    int val=scanner.nextInt();
                    circleArray.addQueue(val);
                    break;
                case 'g':
                    try {
                        int res=circleArray.getQueue();
                        System.out.println("取數的資料為\t:"+res);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h':
                    int res = circleArray.headQueue();
                    System.out.printf("隊列頭的資料是%d\n", res);
                    break;
                default:
                    break;
            }
        }
    }
}

class CircleArray {

    private int maxSize;//表示最大的總量
    //front 指向隊列元素的一個元素,初始值為   0
    private int front;//頭
    //rear 指向隊列的最後一個元素的後一個位置. 空出一個空間,以便控制是否滿. 初始值圍毆 0
    private int rear;//尾部
    private int[] arr;//利用數組存放資料,模拟隊列

    /**
     * 建立隊列
     *
     * @param arrmaxSize
     */
    public CircleArray(int arrmaxSize) {
        maxSize = arrmaxSize;
        arr = new int[maxSize];
    }

    /**
     * 判斷隊列是否滿
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判斷是否為空
     *
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }


    /**
     * 添加元素
     */
    public void addQueue(int n) {
        //判斷隊列是否滿
        if (isFull()) {
            System.out.println("隊列已滿");
            return;
        }
        //直接将資料加入
        arr[rear] = n;
        //将 rear 後移, 這裡必須考慮取模
        rear = (rear + 1) % maxSize;
    }

    /**
     * 取出資料
     * @return
     */
    public int getQueue() {
        //判斷是否為空
        if (isEmpty()) {
            //抛出異常
            throw new RuntimeException("為空");
        }
        //将頭部元素指派
        int val=arr[front];
        front=(front+1)%maxSize;
        return val;
    }

    /**
     * 顯示所有資料
     */
    public void showQueue() {
        //周遊
        if (isEmpty()) {
            System.out.println("隊列為空");
            return;
        }
        for (int i = front; i < front+size(); i++) {
            System.out.println("第" + i%maxSize + "元素未:\t" + arr[i%maxSize]);
        }

    }

    /**
     * 取出元素
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("為空");
        }
        return arr[front + 1];
    }

    /**
     * 目前有效資料的個數
     * @return
     */
    public int size(){
        return  (rear+maxSize-front)%maxSize;
    }

}
資料結構與算法--003-隊列數組實作--Java
資料結構與算法--003-隊列數組實作--Java
隊列 算法 資料結構 java 資料
上一篇: LC0141-環形連結清單---LC0142-環形連結清單 II
下一篇: for循環如果先--_97-for循環嵌套 輸出反倒直角三角形

繼續閱讀