【数据结构与算法】List接口&栈&队列

雨点打透心脏的1/2处 2024-04-26 02:12 4阅读 0赞

> 🔥 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> 💖 系列专栏：[数据结构与算法][Link 2]  
> 🌠 首发时间：2022年9月17日  
> 🦋 欢迎关注🖱点赞👍收藏🌟留言🐾  
> 🌟 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  List 接口
 *  ArrayList 和 LinkedList
 *  Comparator接口
 *  线性表和合集的静态方法
 *  队列和优先队列
 *   *  将 LinkedList 作为队列使用
     *  实现栈和队列
     *  优先队列

## List 接口 ##

**List** 接口继承自 **Collection** 接口，其中定义了一个用于顺序存储元素的合集，我们可以使用它的两个具体类 **ArrayList** 或者 **LinkedList** 来创建一个线性表

<table> 
 <thead> 
  <tr> 
   <th>方法名及返回类型</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>add(index: int, element: Object) : boolean</code></td> 
   <td>在指定索引位置处增加一个新元素</td> 
  </tr> 
  <tr> 
   <td><code>addAll(index: int, c: Collection&lt;? extends E&gt;) : boolean</code></td> 
   <td>在指定索引位置处添加 <strong>c</strong> 中的所有元素</td> 
  </tr> 
  <tr> 
   <td><code>get(index: int) : E</code></td> 
   <td>返回该线性表指定索引位置处的元素</td> 
  </tr> 
  <tr> 
   <td><code>indexOf(element: Object) : int</code></td> 
   <td>返回第一个匹配元素的索引</td> 
  </tr> 
  <tr> 
   <td><code>lastIndexOf(element: Object) : int</code></td> 
   <td>返回最后一个匹配元素的索引</td> 
  </tr> 
  <tr> 
   <td><code>listIterator() : ListIterator&lt;E&gt;</code></td> 
   <td>返回针对该线性表元素的迭代器</td> 
  </tr> 
  <tr> 
   <td><code>listIterator(startIndex: int) : ListIterator&lt;E&gt;</code></td> 
   <td>返回针对从 <strong>startIndex</strong> 开始的元素的迭代器</td> 
  </tr> 
  <tr> 
   <td><code>remove(index: int) : E</code></td> 
   <td>移除指定索引位置处的元素</td> 
  </tr> 
  <tr> 
   <td><code>set(index: int, element: Object) : Object</code></td> 
   <td>设置指定索引处的元素</td> 
  </tr> 
  <tr> 
   <td><code>subList(fromIndex: int, toIndex: int) : List&lt;E&gt;</code></td> 
   <td>返回从 <strong>fromIndex</strong> 到 <strong>toIndex-1</strong> 的子线性表</td> 
  </tr> 
 </tbody> 
</table>

## ArrayList 和 LinkedList ##

数组线性表类 **ArrayList** 和链表类 **LinkedList** 是实现 **List** 接口的两个具体类

**ArrayList** 用数组存储元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中，而 **LinkedList** 则是在一个链表中存储元素

要选用这两种类中的哪一个依赖于特定需求。如果需要通过下标随机访问元素，而不会在线性表起始位置插入或删除元素，那么 **ArrayList** 提供了最高效率的合集。但是，如果应用程序需要在线性表的起始位置上插入或删除元素，就应该选择 **LinkedList** 类

**ArrayList** 的构造方法和其特有方法：

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>ArrayList()</code></td> 
   <td>使用默认的初始容量创建一个空线性表</td> 
  </tr> 
  <tr> 
   <td><code>ArrayList(c: Collection&lt;? extends E&gt;)</code></td> 
   <td>从已有的合集中创建一个线性表</td> 
  </tr> 
  <tr> 
   <td><code>ArrayList(initialCapacity: int)</code></td> 
   <td>创建一个指定初始容量的空线性表</td> 
  </tr> 
  <tr> 
   <td><code>trimToSize() : void</code></td> 
   <td>将该 <strong>ArrayList</strong> 实例的容量裁剪到该线性表当前大小</td> 
  </tr> 
 </tbody> 
</table>

**LinkedList** 的构造方法和其特有方法：

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>LinkedList()</code></td> 
   <td>创建一个默认的空线性表</td> 
  </tr> 
  <tr> 
   <td><code>LinkedList(c: Collection&lt;? extends E&gt;)</code></td> 
   <td>从已有的合集种创建一个线性表</td> 
  </tr> 
  <tr> 
   <td><code>addFirst(o: E) : void</code></td> 
   <td>添加元素到该线性表的头部</td> 
  </tr> 
  <tr> 
   <td><code>addLast(o: E) : void</code></td> 
   <td>添加元素到该线性表的尾部</td> 
  </tr> 
  <tr> 
   <td><code>getFirst() : E</code></td> 
   <td>返回该线性表的第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>getLast() : E</code></td> 
   <td>返回该线性表的最后一个元素</td> 
  </tr> 
  <tr> 
   <td><code>removeFirst() : E</code></td> 
   <td>从线性表中返回并删除第一个元素</td> 
  </tr> 
  <tr> 
   <td><code>removeLast() : E</code></td> 
   <td>从线性表返回并删除最后一个元素</td> 
  </tr> 
 </tbody> 
</table>

我们写一个程序来感受一下：

import java.util.*;
    
    public class TestArrayAndLinkedList {
        
        public static void main(String[] args) {
        
            List<Integer> arrayList = new ArrayList<>();
            arrayList.add(1);
            arrayList.add(2);
            arrayList.add(3);
            arrayList.add(4);
            arrayList.add(0, 10);
            arrayList.add(3, 30);
            System.out.println("A list of integers in the array list:");
            System.out.println(arrayList);
    
            LinkedList<Object> linkedList = new LinkedList<>(arrayList);
            linkedList.add(1, "red");
            linkedList.removeLast();
            linkedList.addFirst("green");
            System.out.println("Display the linked list backward:");
            for (int i = linkedList.size() - 1; i >= 0; --i) {
        
                System.out.print(linkedList.get(i) + " ");
            }
        }
    }

运行结果如下：

![在这里插入图片描述][0d2d81a59c75414e8e881dfc36ee9ba7.png]

## Comparator接口 ##

**Java API** 的一些类，比如 **String**、**Date**、**Calendar**、**BigInteger**、**BigDecimal** 以及所有基本类型的数字包装类都实现了 **Comparator** 接口。**Comparator** 接口中定义了 **compareTo** 方法，用于比较实现了 **Comparable** 接口的同一个类的两个元素

如果元素的类没有实现 **Comparable** 接口又将如何呢？这些元素可以比较吗？我们可以定义一个比较器（**Comparator**）来比较不同类的元素。要做到这一点，需要创建一个实现 `java.util.Comparator<T>` 接口的类并重写它的 **compare** 方法

public int compare(T element1, T element2)

如果 **element1** 小于 **element2**，就返回一个负值；如果 **element1** 大于 **element2**，就返回一个正值；如果两者相等，则返回 **0**

## 线性表和合集的静态方法 ##

**Collections** 类（不是 **Collection**接口）包含了执行合集和线性表中通用操作的静态方法

**Collections** 类包含用于线性表的 **sort**、**binarySearch**、**reverse**、**shuffle**、**copy** 和 **fill** 方法，以及用于合集的 **max**、**min**、**disjoint** 和 **frequency** 方法，如下表所示

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>sort(list: List) : void</code></td> 
   <td>对指定的线性表进行排序</td> 
  </tr> 
  <tr> 
   <td><code>sort(list: List, c: Comparator) : void</code></td> 
   <td>使用比较器对指定的线性表进行排序</td> 
  </tr> 
  <tr> 
   <td><code>binarySearch(list: List, key: Object) : int</code></td> 
   <td>采用二分查找来找到排好序的线性表中的键值</td> 
  </tr> 
  <tr> 
   <td><code>binarySearch(list: List, key: Object, c: Comparator) : int</code></td> 
   <td>使用比较器，采用二分查找来找到排好序的线性表中的键值</td> 
  </tr> 
  <tr> 
   <td><code>reverse(list: List) : void</code></td> 
   <td>对指定的线性表进行逆序排序</td> 
  </tr> 
  <tr> 
   <td><code>reverseOrder() : Comparator</code></td> 
   <td>返回一个逆序排序的比较器</td> 
  </tr> 
  <tr> 
   <td><code>shuffle(list: List) : void</code></td> 
   <td>随机打乱指定的线性表</td> 
  </tr> 
  <tr> 
   <td><code>shuffle(list: List, rmd: Random) : void</code></td> 
   <td>使用一个随机对象打乱指定的线性表</td> 
  </tr> 
  <tr> 
   <td><code>copy(des: List, src: List) : void</code></td> 
   <td>复制源线性表到目标线性表中</td> 
  </tr> 
  <tr> 
   <td><code>nCopies(n: int, o: Object) : List</code></td> 
   <td>返回一个由 n 个对象副本组成的线性表</td> 
  </tr> 
  <tr> 
   <td><code>fill(list: List, o: Object) : void</code></td> 
   <td>使用对象填充线性表</td> 
  </tr> 
  <tr> 
   <td><code>max(c: Collection) : Object</code></td> 
   <td>返回合集中的 max 对象</td> 
  </tr> 
  <tr> 
   <td><code>max(c: Collection, c: Comparator) : Object</code></td> 
   <td>使用比较器返回 max 对象</td> 
  </tr> 
  <tr> 
   <td><code>min(c: Collection) : Object</code></td> 
   <td>返回合集中的 min 对象</td> 
  </tr> 
  <tr> 
   <td><code>min(c: Collection, c: Comparator) : Object</code></td> 
   <td>使用比较器返回 min 对象</td> 
  </tr> 
  <tr> 
   <td><code>disjoint(c1: Collection, c2: Collection) : boolean</code></td> 
   <td>如果 c1 和 c2 没有共同的元素，则返回真</td> 
  </tr> 
  <tr> 
   <td><code>frequency(c: Collection, o: Object) : int</code></td> 
   <td>返回合集中指定元素的出现次数</td> 
  </tr> 
 </tbody> 
</table>

下面的代码是对线性表中的字符串进行排序：

import java.util.*;
    
    public class test {
        
        public static void main(String[] args) {
        
            List<String> list = Arrays.asList("red", "green", "blue");
            Collections.sort(list);
            System.out.println(list);
        }
    }

执行结果如下：

![在这里插入图片描述][5de249c4560143ddac8d11f447506430.png]

如果想要降序排列，我们可以简单地使用 **Collection.reverseOrder()** 方法，它会返回一个 **Comparator** 对象，该方法以逆序排列元素，下面是一段简单的降序排列的代码：

import java.util.*;
    
    public class test {
        
        public static void main(String[] args) {
        
            List<String> list = Arrays.asList("red", "green", "blue");
            Collections.sort(list, Collections.reverseOrder());
            System.out.println(list);
        }
    }

执行结果如下：

![在这里插入图片描述][c071af0cd36c454584862778c52d670a.png]

## 队列和优先队列 ##

队列（**queue**）是一种先进先出的数据结构，元素被追加到队列末尾，然后从队列头删除。在优先队列（**priority queue**）中，元素被赋予优先级。当访问元素时，拥有最高优先级的元素最先被删除

### 将 LinkedList 作为队列使用 ###

**JFC** 中并没有提供具体的队列类，而只是提供了 **Queue** 接口和 **Deque** 接口，而具体类 **LinkedList** 继承了 **Deque** 接口，而 **Deque** 接口又继承了 **Queue** 接口，事实上 **LinkedList** 可以作为队列使用

import java.util.*;
    
    public class TestQueue {
        
        public static void main(String[] args) {
        
            Queue<String> queue = new LinkedList<>();
            queue.offer("red");
            queue.offer("green");
            queue.offer("blue");
            queue.offer("cyan");
    
            while (queue.size() > 0) {
        
                System.out.print(queue.remove() + " ");
            }
        }
    }

执行结果如下：

![在这里插入图片描述][f0d287c7510b48de82e594bf6a85c5a1.png]

### 实现栈和队列 ###

需求：

*  实现栈 **GenericStack**：

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>GenericStack()</code></td> 
   <td>创建一个空的栈</td> 
  </tr> 
  <tr> 
   <td><code>getSize() : int</code></td> 
   <td>返回栈中元素的数量</td> 
  </tr> 
  <tr> 
   <td><code>peek() : E</code></td> 
   <td>返回栈顶的元素</td> 
  </tr> 
  <tr> 
   <td><code>pop() : E</code></td> 
   <td>返回并删除栈顶的元素</td> 
  </tr> 
  <tr> 
   <td><code>push(o: E) : void</code></td> 
   <td>往栈顶添加一个元素</td> 
  </tr> 
  <tr> 
   <td><code>isEmpty() : boolean</code></td> 
   <td>如果栈为空，返回 <strong>true</strong></td> 
  </tr> 
 </tbody> 
</table>

具体代码如下：

import java.util.*;
    
    public class GenericStack<E> {
        
        private final ArrayList<E> list;
    
        public GenericStack() {
        
            list = new ArrayList<>();
        }
    
        public int getSize() {
        
            return list.size();
        }
    
        public E peek() {
        
            return list.get(getSize() - 1);
        }
    
        public void push(E o) {
        
            list.add(o);
        }
    
        public E pop() {
        
            E o = list.get(getSize() - 1);
            list.remove(getSize() - 1);
            return o;
        }
    
        public boolean isEmpty() {
        
            return list.isEmpty();
        }
    }

*  实现队列 **GenericQueue**：

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>enqueue(e: E) : void</code></td> 
   <td>添加一个元素到队列中</td> 
  </tr> 
  <tr> 
   <td><code>dequeue() : E</code></td> 
   <td>从队列中移除一个元素</td> 
  </tr> 
  <tr> 
   <td><code>getSize() : int</code></td> 
   <td>返回队列中元素的数量</td> 
  </tr> 
 </tbody> 
</table>

具体代码如下：

import java.util.*;
    
    public class GenericQueue<E> {
        
        private final LinkedList<E> list;
        
        public GenericQueue() {
        
            list = new LinkedList<>();
        }
    
        public void enqueue(E e) {
        
            list.add(e);
        }
    
        public E dequeue() {
        
            return list.removeFirst();
        }
    
        public int getSize() {
        
            return list.size();
        }
    
        @Override
        public String toString() {
        
            return "GenericQueue{" +
                    "list=" + list +
                    '}';
        }
    }

### 优先队列 ###

**PriorityQueue** 类实现了一个优先队列，默认情况下，优先队列使用 **Comparable** 以元素的自然顺序进行排序，拥有最小数值的元素被赋予最高优先级，因此最先从队列中删除。如果几个元素具有相同的最高优先级，则任意选择一个，也可以使用构造方法 `PriorityQueue(initialCapacity, comparator)` 中的 **Comparator** 来指定一个顺序

<table> 
 <thead> 
  <tr> 
   <th>方法名</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>PriorityQueue()</code></td> 
   <td>创建一个初始容量为 11 的默认优先队列</td> 
  </tr> 
  <tr> 
   <td><code>PriorityQueue(initialCapacity: int)</code></td> 
   <td>创建一个初始容量为指定值的默认优先队列</td> 
  </tr> 
  <tr> 
   <td><code>PriorityQueue(c: Collection&lt;? extends E&gt;)</code></td> 
   <td>创建一个具有指定合集的优先队列</td> 
  </tr> 
  <tr> 
   <td><code>PriorityQueue(initialCapacity: int, comparator: Comparator&lt;? super E&gt;)</code></td> 
   <td>创建一个初始容量为指定值并且具有比较器的优先队列</td> 
  </tr> 
 </tbody> 
</table>

运行实例：

import java.util.*;
    
    public class PriorityQueueDemo {
        
        public static void main(String[] args) {
        
            PriorityQueue<String> q1 = new PriorityQueue<>();
            q1.offer("red");
            q1.offer("green");
            q1.offer("blue");
            q1.offer("cyan");
            System.out.println("Priority queue using Comparable:");
            while (q1.size() > 0) {
        
                System.out.print(q1.remove() + " ");
            }
            System.out.println();
    
            PriorityQueue<String> q2 = new PriorityQueue<>(4, Collections.reverseOrder());
            q2.offer("red");
            q2.offer("green");
            q2.offer("blue");
            q2.offer("cyan");
            System.out.println("Priority queue using Comparator:");
            while (q2.size() > 0) {
        
                System.out.print(q2.remove() + " ");
            }
            System.out.println();
        }
    }

运行结果如下：

![在这里插入图片描述][a0e3d4019c69452f842fa5fb96b651e9.png]

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_12010243.html?spm=1001.2014.3001.5482
[0d2d81a59c75414e8e881dfc36ee9ba7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/44e5217ee5244393bce10f08752e1473.png
[5de249c4560143ddac8d11f447506430.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e556b76cd1d54906939eef27a3e39997.png
[c071af0cd36c454584862778c52d670a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/d28651c449b144beb80f7e889feacd4c.png
[f0d287c7510b48de82e594bf6a85c5a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2dd9cfeb23fb4cd186763a5d3af2b76c.png
[a0e3d4019c69452f842fa5fb96b651e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8a52edf572a04da4a7dbd32d535548be.png