您好,登錄后才能下訂單哦!
這篇文章主要介紹java如何實現(xiàn)隊列queue數(shù)據(jù)結(jié)構(gòu),文中介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們一定要看完!
隊列是一種非原始(特殊)的線性表,是一種先進先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)。它只允許在表的前端(front)進行刪除操作,而在表的后端(rear)進行插入操作。
FIFO:first input first output,即先添加的元素,先移除,最后添加的元素,最后移除。
工作方式類似于商場排隊結(jié)賬情形:
數(shù)組模擬隊列圖示:
插入值操作:insert ——》 enqueue(入隊) ——》參數(shù)是要插入的數(shù)據(jù)data
刪除值操作:remove ——》 dequeue (出隊)——》 無參
如果 FRONT = 0,那么隊列就是空的。
如果 REAR = size of the queue,那么隊列就是滿了。
如果 FRONT = REAR,那么隊列中至少有一個元素。
如果你想知道隊列中元素的總數(shù),那么使用這個公式計算(REAR - FRONT)+1。
我們可以通過數(shù)組、堆棧和鏈表來實現(xiàn)隊列。其中數(shù)組是實現(xiàn)隊列的最簡單方法。
創(chuàng)建一個大小為 n 的數(shù)組。將 FRONT 和 REAR 的值初始化為 -1,該值表示該數(shù)組當前為空。
編寫一個ArrayQueue類如下:
class ArrayQueue { private int maxSize; // 數(shù)組的最大容量 private int front; // 隊列頭 private int rear; // 隊列尾 private int[] arr; // 存放數(shù)據(jù), 模擬隊列 // 創(chuàng)建構(gòu)造器,初始化 public ArrayQueue(int arrMaxSize) { maxSize = arrMaxSize; arr = new int[maxSize]; front = -1; // front 是指向隊列頭的前一個位置 rear = -1; // rear 是指向隊列尾的數(shù)據(jù)(最后一個數(shù)據(jù)) } // 判斷隊列是否已滿 public boolean isFull() { return rear == maxSize - 1; } // 判斷隊列是否為空 public boolean isEmpty() { return rear == front; } // 添加數(shù)據(jù) public void addQueue(int n) { if (isFull()) { System.out.println("隊列已滿,不能再添加數(shù)據(jù)了!"); return; } rear++; // 讓rear 后移 arr[rear] = n; } // 獲取數(shù)據(jù) public int getQueue() { if (isEmpty()) { // 通過拋出異常 throw new RuntimeException("隊列為空,無數(shù)據(jù)可??!"); } front++; // front后移 return arr[front]; } // 顯示隊列的所有數(shù)據(jù) public void showQueue() { if (isEmpty()) { System.out.println("隊列空的,沒有數(shù)據(jù)~~"); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]=%d\n", i, arr[i]); } } // 顯示隊列的頭部指向的下一個 public int headQueue() { if (isEmpty()) { throw new RuntimeException("隊列為空,沒有數(shù)據(jù)~~"); } return arr[front + 1]; } }
編寫測試方法:
//創(chuàng)建一個隊列 ArrayQueue queue = new ArrayQueue(3); char key = ' '; Scanner scanner = new Scanner(System.in);// boolean loop = true; //輸出一個菜單選項 while(loop) { System.out.println("s(show): 顯示隊列"); System.out.println("e(exit): 退出程序"); System.out.println("a(add): 添加數(shù)據(jù)到隊列"); System.out.println("g(get): 從隊列取出數(shù)據(jù)"); System.out.println("h(head): 查看隊列頭的數(shù)據(jù)"); key = scanner.next().charAt(0);//接收一個字符 switch (key) { case 's': //顯示隊列所有數(shù)據(jù) queue.showQueue(); break; case 'a': //添加數(shù)據(jù) System.out.println("輸出一個數(shù)"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': //依次取出數(shù)據(jù) try { int res = queue.getQueue(); System.out.printf("取出的數(shù)據(jù)是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'h': //查看隊列頭指向 try { int res = queue.headQueue(); System.out.printf("隊列頭的數(shù)據(jù)是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出程序 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); }
以上是“java如何實現(xiàn)隊列queue數(shù)據(jù)結(jié)構(gòu)”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(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)容。