Java隊(duì)列篇之實(shí)現(xiàn)數(shù)組模擬隊(duì)列及可復(fù)用環(huán)形隊(duì)列詳解
隊(duì)列簡(jiǎn)介
隊(duì)列是一個(gè)有序列表，可以用數(shù)組或是鏈表來(lái)實(shí)現(xiàn)。
遵循先入先出的原則。即先存入隊(duì)列的數(shù)據(jù)，先取出，后存入的后取出。
示意圖：(使用數(shù)組模擬隊(duì)列示意圖)
有兩個(gè)分別指向頭部和尾部的“指針”。
數(shù)組模擬隊(duì)列（無(wú)法復(fù)用）
1、實(shí)現(xiàn)思路
隊(duì)列本身是有序列表，若使用數(shù)組的結(jié)構(gòu)來(lái)存儲(chǔ)隊(duì)列的數(shù)據(jù)，則隊(duì)列數(shù)組的聲明如下圖，其中maxSize是該隊(duì)列的最大容量。
因?yàn)殛?duì)列的輸出、輸入是分別從前后端來(lái)處理，因此需要兩個(gè)變量front及rear分別記錄隊(duì)列前后端的下標(biāo)，front會(huì)隨著數(shù)據(jù)輸出而改變，而rear則是隨著數(shù)據(jù)輸入而改變，如圖所示：
當(dāng)我們將數(shù)據(jù)存入隊(duì)列時(shí)稱為addQueue，addQueue的處理需要有兩個(gè)步驟：
①將尾指針往后移。
②若尾指針rear小于隊(duì)列的最大下標(biāo)maxSize-1，則將數(shù)據(jù)存入rear 所指的數(shù)組元素中，否則無(wú)法存入數(shù)據(jù)。
rear+1當(dāng)front== rear[空]
rear==maxSize-1[隊(duì)列滿]
2、代碼實(shí)現(xiàn)
①數(shù)組實(shí)現(xiàn)隊(duì)列類
class ArrQueue {
private int maxSize; //隊(duì)列（數(shù)組）最大容量
private int front; //指向隊(duì)列頭部
private int rear; //指向隊(duì)列尾部
private int[] queue;
//創(chuàng)造隊(duì)列的構(gòu)造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
front = -1; //其實(shí)是隊(duì)列第一個(gè)元素的前一個(gè)索引
rear = -1; //最后一個(gè)元素的索引
}
//判斷是否滿
public boolean isFull(){
return rear == maxSize - 1;
}
//判斷是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("隊(duì)列已經(jīng)滿了，無(wú)法添加！");
return;
}else {
rear++;
queue[rear] = n;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空，無(wú)元素可??！");
}else {
front++;
return queue[front];
}
}
//顯示隊(duì)列
public void showQueue(){
if (isEmpty()){
System.out.println("隊(duì)列為空，沒(méi)有元素可顯示！");
return;
}
for (int i : queue){
System.out.println(i);
}
}
//顯示頭數(shù)據(jù)
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空，沒(méi)有頭數(shù)據(jù)！");
}
int i = front;
System.out.println(queue[++i]);
}
}
②測(cè)試類
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//創(chuàng)建一個(gè)隊(duì)列
ArrQueue arrQueue = new ArrQueue(3);
//創(chuàng)建一個(gè)用戶輸入
Scanner scanner = new Scanner(System.in);
//創(chuàng)建一個(gè)功能菜單
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:顯示隊(duì)列");
System.out.println("a:添加數(shù)據(jù)");
System.out.println("g:取出數(shù)據(jù)");
System.out.println("h:顯示頭數(shù)據(jù)");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("請(qǐng)輸入一個(gè)數(shù)：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
數(shù)組模擬環(huán)形隊(duì)列（可復(fù)用）
對(duì)前面的數(shù)組模擬隊(duì)列的優(yōu)化，充分利用數(shù)組。將數(shù)組看做是一個(gè)環(huán)形的，即取出之后，有位置可以空出來(lái)添加。(通過(guò)取模的方式來(lái)實(shí)現(xiàn)即可)
分析說(shuō)明:
①尾索引的下一個(gè)為頭索引時(shí)表示隊(duì)列滿，即將隊(duì)列容量空出一個(gè)作為約定。在作判斷隊(duì)列滿的時(shí)候需要注意(rear+ 1) % maxSize== front [滿]
②rear == front [空]
1、思路如下:
①front 變量的含義調(diào)整：front 指向隊(duì)列的第一個(gè)元素, 也就是說(shuō)arr[front]就是隊(duì)列的第一個(gè)元素，front的初始值為0。
②rear 變量的含義調(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 + maxSize - front) % maxSize
⑥我們就可以在原來(lái)的隊(duì)列上修改得到一個(gè)環(huán)形隊(duì)列
2、代碼實(shí)現(xiàn)
①數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列類
class ArrQueue {
private int maxSize; //隊(duì)列（數(shù)組）最大容量
private int front; //指向隊(duì)列頭部，隊(duì)列第一個(gè)元素的索引
private int rear; //指向隊(duì)列尾部，隊(duì)列最后一個(gè)元素的后一個(gè)索引
private int[] queue;
//創(chuàng)造隊(duì)列的構(gòu)造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
}
//判斷是否滿
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
//判斷是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("隊(duì)列已經(jīng)滿了，無(wú)法添加！");
return;
}else {
queue[rear] = n;
rear = (rear + 1) % maxSize;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空，無(wú)元素可取！");
}else {
int data = queue[front];
front = (front + 1) % maxSize;
return data;
}
}
//顯示隊(duì)列
public void showQueue(){
if (isEmpty()){
System.out.println("隊(duì)列為空，沒(méi)有元素可顯示！");
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d] = %d\n",i % maxSize,queue[i % maxSize]);
}
}
//求當(dāng)前隊(duì)列有效數(shù)據(jù)個(gè)數(shù)
public int size(){
return (rear + maxSize - front) % maxSize;
}
//顯示頭數(shù)據(jù)
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("隊(duì)列為空，沒(méi)有頭數(shù)據(jù)！");
}
System.out.println(queue[front]);
}
}
②測(cè)試類
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//創(chuàng)建一個(gè)隊(duì)列
ArrQueue arrQueue = new ArrQueue(3); //說(shuō)明該環(huán)形隊(duì)列的最大有效數(shù)據(jù)為2
//創(chuàng)建一個(gè)用戶輸入
Scanner scanner = new Scanner(System.in);
//創(chuàng)建一個(gè)功能菜單
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:顯示隊(duì)列");
System.out.println("a:添加數(shù)據(jù)");
System.out.println("g:取出數(shù)據(jù)");
System.out.println("h:顯示頭數(shù)據(jù)");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("請(qǐng)輸入一個(gè)數(shù)：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
到此這篇關(guān)于Java隊(duì)列篇之實(shí)現(xiàn)數(shù)組模擬隊(duì)列及可復(fù)用環(huán)形隊(duì)列詳解的文章就介紹到這了,更多相關(guān)Java 隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
引入緩存，主要用于實(shí)現(xiàn)系統(tǒng)的高性能，高并發(fā)，這篇文章主要介紹了Java實(shí)現(xiàn)本地緩存的幾種方式,本文結(jié)合示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-07-07
Spring Boot整合EasyExcel(完整版包含上傳解析excel和下載模板)
這篇文章主要介紹了Spring Boot整合EasyExcel(完整版包含上傳解析excel和下載模板),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
解決@SpringBootTest 單元測(cè)試遇到的坑
這篇文章主要介紹了解決@SpringBootTest 單元測(cè)試遇到的坑，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
淺談Mybatis中resultType為hashmap的情況
這篇文章主要介紹了淺談Mybatis中resultType為hashmap的情況，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12
Java開(kāi)發(fā)之spring security實(shí)現(xiàn)基于MongoDB的認(rèn)證功能
這篇文章主要介紹了Java開(kāi)發(fā)之spring security實(shí)現(xiàn)基于MongoDB的認(rèn)證功能,結(jié)合實(shí)例形式分析了spring security在非JDBC環(huán)境下的自定義認(rèn)證服務(wù)實(shí)現(xiàn)技巧,需要的朋友可以參考下2017-11-11
HttpClient HttpRoutePlanner接口確定請(qǐng)求目標(biāo)路由
這篇文章主要為大家介紹了使用HttpClient HttpRoutePlanner接口確定請(qǐng)求目標(biāo)路由,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-10-10
使用jpa的實(shí)體對(duì)象轉(zhuǎn)json符串時(shí)懶加載的問(wèn)題及解決
這篇文章主要介紹了使用jpa的實(shí)體對(duì)象轉(zhuǎn)json符串時(shí)懶加載的問(wèn)題及解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-02-02
這篇文章主要介紹了Java基礎(chǔ)之包裝類,文中有非常詳細(xì)的代碼示例及基礎(chǔ)知識(shí)詳解,對(duì)正在學(xué)習(xí)java基礎(chǔ)的小伙伴們有很大的幫助喲,需要的朋友可以參考下2021-05-05
SpringBoot 集成Kaptcha實(shí)現(xiàn)驗(yàn)證碼功能實(shí)例詳解
在一個(gè)web應(yīng)用中驗(yàn)證碼是一個(gè)常見(jiàn)的元素。今天給大家介紹一下kaptcha的和springboot一起使用的簡(jiǎn)單例子。感興趣的朋友參考下吧2017-08-08
Java面向?qū)ο缶幊讨^承和多態(tài)以及包的解析與使用范例
繼承就是可以直接使用前輩的屬性和方法。自然界如果沒(méi)有繼承，那一切都是處于混沌狀態(tài)。多態(tài)是同一個(gè)行為具有多個(gè)不同表現(xiàn)形式或形態(tài)的能力。多態(tài)就是同一個(gè)接口，使用不同的實(shí)例而執(zhí)行不同操作2021-11-11