Course Module 1 no mu - Lecture: 隊列

對於大多數人來說，“隊列”這個詞在腦海中幾乎沒有什麼愉快的聯想。但今天我們談論的是不同的隊列——Java 隊列。在 Java 中，隊列是繼承Queue接口的任何東西，而 Queue 接口又擴展了Collection接口。這意味著隊列可以像集合一樣對待。

Java 中的隊列支持兩種操作原則：FIFO和LIFO。

FIFO （先進先出）原則支配著常規隊列——第一個加入隊列的元素最先離開。

LIFO （後進先出）原則描述了堆棧的行為——最後添加到隊列的元素最先離開。例如，這就是處理一副紙牌的方式：您一次從最上面的一張紙牌中取出紙牌，直到到達紙牌的底部。

Java 中的隊列層次結構如下所示：

這裡可以看到Queue有 3 個實現類：LinkedList、ArrayDeque和PriorityQueue。LinkedList和ArrayDeque直接繼承的不是Queue，而是Deque。

Deque是在 Java 6 中添加的一個接口。它包括幾個對隊列有用的方法，並允許隊列充當雙端（或雙向）隊列。這意味著它可以是FIFO和LIFO。

Deque接口的兩個後代之一是ArrayDeque。它支持雙端隊列，允許您從兩端插入和刪除元素。它也是一個自動增長大小的動態數組。

還有一個PriorityQueue類，它是Queue的直接後代：它的行為不同於實現Deque 的類。

PriorityQueue是一個優先級隊列，默認情況下根據元素的自然順序組織元素。這裡的排序使用Comparable和Comparator接口。原理與TreeSet或TreeMap相同— 使用Comparable接口並具有自己的排序順序的類。


PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

如果您運行此示例，您將在控制台中看到以下內容：

羅伯
·約翰·
安德魯

由於我們使用的是隊列而不是常規集合，因此我們需要從列表中刪除元素。為此，我們使用以下構造：


while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

Deque接口繼承了Queue方法並添加了幾個它自己有趣的方法：

void addFirst(E obj)	將obj元素添加到隊列的前面
void addLast(E obj)	將obj元素添加到隊列的末尾
E getFirst()	返回隊列中的第一個元素
E getLast()	返回隊列中的最後一個元素
boolean offerFirst(E obj)	將obj元素添加到隊列的前面，如果添加了元素則返回true 。否則，返回false。
布爾報價最後（E obj）	將obj元素添加到隊列的末尾，如果添加了元素則返回true 。否則，返回false。
E pop()	從隊列中獲取第一個元素並將其移除
void push(E obj)	將obj元素添加到隊列的前面
E peekFirst()	返回（但不移除）隊列中的第一個元素
E peekLast（）	返回（但不移除）隊列中的最後一個元素
E pollFirst()	返回並移除隊列中的第一個元素。如果沒有元素，則返回null 。
E pollLast()	返回並移除隊列中的最後一個元素。如果沒有元素，則返回null 。
E 移除最後一個()	返回並移除隊列的第一個元素。如果沒有元素則拋出異常。
E removeFirst()	返回並移除隊列的最後一個元素。如果沒有元素則拋出異常。
布爾 removeFirstOccurrence（對象 obj）	從隊列中移除第一次出現的obj
布爾 removeLastOccurrence（對象 obj）	從隊列中移除最後一次出現的obj

現在讓我們在實踐中看看其中的一些方法。

首先，讓我們向隊列中添加一個元素：


Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        System.out.println(deque);

[橙子、蘋果、菠蘿]

現在讓我們從隊列中獲取值：


	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The first element is: "+ deque.getFirst());
                          
        System.out.println("The last element is: " + deque.getLast());
                          
    }

此代碼顯示隊列的第一個和最後一個元素。

第一個元素是：Orange
最後一個元素是：Pineapple


         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);

運行這段代碼，我們得到：

橙
蘋果

[菠蘿、檸檬]

pop()和poll()之間的區別在於，如果列表為空列表，pop()將拋出NoSuchElementException ，但poll()將返回null。

現在我們將考慮pollFirst()和pollLast()方法。


Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);

橙
檸檬
[蘋果、菠蘿]

這兩種方法都返回並從隊列中刪除一個值。

下面是使用peekFirst()和peekLast()方法的示例：


Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);

第一個元素是：John
最後一個元素是：Oliver
[John, Rob, Greg, Max, Oliver]

這兩種方法都返回隊列中的第一個/最後一個元素，並且不刪除它們。如果隊列為空，則返回null 。

做得好！今天我們學習瞭如何在 Java 中使用隊列。現在您知道如何在實踐中使用它們了。

﻿隊列

隊列