8.1 List

接口：java.util.List<>。

实现：

• java.util.ArrayList<>：变长数组
• java.util.LinkedList<>：双链表

函数：

• add()：在末尾添加一个元素
• clear()：清空
• size()：返回长度
• isEmpty()：是否为空
• get(i)：获取第i个元素
• set(i, val)：将第i个元素设置为val

8.2 栈

类：java.util.Stack<>

函数：

• push()：压入元素
• pop()：弹出栈顶元素，并返回栈顶元素
• peek()：返回栈顶元素
• size()：返回长度
• empty()：栈是否为空
• clear()：清空

8.3 队列

接口：java.util.Queue<>

实现：

• java.util.LinkedList<>：双链表
• java.util.PriorityQueue<>：优先队列
  • 默认是小根堆，大根堆写法：new PriorityQueue<>(Collections.reverseOrder())
    

函数：

• add()：在队尾添加元素
• remove()：删除并返回队头
• isEmpty()：是否为空
• size()：返回长度
• peek()：返回队头
• clear()：清空

8.4 Set

接口：java.util.Set<K>

实现：

• java.util.HashSet<K>：哈希表
• java.util.TreeSet<K>：平衡树

函数：

• add()：添加元素
• contains()：是否包含某个元素
• remove()：删除元素
• size()：返回元素数
• isEmpty()：是否为空
• clear()：清空

java.util.TreeSet多的函数：

• ceiling(key)：返回大于等于key的最小元素，不存在则返回null
• floor(key)：返回小于等于key的最大元素，不存在则返回null

8.5 Map

接口：java.util.Map<K, V>

实现：

• java.util.HashMap<K, V>：哈希表
• java.util.TreeMap<K, V>：平衡树

函数：
put(key, value)：添加关键字和其对应的值
get(key)：返回关键字对应的值
containsKey(key)：是否包含关键字
remove(key)：删除关键字
size()：返回元素数
isEmpty()：是否为空
clear()：清空
entrySet()：获取Map中的所有对象的集合
Map.Entry<K, V>：Map中的对象类型
getKey()：获取关键字
getValue()：获取值

java.util.TreeMap<K, V>多的函数：

• ceilingEntry(key)：返回大于等于key的最小元素，不存在则返回null
• floorEntry(key)：返回小于等于key的最大元素，不存在则返回null

8.6 习题

8.6.1 模拟栈

• 输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

• 输出样例：

5
5
YES
4
NO

• 题解

import java.util.Scanner;
import java.util.Stack;

/**
 * @author ljm
 * @create 2024-02-20 18:33
 */
public class Main {
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();

        Stack<Integer> stk=new Stack<>();

        while(m-->0){
            String op=sc.next();
            if(op.equals("push")){
                int x=sc.nextInt();
                stk.push(x);
            } else if (op.equals("pop")) {
                stk.pop();
            } else if (op.equals("empty")) {
                if(stk.empty()){
                    System.out.println("YES");
                }else {
                    System.out.println("NO");
                }

            } else if (op.equals("query")) {
                System.out.println(stk.peek());
            }

        }

    }
}

8.6.2 0到n-1中缺失的数字

• 题解

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty()) return 0;

        int l = 0, r = nums.size() - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] != mid) r = mid;
            else l = mid + 1;
        }

        if (nums[r] == r) r ++ ;
        return r;
    }
};