文章目錄
- ?什么是佇列
- 💥佇列的定義
- ?佇列的方法
- 💦佇列的分類
- 0?? 鏈式佇列
- 1?? 單向佇列
- 2?? 雙向佇列
- 3?? 回圈佇列
- 💕佇列導圖
- ?光腳造輪子
- 🎈練習題
?什么是佇列
💥佇列的定義
?佇列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行洗掉操作，而在表的后端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭，
圖片來源于網路，
?佇列的方法
| 方法名 | 回傳值型別 | 方法體 | 描述 |
|---|---|---|---|
isEmpty | boolean | boolean isEmpty() | 檢測佇列是否為空，為空則回傳true |
peek | Object | Object peek( ) | 查看佇列首部的物件并回傳，但不從佇列中移除它， |
poll | Object | Object pool( ) | 移除佇列頂部的物件，并作為此函式的值回傳該物件， |
remove | Object | Object remove() | 和poll方法用法一致，但如果佇列為空則會拋出例外 |
add | Object | Object add(Object element) | 把物件壓入佇列，如果佇列已滿，會拋出例外 |
offer | Object | Object offer(Object element) | 和add方法類似，但如果佇列已滿，不會拋出例外，會回傳null |
size | int | int size() | 回傳佇列中存在的元素數量 |
💦佇列的分類
0?? 鏈式佇列
鏈式佇列的容量在理論上來說是無限大的，一般是基于鏈表進行實作的，
1?? 單向佇列
?這類佇列只能從佇列的一個方向進，從另外一個方向出，只能單向操作佇列里面的內容，結構比較簡單，底層實作一般是基于鏈表，
2?? 雙向佇列
?雙向對列，又叫雙端佇列（deque）是指允許兩端都可以進行入隊和出隊操作的佇列，deque 是 “double ended queue” 的簡稱，那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊，雙端佇列比普通的佇列更加靈活，雙端佇列可以用雙向鏈表實作，
3?? 回圈佇列
?回圈佇列一般都是確定大小的，因為是確定大小的，所以一般使用陣列進行實作，在佇列元素占滿的情況下，當一個元素出佇列以后，后面的元素是不能進來的，這就造成了佇列空間的浪費，所以我們在實作回圈佇列的時候，一旦有資料出佇列，我們將后面所有的資料往前搬一個單位，這時候主要后進佇列的資料沒有追上前面的資料，則說明佇列仍還可以進行資料存盤，
💕佇列導圖
?光腳造輪子
使用單向鏈表構建一個單向佇列，并且實作其
size、isEmpty、poll、add、peek方法，難度【簡單】
/*
* 結點類
* */
class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
next = null;
}
}
/*
* 使用尾插
* */
public class LinkedListQueue {
ListNode root;
ListNode last;
int size;
/*
* 構造方法
* */
public LinkedListQueue(){
root = null;
size = 0;
}
/*
* size()方法
* */
public int size(){
return size;
}
/*
* peek()方法
* */
public int peek(){
return root.val;
}
/*
* poll()方法
* */
public int poll(){
int ret = root.val;
root = root.next;
size--;
return ret;
}
/*
* add()方法
* */
public int add(int val){
ListNode last = root;
for(int i = 1;i<size;i++){
last = root.next;
}
last.next = new ListNode(val);
size++;
return val;
}
/*
* isEmpty()方法
* */
public boolean isEmpty(){
return (size == 0);
}
}
可以自己將雙向鏈表實作的雙向佇列實作，也可以使用陣列實作一個回圈佇列
🎈練習題
- ? 【用佇列實作堆疊】LeetCode 225【簡單】👉點我立即練習
- ? 【無法吃午餐的學生數量】LeetCode 1700【簡單】👉點我立即練習
- ? 【佇列中可以看到的人數】LeetCode 1944【困難】👉點我立即練習
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/300735.html
標籤：java