學(xué)習(xí)過(guò)數(shù)據(jù)結(jié)構(gòu)的小伙伴們,想來(lái)對(duì)最常用的數(shù)據(jù)結(jié)構(gòu)之一的隊(duì)列是不陌生的吧。沒(méi)學(xué)過(guò)的也不用緊張,下文將簡(jiǎn)單為大家介紹關(guān)于數(shù)據(jù)結(jié)構(gòu)中隊(duì)列的一些簡(jiǎn)單的概念以及具體的實(shí)現(xiàn)思路。并通過(guò)Java數(shù)組的形式來(lái)模擬數(shù)據(jù)結(jié)構(gòu)中環(huán)形隊(duì)列的實(shí)現(xiàn)。
一、隊(duì)列是什么
我們先來(lái)看下百科的解釋?zhuān)?br>
隊(duì)列是一種特殊的線性表,特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作,而在表的后端(rear)進(jìn)行插入操作,隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱(chēng)為隊(duì)尾,進(jìn)行刪除操作的端稱(chēng)為隊(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ì)列滿(mǎn)
這個(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)有滿(mǎn),我們又無(wú)法繼續(xù)往隊(duì)列里添加數(shù)據(jù)。這個(gè)時(shí)候其實(shí)有兩種解決方案。
方案一:我們每消費(fèi)一個(gè)元素,其后面的元素都整體往前移動(dòng)一位,就像我們生活中排隊(duì)打飯一樣,后面的人都往前挪一挪。但這種方案帶來(lái)的后果是,帶來(lái)的時(shí)間開(kāi)銷(xiāo)太大,因?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ì)列滿(mǎn)標(biāo)記,當(dāng)隊(duì)列是滿(mǎn)的時(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)滿(mǎn)了
if (isFullFlag){
System.out.println("隊(duì)列已滿(mǎn),無(wú)法繼續(xù)添加元素");
return false;
}
// 添加元素
values[rear] = e;
// 元素個(gè)數(shù)加一
number++;
// 尾指針后移一位,若已經(jīng)指向數(shù)組最后的下表,則重新指向0
if (rear == size-1){
rear = 0;
}else{
rear++;
}
// 添加完這個(gè)元素,判斷隊(duì)列是否已經(jīng)滿(mǎn)了,若滿(mǎn)則標(biāo)記為true
if (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ù)組最后的下表,則重新指向0
if (front==size-1){
front = 0;
}else {
front++;
}
// 取隊(duì)列之前若是滿(mǎn)的狀態(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),您可以使用以下功能。
添加: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ì)列詳情為:
"+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ù)組來(lái)模擬數(shù)據(jù)結(jié)構(gòu)中的環(huán)形隊(duì)列實(shí)現(xiàn)的全部?jī)?nèi)容,想要了解更多相關(guān)java 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容,請(qǐng)搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望本篇文章能夠?qū)Υ蠹业膶W(xué)習(xí)或者工作能夠有所幫助!