您好,登錄后才能下訂單哦!
這篇文章主要介紹“Java單向隊列及環(huán)形隊列的實現(xiàn)原理是什么”,在日常操作中,相信很多人在Java單向隊列及環(huán)形隊列的實現(xiàn)原理是什么問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”Java單向隊列及環(huán)形隊列的實現(xiàn)原理是什么”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
1.可以使用數(shù)組和鏈表兩種方式來實現(xiàn)。
2.遵循先入先出(FIFO)的規(guī)則,即先進入的數(shù)據(jù)先出。
3.屬于有序列表。
1.定義一個固定長度的數(shù)組,長度為maxSize。
2.設(shè)置兩個指針first = -1(指向隊列第一個數(shù)據(jù)的前一位,這樣保證在添加第一個數(shù)據(jù)以后頭指針為0,和數(shù)組的下標(biāo)一樣,且用于操作出隊)和last = -1(指向隊尾,用于操作入隊)。
3.即first會因為出隊操作而增加,last會因為入隊操作而增加
代碼實現(xiàn):
package 隊列; public class ArrayQueueTest { public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue(3); arrayQueue.addQueue("瓊"); arrayQueue.addQueue("赟"); arrayQueue.addQueue("瓏"); arrayQueue.showAllQueueData(); System.out.println(arrayQueue.getQueue()); } } class ArrayQueue{ private int maxSize;//定義隊列的最大長度 private int first ;//指向隊列頭的前一個位置!!前一個位置??!出隊方向 private int last ;//指向隊列尾部!!即最后一個數(shù)據(jù)?。。∪腙牱较? private String[] arr; //先建一個空的數(shù)組,具體長度未知,需要maxSize來確定。 //構(gòu)造器初始化隊列信息 public ArrayQueue(int maxSize){ this.maxSize = maxSize; this.first = -1; this.last = -1; arr = new String[maxSize]; } //判斷是否為空 public boolean isEmpty(){ if (first == last) { System.out.println("隊列為空~~"); return true; }else { System.out.println("隊列不為空~~"); return false; } } //判斷隊列是否滿 public boolean isFull(){ if (last == maxSize-1) { System.out.println("隊列已滿~~"); return true; }else { System.out.println("隊列未滿~~"); return false; } } //入隊 public void addQueue(String data){ if (last == maxSize-1){ System.out.println("隊列已滿,不能再添加??!"); return; }else { last++; //添加數(shù)據(jù)只和末尾下標(biāo)有關(guān) arr[last] = data; return; } } //出隊 public String getQueue(){ if (isEmpty()) { //因為getQueue方法是int型,需要返回數(shù)據(jù),如果無數(shù)據(jù),也需要返回 //如果返回-1或者其他數(shù)據(jù),會讓人誤解獲取到的數(shù)就是-1或者其他 //所以用拋出異常來處理 throw new RuntimeException("隊列為空,無數(shù)據(jù)~~"); } else { first++; return arr[first]; } } //遍歷隊列所有信息 public void showAllQueueData(){ if (first == last){ return; } for (int i = 0; i < arr.length; i++) { System.out.println("arr["+i+"]"+"="+arr[i]); } } //獲取隊列頭數(shù)據(jù) public String headQueueData(){ if (isEmpty()){ throw new RuntimeException("無數(shù)據(jù)~~~"); } return arr[++first]; } }
隊列缺點:
由于出隊操作,使得first指針上移變大,導(dǎo)致數(shù)組前面空出來的位置就不能再繼續(xù)添加數(shù)據(jù),即不能再被重復(fù)使用,這樣一個隊列只能使用一次,內(nèi)存效率太低,所以需要使用環(huán)形隊列來優(yōu)化解決。
1.first指針初始默認(rèn)設(shè)置為0,指向隊列頭部,則arr[first] 就是第一個數(shù)據(jù)。
2.last指針初始默認(rèn)也為0,但是會隨著增加數(shù)據(jù)而后移。
3.隊列滿的條件:
(last + 1) % maxSize == first
last+1是為了讓指針后移,而且如果不設(shè)置為 last+1 那么一開始的時候last為0 , last % maxSize == 0,且first也為0,還沒加數(shù)據(jù)就滿了。
4.隊列為空的條件:
first == last
5.由于判斷是否滿的時候: last+1 ,導(dǎo)致實際上可以裝的數(shù)據(jù)比數(shù)組長度少 1
1.隊列初始化 :
class CircleArryQueue{ private int maxSize ; //數(shù)組長度,即隊列最大容量 private int first; //頭指針,控制出隊操作 private int last; //尾指針,控制入隊操作 private int[] arr; //數(shù)組類型,可以換其他的。 //構(gòu)造器初始化信息 public CircleArryQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加,不叫也是默認(rèn)為0 this.last = 0; } }
2.判斷隊列是否為空:
public boolean isEmpty(){ //頭指針和尾指針一樣 則說明為空 return last == first; }
3.判斷隊列是否滿:
/* *這里的 last+1 主要是為了讓指針后移,特別是在隊列尾部添加數(shù)據(jù)的時候,本來用last也可以判斷,但 *是一開始還沒加數(shù)據(jù)的時候,如果直接用last % maxSize == first,結(jié)果是true,所以為了解決指針后*移和判斷是否滿,用來last+1。其次,因為last+1可能會導(dǎo)致數(shù)組指針越界,所以用取模來控制它的范 * 圍,同時保證他會在一個固定的范圍循環(huán)變換,也利于環(huán)形隊列的實現(xiàn)。 */ public boolean isFull(){ return (last + 1) % maxSize == first; }
4.添加數(shù)據(jù)到隊列尾部:入隊
public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經(jīng)滿啦~~"); return; } arr[last] = data; //last+1是為了后移,取模是為了避免指針越界,同時可以讓指針循環(huán) last = (last + 1) % maxSize; }
5.取出隊首數(shù)據(jù):出隊
public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數(shù)據(jù)了 new RuntimeException("隊列為空,沒有獲取到數(shù)據(jù)~~"); } //要先把first對應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回數(shù)據(jù) int value = arr[first]; //first+1的操作和last+1是一樣的,取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數(shù)據(jù)就不對了 //如果直接返回數(shù)據(jù),那first指針還沒后移 也不對,所以需要使用第三方變量 }
6.展示隊列中所有數(shù)據(jù):
public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空,沒有數(shù)據(jù)~~"); return; } //此處i不為0,是因為有可能之前有過popData()操作,使得firs不為0,所以最好使用 //first給i動態(tài)賦值, for (int i = first; i < first+size() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); }
7.獲取隊列中數(shù)據(jù)的總個數(shù):
public int dataNum(){ //韓順平老師的教程上是這樣寫,但是我理解不了..........。 return (last+maxSize-first) % maxSize; }
8.查看隊首數(shù)據(jù)但不彈出:
public void seeFirstData(){ return arr[first]; }
全部代碼整合:
package 練習(xí); import java.util.Scanner; public class CircleArryQueue { public static void main(String[] args){ CircleQueue circleQueue = new CircleQueue(4); System.out.println("--------測試環(huán)形隊列--------"); char key = ' '; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("s(showAllData):查看隊列數(shù)據(jù)"); System.out.println("p(pushData):隊尾添加數(shù)據(jù)"); System.out.println("g(popData):彈出隊頭數(shù)據(jù)"); System.out.println("h(seefirstData):獲取隊頭數(shù)據(jù)"); System.out.println("e(exit):退出程序"); key = scanner.next().charAt(0); switch (key){ case 's': circleQueue.showAllData(); break; case 'p': System.out.println("輸入一個數(shù)據(jù):"); int obj = scanner.nextInt(); circleQueue.pushData(obj); break; case 'g': circleQueue.popData(); break; case 'h': circleQueue.seeFirstData(); break; case 'e': scanner.close(); flag = false; break; default: break; } } System.out.println("程序結(jié)束~~~"); } } class CircleQueue { private int maxSize ; //數(shù)組長度,即隊列最大容量 private int first; //頭指針,控制出隊操作 private int last; //尾指針,控制入隊操作 private int[] arr; //數(shù)組類型,可以換其他的。 //構(gòu)造器初始化信息 public CircleQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; this.first = 0; //這兩個可以不加,不叫也是默認(rèn)為0 this.last = 0; } public boolean isEmpty(){ //頭指針和尾指針一樣 則說明為空 return last == first; } /* *這里的 last+1 主要是為了讓指針后移,特別是在隊列尾部添加數(shù)據(jù)的時候,本來用last也可以判斷但 *是一開始還沒加數(shù)據(jù)的時候,如果直接用last % maxSize == first,結(jié)果是true,所以為了解決指針 *后移和判斷是否滿,用來last+1。其次,因為last+1可能會導(dǎo)致數(shù)組指針越界,所以用取模來控制它 *的范圍,同時保證他會在一個固定的范圍循環(huán)變換,也利于環(huán)形隊列的實現(xiàn)。 */ public boolean isFull(){ return (last + 1) % maxSize == first; } public void pushData(int data){ //先判斷是否滿了 if(isFull()){ System.out.println("隊列已經(jīng)滿啦~~"); return; } arr[last] = data; //last+1是為了后移,取模是為了避免指針越界,同時可以讓指針循環(huán) last = (last + 1) % maxSize; } public int popData(){ if (isEmpty()) { //拋異常就可以不用返回數(shù)據(jù)了 throw new RuntimeException("隊列為空,沒有獲取到數(shù)據(jù)~~"); } //要先把first對應(yīng)的數(shù)組數(shù)據(jù)保存——>first后移——>返回數(shù)據(jù) int value = arr[first]; //first+1的操作和last+1是一樣的,取模也是 first = (first+1) % maxSize; System.out.println(value); return value; //如果不保存first指針 那么返回的數(shù)據(jù)就不對了 //如果直接返回數(shù)據(jù),那first指針還沒后移 也不對,所以需要使用第三方變量 } //查看所有數(shù)據(jù) public void showAllData(){ if (isEmpty()) { System.out.println("隊列為空,沒有數(shù)據(jù)~~"); } //此處i不為0,是因為有可能之前有過popData()操作,使得firs不為0,所以最好使用 //first給i動態(tài)賦值, for (int i = first; i < first+dataNum() ; i++) { System.out.println("arr["+i%maxSize+"]"+arr[i%maxSize]); } } //查看有效數(shù)據(jù)個數(shù) public int dataNum(){ //韓順平老師的教程上是這樣寫,但是我理解不了..........。 return (last+maxSize-first) % maxSize; } //查看隊列第一個數(shù)據(jù) public int seeFirstData(){ System.out.println(arr[first]); return arr[first]; } }
到此,關(guān)于“Java單向隊列及環(huán)形隊列的實現(xiàn)原理是什么”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。