CPT204-Advanced OO Programming: Lists, Stacks, Queues, and Priority Queues

1.Java?集合框架層次結構Java Collection Framework hierarchy

1.1Java?集合框架描述：

1.2數據結構Data structures

1.3 Java?集合框架支持兩種類型的容器（數據結構）：

1.4 Java?集合框架的設計

2.Collection?

2.1?Collection接口

2.1.1具體方法

2.1.2迭代器?Iterators?

2.2?AbstractCollection類

3.列表List?

3.1列表接口?The List?Interface

3.1.1具體方法

3.1.2?迭代器ListIterator

3.2 ArrayList?和?LinkedList

3.2.1 java.util.ArrayList

3.2.2 java.util.LinkedList

3.2.3?ArrayList?與LinkedList?區別

3.2.4使用?ArrayList?和?LinkedList

3.3Vector及其拓展得到的Stack類

3.3.1向量類The Vector?Class

3.3.2棧類The Stack Class

4.隊列?Queues

4.1隊列接口The Queue?Interface

4.2雙端隊列接口（Deque）

4.3優先隊列?-->?java.util.PriorityQueue

4.4 LinkedList?

5.集合Set

5.1基礎概念

5.2 HashSet

5.2.1 :?創建Creation?

5.2.2?方法

5.2.2.1add()：向集合中添加元素??Adding elementsto set

5.2.2.2?增強型for循環?Enhanced for loop

5.2.2.3其它方法：

- retainAll()：保留兩個集合的交集

5.3 LinkedHashSet：

5.4 SortedSet?

?5.5 NavigableSet?

5.6TreeSet：

5.6.1創建：

5.6.2?add()方法

5.7總結

6.地圖?map

6.1基礎概念

6.2三種類型

6.3創建

6.4特征

6.5方法：

7. 列表和集合的靜態方法Static Methods for Lists and?Collections

7.1集合類中用于列表的靜態方法

8.集合和列表的表現

9.比較器接口?The Comparator Interface

10.案例研究：表達式求值 ?Case Study: Evaluating Expressions

10.1算法示例??

1.Java?集合框架層次結構Java Collection Framework hierarchy

1.1Java?集合框架描述：

- Java?提供了多種數據結構，可用于高效地組織和操作數據，通常被稱為?Java?集合框架。Java provides several data structures that can be used to organize and manipulate data efficiently, commonly known as Java Collections Framework

- Java?集合框架中定義的所有接口和類都被歸類在?`java.util`?包中。All the interfaces and classes defined in the Java Collections?Framework are grouped in the?java.util?package

1.2數據結構Data structures

-?數據結構或集合是一種以某種方式組織起來的數據的集合。

A data structure?or collection is a collection of data organized in some fashion

????????·它不僅存儲數據，還支持用于訪問和操作數據的操作。not only stores data but also supports operations for accessing and manipulating the data?

????????????????>為特定任務選擇最佳的數據結構和算法是開發高性能軟件的關鍵之一。Choosing the best data structures and algorithms for a particular task is one of the keys to developing high-performance software

-?在面向對象的思維方式中，數據結構也被稱為容器，是一種存儲其他對象（稱為元素）的對象。In object-oriented thinking, a data structure, also known as a container, is an object that stores other objects, referred to as elements

1.3 Java?集合框架支持兩種類型的容器（數據結構）：

The Java Collections Framework supports two types of containers:

-?一種用于存儲元素集合，簡單稱為集合collection：

One for storing a collection of elements, simply called a collection

??????????·列表（Lists）存儲有序的元素集合。Lists store an ordered collection of elements

??????????·集合（Sets）存儲一組無重復的元素。Sets store a group of nonduplicate elements

??????????·棧（Stacks）存儲以“后進先出”方式處理的對象。Stacks store objects that are processed in a last-in, first-out fashion

??????????·隊列（Queues）存儲以“先進先出”方式處理的對象。Queues store objects that are processed in a first-in, first-out fashion

??????????·優先隊列（PriorityQueues）存儲按優先級順序處理的對象。PriorityQueues store objects that are processed in the order of their priorities

-?另一種用于存儲鍵值對，稱為映射。One for storing key/value pairs, called a map

-?注意：在?Python?中，這被稱為字典。Note: this is called a dictionary in Python

1.4 Java?集合框架的設計

-?接口定義了框架/通用的?API。The interfaces define the framework/general API

-?抽象類提供了部分實現。The abstract classes provide partial implementation

????????·提供一個部分實現了接口的抽象類，方便用戶編寫專門容器的代碼。Providing an abstract class that partially implements an interface makes it convenient for the user to write the code for the specialized containers

????????·AbstractCollection是為了方便而提供的（因此它被稱為便利抽象類）。AbstractCollection is provided for convenience (for this reason, it is called?a convenience abstract class)

-?具體類則通過具體的數據結構來實現接口。

The concrete classes implement the interfaces with concrete data structures?

????????·Java?集合框架中的所有具體類都實現了?java.lang.Cloneable?和?java.io.Serializable?接口，除了?java.util.PriorityQueue?沒有實現?Cloneable?接口。All the concrete classes in the Java Collections Framework implement?the?java.lang.Cloneable?and java.io.Serializable interfaces except that java.util.PriorityQueue does not implement the Cloneable interface

2.Collection?

2.1?Collection接口

-?Collection?接口是用于操作對象集合的根接口。

The Collection?interface is the root interface for manipulating a collection of objects

- Collection接口中的某些方法在具體子類中無法實現（例：只讀集合無法添加或刪除元素）。

Some of the methods in the Collection interface cannot be implemented in the concrete subclass (e.g., the read-only collections cannot add or remove)?

????????·在這種情況下，該方法會拋出???java.lang.UnsupportedOperationException.?In this case, the method would throw java.lang.UnsupportedOperationException, like this:

2.1.1具體方法

2.1.2迭代器?Iterators?

-?每個集合都實現了?Iterable?接口。Each collection is Iterable

????????·迭代器是一種經典的設計模式，用于遍歷數據結構，而無需暴露數據在數據結構中的存儲細節。Iterator?is a classic design pattern for walking through a data structure without having to expose the details of how data is stored in the data structure

????????????????>它也用于增強型?`for`?循環，例如：Also used in for-each loops:

-?Collection接口擴展了Iterable接口。

The Collection interface extends the Iterable interface

????????·你可以通過?Iterable接口中的?iterator()方法獲取一個集合的迭代器對象，以遍歷集合中的所有元素。iterator()方法返回一個?Iterator?的實例。You can obtain a collection Iterator object to traverse all the elements in the collection with the iterator() method in the Iterable interface which returns an instance of Iterator

2.2?AbstractCollection類

-?AbstractCollection?類為?Collection?接口提供了部分實現（Collection?中的所有方法，除了?add、size?和?iterator方法）。The AbstractCollection class provides partial implementation for the Collection interface (all the methods in Collection except the add, size, and iterator methods)?

3.列表List?

3.1列表接口?The List?Interface

-?列表集合以順序方式存儲元素，并允許用戶指定元素的存儲位置。

A list?collection stores elements in a?sequential?order, and allows the user to specify where the element is stored

-?用戶還可以通過索引訪問元素。The user can also access the elements by index

- List?接口按順序存儲元素，并允許重復。

The?List?interface stores elements in sequence and permits duplicates

-?在?Java?集合框架中有兩個具體的類：ArrayList?和?LinkedList。

Two concrete classes in Java Collections Framework: ArrayList and LinkedList

3.1.1具體方法

- set：替換指定位置上的元素，并返回被替換的元素

3.1.2?迭代器ListIterator

- listIterator()?和?listIterator(startIndex)?方法返回一個ListIterator的實例。

The?listIterator() and listIterator(startIndex) methods return an instance of ListIterator

????????·ListIterator?接口擴展了?Iterator?接口，用于對列表進行雙向遍歷以及向列表中添加元素。The ListIterator interface extends the Iterator interface for bidirectional traversal of the list and add elements to the list

????

-?方法nextIndex()返回迭代器中下一個元素的索引，而?previousIndex()?方法返回迭代器中上一個元素的索引。The nextIndex()?method returns the index of the next element in the iterator, and the previousIndex() returns the index of the previous element in the iterator

-?方法add(element)?會在?Iterator接口的?next()?方法將要返回的元素之前，將指定的元素插入到列表中。The add(element) method inserts the specified element into the list immediately before the next element that would be returned by the next() method defined in the Iterator interface

3.2 ArrayList?和?LinkedList

- ArrayList?類和?LinkedList?類是?List?接口的具體實現。

The?ArrayList class and the LinkedList class are concrete implementations of the List interface

????????·列表的大小可以動態增長或縮小，而數組一旦創建，其大小就是固定的。

A list can grow or shrink dynamically While an array is fixed once it is created

????????·如果您的應用程序不需要插入或刪除元素，那么數組是最高效的數據結構。If your application does not require insertion or deletion of elements, the most efficient data structure is an?array?

3.2.1 java.util.ArrayList

-?通過數組實現，例如，在指定索引處插入新元素之前，需要將該索引之后的所有元素向右移動，并將?`ArrayList`?的大小增加?1。Implemented with arrays, e.g., before inserting a new element at a?specified index, shift all the elements after the index to the right and increase the ArrayList size by 1

3.2.2 java.util.LinkedList

-?鏈表中的節點?Nodes in Linked Lists

????????·鏈表由節點組成：A linked list consists of nodes:

????????????????>每個節點包含一個元素/值，并且每個節點都鏈接到它的下一個鄰居。

Each node contains an element/value, and each node is?linked?to its next neighbor:

·可以將節點定義為一個類，如下所示：A node can be defined as a class, as follows:

?????????????????????????

3.2.3?ArrayList?與LinkedList?區別

-?關鍵區別在于內部實現方式，這會影響它們的性能。The critical difference between them pertains to internal implementation, which affects their performance.

????????·如果您需要通過索引支持隨機訪問，且不需要在列表末尾以外的任何位置插入或刪除元素，那么?ArrayList?是最高效的選擇。If you need to support random access through an index?without inserting or removing?elements from any place other than the end, ArrayList offers the most efficient collection

????????·如果您的應用程序需要在列表的開頭插入或刪除元素，那么您應該選擇?LinkedList。If your application requires the insertion or deletion of elements from at the beginning of the list, you should choose LinkedList

3.2.4使用?ArrayList?和?LinkedList

-?示例演示

????????·創建了一個填充了數字的?ArrayList，并在列表的指定位置插入新元素。

????????·從?ArrayList?創建了一個LinkedList，并在列表中插入和刪除元素。

????????·正向和反向遍歷列表。????????

-?對于鏈表來說，雖然可以使用get(i)方法，但通過索引查找每個元素是一個更耗時的操作。 ?The get(i)?method is available for a?linked list, but it is a more time-consuming?operation to find each element

????????·相反，你應該使用迭代器或增強型?`for`?循環（`for-each`?循環）? Instead you should use an iterator or for-each loops:?

3.3Vector及其拓展得到的Stack類

-?早期數據格式，這些類被重新設計以融入?Java?集合框架，但為了兼容性，它們的舊式方法仍然被保留。These classes were redesigned to fit into the Java Collections Framework, but their?old-style methods are retained for compatibility?

3.3.1向量類The Vector?Class

-?向量類（Vector）與數組列表（ArrayList）類似，區別在于它包含用于訪問和修改向量的同步方法。Vector?is the same as?ArrayList, except that it contains synchronized methods for accessing and modifying the vector

????????·同步方法可以在多個線程同時訪問和修改向量時防止數據損壞。Synchronized methods can prevent data corruption when a vector is accessed and modified by two or more threads concurrently

????????????????>到目前為止討論過的類都不包含同步方法。None of the classes discussed until now are synchronized

????????·對于許多不需要同步的應用程序，使用數組列表（ArrayList）比使用向量類（Vector）更高效。For many applications that do not require synchronization, using ArrayList is more efficient than using Vector

-?從Java 2版本保留下來的方法：

????????·addElement(Object element)方法與add(Object element)方法功能相同，區別在于addElement方法是同步的。addElement(Object element) is the same as the add(Object element) method, except that the addElement method is synchronized

-?Enumeration?是早期?Java?提供的接口，用于按順序訪問集合中的元素（類似?Iterator）

3.3.2棧類The Stack Class

-?棧類（Stack）表示一個后進先出（LIFO）的對象棧。元素只能從棧頂進行訪問。The Stack class represents a last-in-first-out stack of objects. The elements are accessed only from the top of the stack

????????·你可以通過push(o:E)方法將元素壓入棧頂，通過peek()方法查看棧頂元素，通過pop()方法移除棧頂元素。You can insert with push(o:E), retrieve with peek() and remove with pop() (all from the top of the stack)

-?棧是通過擴展向量類（Vector）實現的。Stack is implemented as an extension of Vector

-?從Java 2版本保留下來的方法：

????????·empty()方法與isEmpty()方法功能相同。empty() method is the same as isEmpty()?

4.隊列?Queues

-?隊列是一種先進先出（FIFO）的數據結構：A queue?is a?first-in/first-out?data structure

????????·元素被追加到隊列的末尾，并從隊列的開頭移除。Elements are appended to the end of the queue and are removed from the beginning of the queue

????????????????>使用offer(o:E)方法將元素添加到隊列中。此方法類似于集合接口（Collection interface）中的add方法，但對于隊列，更推薦使用offer方法。The?offer(o:E)?method is used to add an element to the queue .This method is similar to the add method in the Collection interface, but the offer method is preferred for queues

????????????????>poll方法和remove方法類似，區別在于當隊列為空時，poll()會返回null，而remove()會拋出異常。The poll and remove methods are similar, except that poll() returns null if the queue is empty, whereas remove() throws an exception

????????????????>peek方法和element方法類似，區別在于當隊列為空時，peek()會返回null，而element()會拋出異常。The peek and element methods are similar, except that peek() returns null if the queue is empty, whereas element() throws an exception

-?在優先隊列中，元素會被分配優先級。在訪問元素時，優先級最高的元素會最先被移除。In a priority queue, elements are assigned priorities When accessing elements, the element with the highest priority is removed first

4.1隊列接口The Queue?Interface

-?隊列接口擴展了java.util.Collection，增加了額外的插入、提取和檢查操作。

Queue interface extends java.util.Collection with additional insertion, extraction, and inspection operations

????

4.2雙端隊列接口（Deque）

-?雙端隊列接口支持在隊列的兩端插入和移除元素。??Deque interface supports element insertion and removal at both ends

????????·Deque”是“double-ended queue”（雙端隊列）的縮寫。?The name deque is short for “double-ended queue”?

????????·雙端隊列接口擴展了隊列接口（Queue），并增加了從隊列兩端插入和移除元素的額外方法。?The Deque interface extends Queue with additional methods for inserting and removing elements from both ends of the queue

????????·雙端隊列接口中定義了以下方法：??

????????????????>addFirst(e)`：在隊列頭部插入元素 ?

????????????????>`removeFirst()`：移除隊列頭部的元素 ?

????????????????>`addLast(e)`：在隊列尾部插入元素 ?

????????????????>`removeLast()`：移除隊列尾部的元素 ?

????????????????>`getFirst()`：獲取隊列頭部的元素 ?

????????????????>`getLast()`：獲取隊列尾部的元素 ?

4.3優先隊列?-->?java.util.PriorityQueue<T>

-?默認情況下，優先隊列根據元素的自然順序（通過`Comparable`接口）對其元素進行排序。

By default, the priority queue orders its elements according to?their natural ordering using Comparable??

-?值最小的元素被分配最高的優先級，因此會首先從隊列中移除。?The element with the?least value?is assigned the highest priority and thus is removed from the queue first?

-?如果有多個元素具有相同的最高優先級，則會隨機打破平局。If there are several elements with the same highest priority, the tie is broken arbitrarily??

-?你也可以在構造函數中通過`Comparator`指定排序順序。You can also specify an ordering using Comparator in the constructor??

????????????????????????????????PriorityQueue(initialCapacity, comparator)

4.4 LinkedList?

- LinkedList?是隊列的具體實現類，它支持從列表的兩端插入和移除元素。LinkedList is the concrete class for queue and it supports inserting and removing elements from both ends of a list

????????·LinkedList?類實現了?Deque?接口，而?Deque?接口擴展了?Queue?接口。The LinkedList class implements the Deque interface, which extends the Queue interface

5.集合Set

5.1基礎概念

-?集合(Set)接口是集合(Collection)接口的子接口。Set interfaceis a sub-interface of Collection

????????·它擴展了集合(Collection)接口，但沒有引入新的方法或常量。It extends the Collection, but does not introduce new methods or constants.

????????·然而，集合(set)接口規定，集合(set)的實例不能包含重復的元素。However, the Set interface stipulates that an instance of Set contains no duplicate elements

-?可以使用它的三種具體類之一來創建一個集合：HashSet、LinkedHashSet?或?TreeSet。

can create a set using one of its three concrete classes: HashSet, LinkedHashSet, or TreeSet

????????·實現集合(set)接口的具體類必須確保無法將重復的元素添加到集合中(set)。The concrete classes that implement Set must ensure that no duplicate elements can be added to the set

????????????????>HashSet和LinkedHashSet使用：hashCode() + equals()。

????????????????>TreeSet使用：compareTo()或Comparable。

5.2 HashSet

- HashSet?類是一個實現了Set接口的具體類。The HashSet class is a concrete class that implements Set

5.2.1 :?創建Creation?

-?你可以使用它的無參構造函數來創建一個空的哈希集合。

????????????????????????????????????????Set<String> set = new HashSet<>()；

????????·第一個菱形操作符（“<>”）被稱為類型參數或泛型類型。它指定了?HashSet將要存儲的元素類型。在這個例子中，HashSet?被指定為存儲String?類型的對象。The first diamond operation ("<>") is called a type parameter or generic type.?Itspecifiesthe type of elementsthat the HashSet willstore. In this case, the HashSet?isspecified to store objects of type?String

????????·在第二個菱形操作符（“<>”）中，編譯器會根據上下文推斷泛型類型，這通常與第一個菱形操作符中指定的類型相同（僅在簡單情況下）。In the 2nd diamond operation ("<>"),the compiler infersthe generic type from the context, which istypically the same asthe type specified in the first diamond operator (Just in simple cases)

????????·括號（“()”）用于調用HashSet類的構造函數。在這個例子中，它調用了?HashSet?類的無參構造函數，該構造函數創建了一個空的集合。The parentheses("()") is used for calling the constructor of the HashSet class. In this case, it is calling the no- argument constructor of the HashSet class, which creates an empty set.

-?你可以從一個現有的集合(collection)創建一個哈希集合。You can create a hash set from an existing collection

????????????????????????List<String> list = Array.aslist(“apple”)

????????????????????????HashSet<String> hashset = new hashSet<>(list);

????????·我們有一個字符串列表?We have a List of?strings

????????·<String>，由于列表的類型?<String>, becasue of the list type

????????·<>，仍然與上面預指定的類型相同。<> ,stillsame asthe pre-specificed type above

????????·這個列表將被傳遞到括號中。?the list will be passed to the parentheses

-?你可以創建一個空的?HashSet，并指定其初始容量或初始容量加上加載因子。You can an empty HashSet with the specified initial capacity only or initial capacity plus loadFactor

????????????????????????int?initialCapacity =16;

????????????????????????float loadFactor = 0.74f;

????????????????????????HasgSet<String> hashset1 = new HashSet<>(initialCapacity);

????????????????????????HashSet<Strinf> hasgset = new HashSet<>(initialCapacity ,loadFactor );

????????·默認情況下，初始容量是16，加載因子是0.75。By default, the initial capacity is 16 and the load factor is 0.75?

????????·加載因子的范圍是從0.0到1.0，用于衡量集合在容量增加（加倍；×2）之前被允許填充的程度。Loadfactor rangesfrom 0.0 to 1.0, measuring how full the set is allowed to be before its capacity is increased (doubled; x2)

5.2.2?方法

-?接口(Collection)和抽象類(AbstractSet)將由具體類(HashSet、LinkedHashSet、TreeSet）實現或擴展。因此，所有聲明的方法（例如，add()、remove()`等）都可以在集合實例中被調用。The interfaces(e.g., Collection) and abstract classes(e.g., AbstractSet) will be implemented/extended by the concrete classes(i.e., HashSet, LinkedHashSet, TreeSet). So, all the declared methods(e.g., add(), remove(), etc) can be called in a set instance

5.2.2.1add()：向集合中添加元素??Adding elementsto set

-?哈希集合是無序的（因為使用了哈希機制）且不允許重復 A hash set is unordered (because of hashing)?and，is non-duplicated ??

-?哈希集合使用hashCode(?)的equals(?)方法來檢查重復項。（需要實現?equals(?)方法才行）

A hash set use hashcode() and equals() to check duplication?

????????·這兩個方法是“內置”的，因為它們是?Java?標準?String?類的一部分（與其他來自?Java?標準庫的對象，如Integer一樣）。These 2 methods are "built-in" in the String object, asthey are part of the standard String classin Java (Same as other objectsfrom the standard Java library like Integer)

5.2.2.2?增強型for循環?Enhanced for loop

-?集合接口擴展了可迭代接口（Iterable interface），因此集合中的元素是可迭代的。

Collection interface extends the Iterable interface , so the elements in a set are iterable

-?方法1：增強型for循環?Enhanced for loop

????????????????????????????????for (declaration : expression) {?

????????????????????????????????// Statements}?

????????·聲明：用于聲明一個變量，該變量將保存你正在迭代的數組或集合中的元素。Declaration: the part where you declare a variable that will hold an element of the array or collection you're iterating over

????????·表達式：你想要迭代的集合或數組；目標。Expression: the collection or array you want to iterate over; the target

·使用增強型for循環是因為哈希集合是無序的，沒有索引（沒有?[i]）。

Enhanced for loop is used because a hash set is unordered without index (No [i])

-?方法2：forEach()方法

????????·這是?Iterabl接口中的一個默認方法。A default method in the Iterable interface

????????????????Set.forEach(e -> System.out.print(e))`

????????????????>’e’是傳遞給?lambda?表達式的參數。它代表集合中的當前元素。e isthe parameter passed to the lambda expression. It representsthe current element of the set

? ? ? ? ? ? ? ? ? ? > ‘->’?是?lambda?箭頭，它將?lambda?表達式的參數與其主體分開。

????????????????????????-> isthe lambda arrow which separatesthe parameters of the lambda expression from its body

5.2.2.3其它方法：

- remove()：從集合中刪除一個字符串?Delete a string from set1

- size()：集合的大小the size of the set

- contains()：如果集合包含某個特定的元素，返回真/假 if the set contains a certain element, return T/F

- addAll()：將集合中的元素添加到另一個集合中，不包含重復項！會調用?hashCode()和?equals()?方法add the elements in seti and set2 together. NO DUPILICATION!?hashcode() and equals () are called

- removeAll()：從集合中移除另一個集合中的元素removing the elements in set 2 from set1

- retainAll()：保留兩個集合的交集

5.3 LinkedHashSet：

-?基礎概念

????????·LinkedHashSet繼承自?HashSet,并實現了一個鏈表,這個鏈表支持集合中元素的排序LinkedHashSet extends HashSet with a linked list implementation that supports an ordering of the elements in the set

????????·它與我們之前了解的?HashSet?非常相似（例如，集合的創建和可以調用的方法）都適用于?LinkedHashSet。Very similar to HashSet, those we have acquired previously (e.g., the set creation and the methods can be called) are applicable to LinkedHashSet

????????·顯著的區別：LinkedHashSet?中的元素可以按照它們被插入集合的順序被檢索。Significant Difference: The elements in a LinkedHashSet can be retrieved in the order in which they were inserted into the set

-?示例：

5.4 SortedSet?

-?基本概念：SortedSet是?Set?的一個子接口，它保證集合中的元素是排序的。

SortedSet is asub-interface of Set, which guarantees that the elements in the set are sorted

-?常用方法：

????????·first()：返回集合中的第一個元素。return the first element in the set

????????·last()：返回集合中的最后一個元素。return the last element in the set

????????·headSet()：查找小于或等于給定元素 find the elementsthat are lessthan or equal to the given toElement ?

????????·tailSet()：查找大于或等于給定元素 find the elementsthat are equal to or bigger than the given toElement

???????????

?5.5 NavigableSet?

-?基本概念:NavigableSet?擴展了?SortedSet，提供了導航方法（例如,lower(e),floor(e)等）

NavigableSet extends SortedSet to provide navigation methods (e.g., lower(e), floor(e),etc)

-?常用方法：

????????·lower()：返回集合中嚴格小于給定元素的最大元素。Returns?the greatest element in thissetstrictly lessthan the given element?

????????·higher()：返回集合中嚴格大于給定元素的最小元素。Returnst?he least element in thissetstrictly greater than the given element

? ? ? ? ? ? ·floor()：返回集合中小于或等于給定元素的最大元素。Returns?the greatest element in thisset lessthan or equal to the given element

??????????????·ceiling()：返回集合中大于或等于給定元素的最小元素。Returns?the least element in thisset greater than or equal to the given element

????????????????·pollFirst()：檢索并移除第一個（最小）元素。Retrieves and removesthe first (lowest) element

????????????????·pollLast()：檢索并移除最后一個（最大）元素。Retrieves and removesthe last (highest) element

5.6TreeSet：

-?基本概念：

TreeSet是一個具體類，實現了SortedSet和NavigableSet接口。TreeSet?is a concrete class that implements the SortedSet and NavigableSet interfaces

5.6.1創建：

-?無參數的空TreeSet,其元素將根據元素的自然順序升序排序.(由于實現了SortedSet接口)

Empty tree set without arguement, which will be sorted in ascending order according to the natural ordering of its elements. (Due to the implementation of SortedSet interface)?

????????????TreeSet<String> treeSet = new TreeSet<>();

-?使用其他集合創建的?TreeSet，其元素將根據自然順序排序。Tree set with other collections, being sorted by the natural ordering. ????

TreeSet<String> treeSet = new TreeSet<>(list);

-?使用自定義比較器的?TreeSet，其中我們可以定義排序順序。

Tree set with customized comparator,where we can define the orders ??

TreeSet<String> treeSet = new TreeSet<>(Comparator.reverseOrder());

-?與指定的已排序集合具有相同元素和相同排序的TreeSet。

Tree set with the same elements and the same ordering asthe specified sorted set

???//?如果我們已經有一個根據特定規則排序的集合?

???SortedSet<String> originalSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);

???//?我們可以通過這種方式創建另一個具有相同元素和相同排序的TreeSet

???????TreeSet<String> copiedSet = new TreeSet<>(originalSet);

5.6.2?add()方法

-?類似于哈希集合，重復的元素不會被添加到樹集合中。Similar to a hash set, the duplicted elements would not be added to the tree set

-?這不是因為hashCode()和?equals()方法，而是由于?Java?標準庫中?String和?Integer以及其他包裝類中“內置”的compareTo()?方法。Instead of hashcode() and equals(), thisis because the “built-in” compareTo() in String and Integer and other wrapper classesin Java'sstandard library.

-?區別在于底層數據結構，哈希集合?->?哈希，樹集合?->?樹The difference is due to the bottomed data structure, hash set -> Hashing , tree set -> Tree

5.7總結

- HashSet、LinkedHashSet?和?TreeSet?都是?Java?中?Set接口的實現，這意味著它們都具有不允許重復元素的基本特性。HashSet, LinkedHashSet, and TreeSet are all implementations of the Set interface in Java, which meansthey all share the fundamental characteristic of not allowing duplicate elements.

- HashSet：

????????·排序：它不保證任何迭代順序。Ordering: It does not guarantee any order of iteration

????????·內部結構：由哈希表支持。Internal Structure: Backed by a hash table

- LinkedHashSet：

????????·排序：維護一個貫穿其所有條目的雙向鏈表，這定義了迭代順序，通常是元素被插入到集合中的順序（插入順序）。Ordering: Maintains a doubly-linked list running through all its entries, which definesthe iteration ordering, which is normally the order in which elements were inserted into the set (insertion-order).?

????????·內部結構：由帶有貫穿它的鏈表的哈希表支持 Internal Structure: Backed by a hash table with a linked list running through it

- TreeSet：

????????·排序：保證元素將根據元素的自然順序或在集合創建時提供的比較器按升序排序。Ordering: Guaranteesthat elements will be sorted in ascending element order, according to the natural ordering of the elements, or by a Comparator provided atset creation time

????????·內部結構：由樹支持。Internal Structure: Backed by a tree

6.地圖?map

6.1基礎概念

-?地圖（Map）是一個容器對象，用于存儲鍵/值對的集合。A map is a container object thatstores a collection of key/value pairs.

-?它可以通過鍵來快速檢索、刪除和更新這對鍵/值。映射存儲值的同時也會存儲鍵。It enablesfast retrieval, deletion, and updating of the pair through the key. A map?storesthe values along with the keys.

-?在列表（List）中，索引是整數。在地圖（Map）中，鍵可以是任何對象。In List, the indexes are integers. In Map, the keys can be any objects.

????????·地圖不能包含重復的鍵。A map cannot contain duplicate keys.

? ? ? ? ?·每個鍵映射到一個值。Each key maps?to one value.

6.2三種類型

-?有三種類型的字典：HashMap、LinkedHashMap?和?TreeMap。

????????·它們仍然確保映射實例通過?hashCode()?和?equals()（對于?HashMap?和?LinkedHashMap）以及?compareTo()/Comparator（對于?TreeMap）來保證鍵的唯一性。

Still, they ensure the map instances non- duplicated using hashcode() and equals() (for HashMap and LinkedHashMap) as well asthe compareTo()/Comparator (for TreeMap).

????????● HashMap、LinkedHashMap?和?TreeMap?類是?Map?接口的三種具體實現，其中?TreeMap?還額外實現了?SortedMap?和NavigableMap接口。The HashMap, LinkedHashMap, and TreeMap classes are three concrete implementations of the Map interface, with TreeMap additionally implements SortedMap and NavigableMap

6.3創建

-?我們可以使用帶參數（m：Map<? extends K,? extends V>）的方式來創建新的哈希映射（HashMap）、鏈接哈希映射（LinkedHashMap）或樹映射（TreeMap）。We can create new hash/linked hash/tree maps with arguement (m: Map<? extends K,? extends V>)

-?這表明構造函數接受一個?Map<X, Y>?類型的參數，其中?X?是?K?的子類型，Y?是?V?的子類型。

It indicatesthat the constructor accepts a Map <X, Y> (i.e.,smallMap) where X is a subclass of K, and Y is a subclass of V (See figure).?

-?當?X?完全等于?K，Y?完全等于?V?時，這種方法同樣適用。

It would also work when X is exactly K, and Y is exactly V

·Map<Integer, String> smallMap = new HashMap<>();

·Map<Integer, String> largerMap = new HashMap<>(smallMap);

-?通常，類似于?LinkedHashSet，LinkedHashMap?通過鏈表實現擴展了?HashMap，支持按插入順序檢索元素。Usually, and similar to LinkedHashSet, LinkedHashMap extends HashMap with a linked-list implementation thatsupportsretreiving elementsin the insertion order.

-?在?LinkedHashMap中，有一個構造函數參數（initialCapacity：int，loadFactor：float，accessOrder：boolean）。In LinkedHashMap, there is a constructor arguement (initialCapacity: int, loadFactor: float, accessOrder: boolean)?

-?一旦設置為LinkedHashMap(initialCapacity, loadFactor, true)，創建的?LinkedHashMap將允許我們按照元素最后被訪問的順序來檢索它們，從最近最少訪問到最近最多訪問的順序（訪問順序）。Once it isset to be LinkedHashMap(initialCapacity, loadFactor, true), the created LinkedHashMap would allow usto retreive elements in the order in which they?were last accessed, from least recently to most recently accessed (access order)

6.4特征

-?哈希映射是無序的，類似于哈希集合。A hash map is unordered, similar to a hash set

-?樹映射按涉及元素的鍵排序（在這種情況下是按字母順序）。

A tree map is ordered by the keys of the involved elements (alphabetically in this case)

-?鏈接哈希映射可以按插入順序排序，也可以按訪問順序排序（`accessOrder: true`）。

A linked hash map can be ordered by the insertion order, and by the access order (accessOrder: True)

6.5方法：

- get()：返回指定鍵映射的值。Returns the value to which the specified key is mapped

- forEach()：對映射中的每個條目執行給定操作，直到所有條目都已處理完畢或操作拋出異常。Performs the given action for each entry in this map until all entries have been processed or the action throws an exception

???????void forEach(BiConsumer<? super K, ? super V> action)

????????·不返回任何內容（void），只執行操作。return nothing (void), just perform the action

????????·K是映射的鍵，V?是映射的值。K is the map’s key, V is the map’s value

????????·基本上，forEach((key, value) -> action)。Basically, forEach( (key,value) -> action )

7. 列表和集合的靜態方法Static Methods for Lists and?Collections

- ?java.util.Collections類包含用于在集合或列表中執行常見操作的靜態方法。The java.util.Collections?class contains static methods to perform common operations in a collection or a list

????????·用于集合的方法包括：max、min、disjoint?和?frequency。

????????·用于列表的方法包括：sort、binarySearch、reverse、shuffle、copy?和?fill。

- Collections?類的?UML?圖?

- Collections類其他有用的靜態方法：

????????·rotate(List list, int distance)：將列表中的所有元素按指定距離旋轉。

????????·replaceAll(List list, Object oldVal, Object newVal)：將列表中所有指定值的出現替換為另一個值。

????????·indexOfSubList(List source, List target)：返回源列表中第一個與目標列表相等的子列表的索引。

????????·lastIndexOfSubList(List source, List target)：返回源列表中最后一個與目標列表相等的子列表的索引。

????????·swap(List list, int i, int j)：在指定列表中交換指定位置的元素。

????????·addAll(Collection<? super T> c, T... )：將指定數組中的所有元素添加到指定集合中。

7.1集合類中用于列表的靜態方法

-?排序：Sorting

????????·增序排序? ?

????????????????>輸出結果是：`[blue, green, red]`

????????·降序排序，使用?Collections.reverseOrder()

????????????????>輸出結果是：`[red, green, blue]`

????????·聲明

????????????????>static <T extends Comparable<? super T>> void sort(List<T> list)

??使用?Comparable?接口中的?compareTo方法對列表進行排序。uses the compareTo method in the Comparable interface

????????????????>static <T> void sort(List<T> list, Comparator<? super T> c)

??使用?Comparator?接口中的?compare方法對列表進行排序。uses the compare method in the Comparator interface

-?二分查找Binary search:

????????·你可以使用?binarySearch?方法在已排序的列表中查找一個鍵值。You can use the binarySearch?method to search for a key in a sorted list

????????·要使用此方法，列表必須按升序排列。To use this method, the list must be sorted in increasing order

????????·如果鍵值不在列表中，該方法會返回?-(鍵值應插入的點?+ 1)。If the key is not in the list, the method returns -(insertion point + 1)?

-?反轉列表Reverse

????????·代碼輸出：[blue, green, red, yellow]

-?隨機打亂Shuffle

??????????·你也可以使用?`shuffle(List, Random)`?方法，通過指定的?`Random`?對象隨機重新排列列表中的元素。You can also use the shuffle(List, Random) method to randomly reorder the elements in a list with a specified Random object.

????????·使用指定的?Random?對象隨機打亂列表，便于實現可重復的隨機打亂或在多線程環境中使用。

-?拷貝：copy(dest, src)：

????????·將一個源列表中的所有元素復制到目標列表的相同索引位置 copy(dest, src): copy all the elements from a source list to a destination list on the same inde

????????????????>list1的輸出結果是：[white, black, green, blue]

????????·copy方法執行的是淺拷貝：僅復制源列表中元素的引用，而不是元素本身的副本。如果源列表和目標列表中的元素是可變對象，那么修改這些對象的內容會影響兩個列表中對應的元素。

The copy method performs a shallow copy: only the references of the elements from the source list are copied?

? ? ? ? ·如果目標列表比源列表小，那么我們會遇到一個運行時錯誤。If the destination list is smaller than the source list then we get a runtime error:?

-?asList方法

????????·用于從可變長度的參數列表中創建一個列表。creating a list from a variable-length list of arguments

???????????>返回的是一個由?Arrays?類內部定義的內部類對象的?List?引用：`java.util.Arrays$ArrayList`。它也被稱為?`ArrayList`，但實際上只是一個數組的包裝器。

returns a List reference of inner class object defined within Arrays : java.util.Arrays$ArrayList, which is also called ArrayList but it is just a wrapper for an array?

-?nCopies(int n, Object o)?方法

????????·創建一個不可變的列表，該列表由指定對象的?n個副本組成。create an immutable list that consists of n copies of the specified object

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

????????????????>list1`?是一個包含三個?`Calendar`?對象的列表。

????????????????>通過?`nCopies`?方法創建的列表是不可變的，因此你無法在列表中添加或刪除元素——所有元素都指向同一個引用！The list created from the nCopies method is immutable, so you cannot add/remove elements in the list ---All the elements have the same reference!

????????????????>`list1`?是?`Collections`?類的一個內部類的實例：`java.util.Collections$CopiesList`。

list1 is an instance of an inner class of Collections: class java.util.Collections$CopiesList

-?fill(List list, Object o)方法

????????·將列表中的所有元素替換為指定的元素。replaces all the elements in the list with the specified element

????????????????>輸出：`[black, black, black]`

??- max和min方法

????????·用于在集合中查找最大和最小的元素。find the maximum and minimum elements in a collection

-?disjoint(collection1, collection2)方法

????????·用于判斷兩個集合是否沒有任何共同的元素。如果沒有共同元素，則返回?`true`。

returns true if the two collections have no elements in common

-?frequency(collection, element)?方法

????????·用于查找指定元素在集合中的出現次數。finds the number of occurrences of the element in the collection

????????·過程中使用的是?.equal?方法

8.集合和列表的表現

-?集合(set)比列表更適合存儲無重復元素。Sets are more efficient than lists for storing nonduplicate elements

-?列表通過索引訪問元素很有用。Lists are useful for accessing elements through the index

-?集合不支持索引，因為集合中的元素是無序的。Sets do not support indexing because the elements in a set are unordered

-?要遍歷集合中的所有元素，可以使用增強型for循環或迭代器。To traverse all elements in a set, use a for-each loop or iterator

9.比較器接口?The Comparator Interface

-?有時，你可能需要比較那些不是?Comparable?類型的實例，或者按照與?Comparable?不同的標準進行比較。Sometimes you want to compare the elements that are not instances of Comparable or by a different criteria than Comparable

-?你可以定義一個比較器（Comparator）來比較這些元素。You can define a Comparator to compare these elements

????????·定義一個實現了?java.util.Comparator<T>?接口的類。Define a class that implements the java.util.Comparator<T> interface

????????·Comparator接口包含兩個方法：compare?和?equals。The Comparator interface has two methods: compare and equals

????????????????????????????????public int compare(T element1, T element2)

????????????????>如果?`element1`?小于?`element2`，返回負值；????????????????

????????????????>如果?`element1`?大于?`element2`，返回正值；

????????????????>如果兩者相等，返回零。

-?例子：