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

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

List 接口

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

ArrayList 和 LinkedList

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

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

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

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

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

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

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) + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运行结果如下：

Comparator接口

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

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

public int compare(T element1, T element2)
1

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

线性表和合集的静态方法

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

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

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

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);
    }
}
1
2
3
4
5
6
7
8
9

执行结果如下：

如果想要降序排列，我们可以简单地使用 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);
    }
}
1
2
3
4
5
6
7
8
9

执行结果如下：

队列和优先队列

队列（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() + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

执行结果如下：

实现栈和队列

需求：

• 实现栈 GenericStack：

具体代码如下：

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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

• 实现队列 GenericQueue：

具体代码如下：

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 +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

优先队列

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

运行实例：

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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

运行结果如下：