Java中常見隊(duì)列舉例詳解(非線程安全)
一.隊(duì)列定義
在 Java 中，隊(duì)列（Queue） 是一種遵循 先進(jìn)先出（FIFO） 原則的數(shù)據(jù)結(jié)構(gòu)，可以通過
java.util.Queue接口及其實(shí)現(xiàn)類來使用。
二.常見接口
添加元素：
boolean add(E e): 添加元素，若隊(duì)列滿則拋出異常。boolean offer(E e): 添加元素，隊(duì)列滿時(shí)返回false。
移除元素：
E remove(): 移除并返回隊(duì)首元素，隊(duì)列空時(shí)拋出異常。E poll(): 移除并返回隊(duì)首元素，隊(duì)列空時(shí)返回null。
查看隊(duì)首元素：
E element(): 返回隊(duì)首元素但不移除，隊(duì)列空時(shí)拋出異常。E peek(): 返回隊(duì)首元素但不移除，隊(duì)列空時(shí)返回null。
三.常見實(shí)現(xiàn)類
3.1 ArrayDeque
3.1.1 實(shí)現(xiàn)原理
* 基于數(shù)組進(jìn)行實(shí)現(xiàn)
* 不允許添加null元素
* 在兩端插入和刪除元素的性能較好，時(shí)間復(fù)雜度為O(1)
* 沒有容量限制，會根據(jù)需要自動擴(kuò)容。
3.1.2 方法圖解
3.1.3 demo代碼
public class ArrayDequeDemo {
public static void main(String[] args) throws Exception{
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i = 7 ; i >=0 ; i--){
deque.addFirst(i);
}
for (int i = 8 ; i < 15 ; i++){
deque.addLast(i);
}
show(deque);
deque.addLast(15);
show(deque);
}
public static void show(ArrayDeque<Integer> deque) throws Exception{
Field elements = ArrayDeque.class.getDeclaredField("elements");
elements.setAccessible(true);
System.out.println(JSONObject.toJSONString(elements.get(deque)));
System.out.println(((Object[])( elements.get(deque))).length);
Field head = ArrayDeque.class.getDeclaredField("head");
head.setAccessible(true);
System.out.println(JSONObject.toJSONString(head.get(deque)));
Field tail = ArrayDeque.class.getDeclaredField("tail");
tail.setAccessible(true);
System.out.println(JSONObject.toJSONString(tail.get(deque)));
}
}3.2 LinkedList
3.1.1 實(shí)現(xiàn)原理
* 基于鏈表實(shí)現(xiàn)
* 允許添加null元素
* 在插入和刪除元素時(shí)性能較好，時(shí)間復(fù)雜度為O(1)
3.1.2 demo代碼
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<Integer> queue = new LinkedList<>();
for(int i = 0 ; i < 20 ; i++){
queue.add((int)(Math.random()*1000));
queue.addFirst(i);
queue.addLast(i);
}
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
System.out.println(queue.poll());
}
}
3.3 PriorityQueue
3.1.1 實(shí)現(xiàn)原理
* 基于二叉堆（通常是最小堆）實(shí)現(xiàn)
3.1.2 demo代碼
public class PriorityQueueDemo {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>(Integer::compareTo);
for(int i = 0 ; i < 20 ; i++){
queue.add((int)(Math.random()*1000));
}
while (!queue.isEmpty()){
System.out.println(queue.poll());
}
System.out.println(queue.poll());
}
}3.1.3 最小堆demo代碼
class MinHeap{
private final List<Integer> heap;
public MinHeap(){
heap = new ArrayList<>();
}
//左子節(jié)點(diǎn)
private int leftChild(int i){
return 2*i+1;
}
//右子節(jié)點(diǎn)
private int rightChild(int i){
return 2*i+2;
}
//父節(jié)點(diǎn)
private int parent(int i){
return (i-1)/2;
}
//插入節(jié)點(diǎn)
public void insert(int x){
heap.add(x);
int index = heap.size()-1;
//上浮節(jié)點(diǎn)
while(index > 0 && heap.get(index) < heap.get(parent(index))){
swap(index, parent(index));
index = parent(index);
}
}
//交換節(jié)點(diǎn)
private void swap(int i, int j) {
int temp = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, temp);
}
//刪除最小節(jié)點(diǎn)
public int deleteMin(){
if(heap.isEmpty()){
throw new RuntimeException("堆為空");
}
if (heap.size() == 1){
return heap.remove(0);
}
int min = heap.get(0);
heap.set(0,heap.remove(heap.size()-1));
minHeapify(0);
return min;
}
//更新指定節(jié)點(diǎn)的最小樹
public void minHeapify(int i){
//左子節(jié)點(diǎn)
int left = leftChild(i);
//右子節(jié)點(diǎn)
int right = rightChild(i);
//最小節(jié)點(diǎn)
int smallest = i;
//計(jì)算左節(jié)點(diǎn)
if(left < heap.size() && heap.get(left) < heap.get(smallest)){
smallest = left;
}
//計(jì)算右節(jié)點(diǎn)
if(right < heap.size() && heap.get(right) < heap.get(smallest)){
smallest = right;
}
if (smallest != i){
swap(i, smallest);
minHeapify(smallest);
}
}
}3.4 優(yōu)缺點(diǎn)
| 實(shí)現(xiàn)類 | 優(yōu)點(diǎn) | 缺點(diǎn) | 使用場景 |
|---|---|---|---|
| LinkedList | 1.支持雙端操作 2.動態(tài)擴(kuò)容，無容量限制 | 1.非線程安全 2.鏈表結(jié)構(gòu)導(dǎo)致內(nèi)存占用較高 | 1.需要雙端隊(duì)列操作（如?；蜿?duì)列） 2.單線程環(huán)境下需要快速插入/刪除 |
| ArrayDeque | 1.基于數(shù)組實(shí)現(xiàn)，內(nèi)存連續(xù)，訪問效率高 2.默認(rèn)初始容量較小，動態(tài)擴(kuò)容效率優(yōu)于 | 1.非線程安全 2.容量固定時(shí)擴(kuò)容需要復(fù)制數(shù)組 | 1.高頻次隊(duì)列操作（如廣度優(yōu)先搜索） 2.替代 |
| PriorityQueue | 1.元素按優(yōu)先級排序 2.基于堆結(jié)構(gòu)，插入/刪除時(shí)間復(fù)雜度為 | 1.非線程安全 2.遍歷順序不保證按優(yōu)先級排序 | 1.任務(wù)調(diào)度（按優(yōu)先級處理） 2.合并多個(gè)有序數(shù)據(jù)流。 |
總結(jié)
到此這篇關(guān)于Java中常見隊(duì)列的文章就介紹到這了,更多相關(guān)JAVA常見隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringCloud之Zuul網(wǎng)關(guān)原理及其配置講解
這篇文章主要介紹了SpringCloud之Zuul網(wǎng)關(guān)原理及其配置講解，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
這篇文章主要介紹了java調(diào)用process線程阻塞問題的解決，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-06-06
springcloud微服務(wù)基于redis集群的單點(diǎn)登錄實(shí)現(xiàn)解析
這篇文章主要介紹了springcloud微服務(wù)基于redis集群的單點(diǎn)登錄實(shí)現(xiàn)解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-09-09
java?Stream流常見操作方法(反射,類加載器,類加載,反射)
這篇文章主要介紹了java?Stream流常見操作方法(反射,類加載器,類加載,反射),文章圍繞主題展開詳細(xì)的內(nèi)容介紹，展開詳細(xì)的內(nèi)容介紹，具有一定參考價(jià)值，感興趣的小伙伴可以參考一下2022-06-06
Java中的SimpleDateFormat的線程安全問題詳解
這篇文章主要介紹了Java中的SimpleDateFormat的線程安全問題詳解,sonar 是一個(gè)代碼質(zhì)量管理工具,SonarQube是一個(gè)用于代碼質(zhì)量管理的開放平臺,為項(xiàng)目提供可視化報(bào)告, 連續(xù)追蹤項(xiàng)目質(zhì)量演化過程,需要的朋友可以參考下2024-01-01
這篇文章主要為大家詳細(xì)介紹了Java HttpURLConnection使用方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-11-11
Spring啟動后獲取所有擁有特定注解的Bean實(shí)例代碼
這篇文章主要介紹了Spring啟動后獲取所有擁有特定注解的Bean實(shí)例代碼，分享了相關(guān)代碼示例，小編覺得還是挺不錯(cuò)的，具有一定借鑒價(jià)值，需要的朋友可以參考下2018-02-02
這篇文章主要介紹了Java接口和抽象類的區(qū)別,對于Java的初學(xué)者來說是需要準(zhǔn)確掌握的概念！2014-07-07
JNI是Java Native Interface的縮寫，通過使用 Java本地接口書寫程序，可以確保代碼在不同的平臺上方便移植。從Java1.1開始，JNI標(biāo)準(zhǔn)成為java平臺的一部分，它允許Java代碼和其他語言寫的代碼進(jìn)行交互2021-06-06
這篇文章主要介紹了淺談Java高并發(fā)解決方案以及高負(fù)載優(yōu)化方法，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09