本篇文章主要講述了使用數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列的思路以及具體代碼

一、隊(duì)列是什么

我們先來(lái)看下百科的解釋：隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。總結(jié)起來(lái)兩點(diǎn)：1.一種線性表2.添加操作只能在表尾，刪除操作在表頭（先進(jìn)先出）

二、實(shí)現(xiàn)隊(duì)列的思路 1.初始化一個(gè)空隊(duì)列

初始化一個(gè)大小固定的數(shù)組，并將頭指針，尾指針都指向下表為0的位置，但其實(shí)這種初始化頭指針指向的是隊(duì)首，尾指針指向的是隊(duì)尾的后一個(gè)元素。

2.往隊(duì)列里添加元素

往隊(duì)列里添加元素，尾指針后移一位。

一直添加直到隊(duì)列滿

這個(gè)時(shí)候尾指針已經(jīng)出現(xiàn)在數(shù)組下標(biāo)外了

3.消費(fèi)隊(duì)列元素

每消費(fèi)一個(gè)隊(duì)列元素，頭指針指向的元素出隊(duì)，并且后移一位

再消費(fèi)兩個(gè)

這個(gè)時(shí)候我們想往隊(duì)列里繼續(xù)添加元素，尾指針后移，然后發(fā)現(xiàn)出現(xiàn)了假溢出的情況，因?yàn)槲仓羔槦o(wú)法再向后移動(dòng)，而隊(duì)列實(shí)際上并沒(méi)有滿，我們又無(wú)法繼續(xù)往隊(duì)列里添加數(shù)據(jù)。這個(gè)時(shí)候其實(shí)有兩種解決方案。方案一：我們每消費(fèi)一個(gè)元素，其后面的元素都整體往前移動(dòng)一位，就像我們生活中排隊(duì)打飯一樣，后面的人都往前挪一挪。但這種方案帶來(lái)的后果是，帶來(lái)的時(shí)間開(kāi)銷太大，因?yàn)榛旧弦僮魉械脑兀赃@種方案不可行。方案二：尾指針在指向下表為最后一個(gè)元素時(shí)，再添加元素，如果還有空位，就將尾指針重新指向0，頭指針在取到下表數(shù)組末尾時(shí)，如果前面還有元素，頭指針也指向0，這就是我們說(shuō)的環(huán)形隊(duì)列。

三、實(shí)現(xiàn)環(huán)形隊(duì)列1.環(huán)形隊(duì)列示例圖

尾指針重新指向零

再添加一個(gè)元素

連續(xù)消費(fèi)三個(gè)元素，如果前面還有元素，頭指針也指向0

這個(gè)時(shí)候我們發(fā)現(xiàn)那個(gè)原來(lái)熟悉的隊(duì)列又回來(lái)了。

2.代碼實(shí)現(xiàn)

/** * description:數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列 * author: xiaowang * */public class MyQueue<E> { // 隊(duì)列最大個(gè)數(shù) private int size; // 元素真實(shí)個(gè)數(shù) private int number; // 頭指針，指向隊(duì)列的第一個(gè)元素即隊(duì)頭 private int front; // 尾指針，指向隊(duì)尾的后一個(gè)元素(非隊(duì)尾) private int rear; // 隊(duì)列具體值 private Object[] values; // 隊(duì)列滿標(biāo)記，當(dāng)隊(duì)列是滿的時(shí)候?yàn)閠rue private boolean isFullFlag; /**構(gòu)造器*/ public MyQueue(int size){if (size<0){ throw new RuntimeException('初始化隊(duì)列時(shí)，隊(duì)列最大元素個(gè)數(shù)不能為負(fù)');}this.front = 0;this.rear = 0;this.number = 0;this.isFullFlag = false;this.size = size;this.values = new Object[size]; } /**往隊(duì)列里添加元素 添加成功返回true 失敗返回false*/ public boolean addToQueue(E e){// 判斷隊(duì)列是否已經(jīng)滿了if (isFullFlag){ System.out.println('隊(duì)列已滿,無(wú)法繼續(xù)添加元素'); return false;}// 添加元素values[rear] = e;// 元素個(gè)數(shù)加一number++;// 尾指針后移一位，若已經(jīng)指向數(shù)組最后的下表，則重新指向0if (rear == size-1){ rear = 0;}else{ rear++;}// 添加完這個(gè)元素，判斷隊(duì)列是否已經(jīng)滿了，若滿則標(biāo)記為trueif (rear==front){ isFullFlag = true;}return true; } /**從隊(duì)列里取出數(shù)據(jù)，隊(duì)頭數(shù)據(jù)*/ public E getFromQueue(){// 判斷隊(duì)列是否為空if (number==0||size==0){ System.out.println('隊(duì)列為空，無(wú)法從隊(duì)列中獲取數(shù)據(jù)'); return null;}// 臨時(shí)變量E e = (E) values[front];// 隊(duì)頭置空values[front] = null;// 個(gè)數(shù)減一number--;// 頭指針后移，若已經(jīng)指向數(shù)組最后的下表，則重新指向0if (front==size-1){ front = 0;}else { front++;}// 取隊(duì)列之前若是滿的狀態(tài)，則更新?tīng)顟B(tài)if (isFullFlag){ isFullFlag = false;}return e; } /**獲取目前有幾個(gè)元素正在進(jìn)行排隊(duì)*/ public int getNumber(){return number; } /**獲取隊(duì)列的最大個(gè)數(shù)*/ public int getSize(){return size; } /**查看隊(duì)列在數(shù)組里保存的詳細(xì)情況*/ public String toString(){StringBuffer valueStr = new StringBuffer();valueStr.append('[');for (int i = 0; i < size; i++) { if (i!=size-1){valueStr.append(values[i]+','); }else{valueStr.append(values[i]+']'); }}return valueStr.toString(); }}

測(cè)試代碼

public class TestQueue { public static void main(String[] args) {MyQueue<String> queue = new MyQueue<String>(5);Scanner scanner = new Scanner(System.in);Scanner scanner2 = new Scanner(System.in);boolean isCan = true;while (isCan){ System.out.println('歡迎來(lái)到小王排隊(duì)系統(tǒng)，您可以使用以下功能。n添加：1；取出：2；展示：3；獲取排隊(duì)個(gè)數(shù)：4；退出：0。'); int flag = scanner.nextInt(); switch (flag){case 1 : System.out.println('請(qǐng)輸入一個(gè)數(shù)據(jù)：'); String data = scanner2.nextLine(); boolean isSuccess = queue.addToQueue(data); if (isSuccess){System.out.println('添加成功~~~'); } break;case 2 : String dataFromQueue = queue.getFromQueue(); if (dataFromQueue!=null){System.out.println('本次取出的數(shù)據(jù)為：'+dataFromQueue); } break;case 3 : System.out.println('隊(duì)列詳情為：n'+queue.toString()); break;case 4 : System.out.println('目前有'+queue.getNumber()+'個(gè)元素正在進(jìn)行排隊(duì)'); break;default: isCan = false; System.out.println('已退出...'); break; }} }}總結(jié)

到此這篇關(guān)于java中用數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列的示例代碼的文章就介紹到這了,更多相關(guān)java 數(shù)組環(huán)形隊(duì)列內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！