Blog of AgioPan
0%

数据结构与算法自学笔记（3）- 队列和栈相关

Posted on Edited on In ,

引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了栈和队列的基础实现、相互转换以及最小栈等核心内容，涵盖了链表实现、数组实现、循环队列等多种实现方式,包括了class013 -> class016的内容。

013【入门】队列和栈-链表、数组实现

队列的基本概念

队列（Queue）是一种先进先出（FIFO, First In First Out）的线性数据结构。元素从队尾（rear）插入，从队首（front）删除。

队列的基本操作

  • enqueue/offer: 入队，将元素添加到队尾
  • dequeue/poll: 出队，从队首移除元素
  • front/peek: 查看队首元素，但不移除
  • isEmpty: 判断队列是否为空
  • size: 获取队列中元素个数

队列的实现方式

方式一：基于双端队列（deque）实现

Python内置的collections.deque提供了高效的双端操作，但常数时间较慢。

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
from collections import deque

class Queue1:
    """
    基于Python内置deque实现的队列
    内部使用双向链表，常数操作较慢但使用简单
    """
    def __init__(self):
        self.queue = deque()  # 内部存储使用deque（双端队列）

    def is_empty(self):
        """判断队列是否为空"""
        return not self.queue

    def offer(self, num):
        """向队列中加入元素，加到队尾"""
        self.queue.append(num)

    def poll(self):
        """从队列头部弹出元素"""
        return self.queue.popleft()

    def peek(self):
        """返回队列头的元素但不弹出"""
        return self.queue[0]

    def size(self):
        """返回队列中元素个数"""
        return len(self.queue)

方式二：基于固定数组实现

在已知操作次数上限的情况下，使用固定数组实现具有更好的常数时间性能。

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
32
33
34
35
36
37
38
39
40
41
class Queue2:
    """
    基于固定数组实现的队列
    适用于已知加入操作总次数上限的场景
    常数时间性能更好，是实际刷题中最常用的方式
    """
    def __init__(self, n):
        """
        初始化队列
        参数: n - 加入操作的总次数上限
        """
        self.queue = [0] * n  # 固定大小数组
        self.l = 0  # 队首指针
        self.r = 0  # 队尾指针

    def is_empty(self):
        """判断队列是否为空"""
        return self.l == self.r

    def offer(self, num):
        """入队操作"""
        self.queue[self.r] = num  # 在队尾位置插入元素
        self.r += 1  # 队尾指针后移

    def poll(self):
        """出队操作"""
        num = self.queue[self.l]  # 取队首元素
        self.l += 1  # 队首指针后移
        return num

    def head(self):
        """返回队首元素"""
        return self.queue[self.l]

    def tail(self):
        """返回队尾元素"""
        return self.queue[self.r - 1]

    def size(self):
        """队列当前元素个数，区间[l, r)"""
        return self.r - self.l

栈的基本概念

栈（Stack）是一种后进先出（LIFO, Last In First Out）的线性数据结构。元素只能从栈顶插入和删除。

栈的基本操作

  • push: 压栈，将元素添加到栈顶
  • pop: 弹栈，从栈顶移除元素
  • peek/top: 查看栈顶元素，但不移除
  • isEmpty: 判断栈是否为空
  • size: 获取栈中元素个数

栈的实现方式

方式一：基于动态数组实现

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
class Stack1:
    """
    基于Python内置列表实现的栈
    使用动态数组，常数时间不是最优但使用简单
    """
    def __init__(self):
        self.stack = []  # 用列表模拟栈

    def is_empty(self):
        """判断栈是否为空"""
        return len(self.stack) == 0

    def push(self, num):
        """压栈操作"""
        self.stack.append(num)

    def pop(self):
        """弹栈操作"""
        return self.stack.pop()

    def peek(self):
        """返回栈顶元素但不弹出"""
        return self.stack[-1]

    def size(self):
        """返回栈的大小"""
        return len(self.stack)

方式二：基于固定数组实现

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
32
33
34
35
class Stack2:
    """
    基于固定数组实现的栈
    适用于已知同时在栈里元素个数上限的场景
    常数时间性能更好，空间可以复用
    """
    def __init__(self, n):
        """
        初始化栈
        参数: n - 同时在栈里的元素个数上限
        """
        self.stack = [0] * n  # 固定大小数组
        self.size_ = 0  # 当前栈元素个数

    def is_empty(self):
        """判断栈是否为空"""
        return self.size_ == 0

    def push(self, num):
        """压栈操作"""
        self.stack[self.size_] = num  # 在当前size位置插入
        self.size_ += 1  # 元素个数+1

    def pop(self):
        """弹栈操作"""
        self.size_ -= 1  # 元素个数-1，先减后取值
        return self.stack[self.size_]  # 返回弹出的元素

    def peek(self):
        """返回栈顶元素但不弹出"""
        return self.stack[self.size_ - 1]

    def size(self):
        """返回栈大小"""
        return self.size_

循环队列

循环队列是队列的一种特殊实现，通过循环使用固定大小的数组来避免空间浪费。

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class MyCircularQueue:
    """
    循环队列实现
    测试链接: https://leetcode.cn/problems/design-circular-queue/
    """
    def __init__(self, k):
        """
        初始化循环队列
        参数: k - 队列容量上限
        """
        self.queue = [0] * k  # 固定大小数组
        self.l = 0  # 队首指针
        self.r = 0  # 队尾指针
        self.size = 0  # 当前元素个数
        self.limit = k  # 容量上限

    def enQueue(self, value):
        """
        入队操作
        返回: 成功返回True，队列满返回False
        """
        if self.isFull():
            return False  # 队列已满
        else:
            self.queue[self.r] = value  # 队尾插入元素
            # 队尾指针循环移动
            self.r = 0 if self.r == self.limit - 1 else self.r + 1
            self.size += 1  # 元素个数+1
            return True

    def deQueue(self):
        """
        出队操作
        返回: 成功返回True，队列空返回False
        """
        if self.isEmpty():
            return False  # 队列为空
        else:
            # 队首指针循环移动
            self.l = 0 if self.l == self.limit - 1 else self.l + 1
            self.size -= 1  # 元素个数-1
            return True

    def Front(self):
        """返回队首元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.l]

    def Rear(self):
        """返回队尾元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            # 计算队尾指针的实际位置
            last = self.limit - 1 if self.r == 0 else self.r - 1
            return self.queue[last]

    def isEmpty(self):
        """判断队列是否为空"""
        return self.size == 0

    def isFull(self):
        """判断队列是否已满"""
        return self.size == self.limit

014【入门】队列和栈入门题目-栈和队列相互实现

用栈实现队列

队列是先进先出（FIFO），而栈是后进先出（LIFO）。要用栈实现队列，需要使用两个栈来模拟队列的行为。

算法思想

使用两个栈：

  • 输入栈（in_stack）：负责接收新元素的push操作
  • 输出栈（out_stack）：负责输出元素的pop和peek操作

关键规则

  1. 倒数据条件：只有当输出栈为空时，才能从输入栈倒数据
  2. 倒数据原则：如果要倒数据，必须将输入栈的数据全部倒完
  3. 时间复杂度：虽然单次操作可能是O(n)，但均摊时间复杂度是O(1)
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
32
33
34
35
36
37
38
39
class MyQueue:
    """
    用栈实现队列
    测试链接: https://leetcode.cn/problems/implement-queue-using-stacks/
    时间复杂度: 均摊O(1)
    """
    def __init__(self):
        self.in_stack = []     # 输入栈，负责push
        self.out_stack = []    # 输出栈，负责pop/peek

    def inToOut(self):
        """
        倒数据操作：从输入栈将数据倒入输出栈
        核心规则：
        1) 输出栈空了，才能倒数据
        2) 如果倒数据，输入栈必须倒完
        """
        if not self.out_stack:                     # 只有输出栈为空才能倒
            while self.in_stack:                   # 输入栈必须倒完
                self.out_stack.append(self.in_stack.pop())

    def push(self, x: int):
        """入队操作：新元素加入输入栈"""
        self.in_stack.append(x)                    # 新元素压入输入栈
        self.inToOut()                             # 检查是否需要倒数据

    def pop(self) -> int:
        """出队操作：从输出栈弹出元素"""
        self.inToOut()                             # 确保输出栈有数据
        return self.out_stack.pop()                # 弹出队首元素

    def peek(self) -> int:
        """查看队首元素：不移除，只查看"""
        self.inToOut()                             # 确保输出栈有数据
        return self.out_stack[-1]                  # 返回栈顶即队首

    def empty(self) -> bool:
        """判断队列是否为空"""
        return not self.in_stack and not self.out_stack  # 两个栈都空才是空队列

时间复杂度分析

虽然inToOut()操作在最坏情况下需要O(n)时间，但通过均摊分析：

  • 每个元素最多被移动两次（输入栈→输出栈→出队列）
  • n次操作的总时间复杂度为O(n)
  • 均摊时间复杂度为O(1)

用队列实现栈

栈是后进先出（LIFO），队列是先进先出（FIFO）。要用队列实现栈，需要在每次push操作后重新排列队列中的元素。

算法思想

使用一个双端队列（deque），在每次push新元素后，将队列中原有的元素依次移动到新元素后面，确保新元素总是在队首位置。

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
32
33
34
from collections import deque

class MyStack:
    """
    用双端队列实现栈
    测试链接: https://leetcode.cn/problems/implement-stack-using-queues/
    """
    def __init__(self):
        self.queue = deque()                       # 用deque实现队列

    def push(self, x: int):
        """
        压栈操作
        时间复杂度: O(n)
        核心思想: 新元素入队后，将前面所有元素重新排列到新元素后面
        """
        n = len(self.queue)                        # 记录当前队列长度
        self.queue.append(x)                       # 新元素加入队尾
        
        # 将前面的n个元素依次移动到队尾
        for _ in range(n):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        """弹栈操作：弹出队首元素，即栈顶元素"""
        return self.queue.popleft()

    def top(self) -> int:
        """查看栈顶元素：返回队首元素"""
        return self.queue[0]

    def empty(self) -> bool:
        """判断栈是否为空"""
        return not self.queue

操作示例

假设依次push元素1, 2, 3：

1
2
3
4
5
6
7
初始状态: []

push(1): [1]

push(2): [2] -> [2,1] (将1移动到2后面)

push(3): [3,2,1] -> [3,2,1] (将2,1依次移动到3后面)

最终队列状态为[3,2,1]，队首元素3就是栈顶元素，符合LIFO特性。

015【入门】栈的入门题目-最小栈

最小栈问题

最小栈要求实现一个栈，除了基本的栈操作外，还要能够在O(1)时间内获取栈中的最小元素。

问题分析

核心挑战是如何在保持基本栈操作O(1)时间复杂度的同时，追踪当前栈中的最小值。当栈顶元素（恰好是最小值）被弹出时，需要快速知道剩余元素中的最小值。

解决方案：辅助栈法

使用两个栈：

  • 数据栈（data）：存储实际数据
  • 最小值栈（min）：存储对应位置的最小值

实现方法一：基于列表

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
32
33
34
class MinStack1:
    """
    最小栈实现方法一：使用Python列表
    测试链接: https://leetcode.cn/problems/min-stack/
    时间复杂度: 所有操作均为O(1)
    """
    def __init__(self):
        self.data = []  # 数据栈，存储实际元素
        self.min = []   # 最小值栈，存储对应位置的最小值

    def push(self, val):
        """
        压栈操作
        核心思想: 每次压栈时，同时在最小值栈中记录当前的最小值
        """
        self.data.append(val)  # 将val压入数据栈
        
        if not self.min or val <= self.min[-1]:  # 如果最小栈为空或val是新的最小值
            self.min.append(val)  # 将val压入最小栈
        else:  # 否则val不是最小值
            self.min.append(self.min[-1])  # 将当前最小值再次压入最小栈

    def pop(self):
        """弹栈操作：同时弹出两个栈的栈顶元素"""
        self.data.pop()  # 弹出数据栈栈顶
        self.min.pop()   # 弹出最小栈栈顶

    def top(self):
        """获取栈顶元素"""
        return self.data[-1]  # 返回数据栈栈顶元素

    def getMin(self):
        """获取栈中最小元素"""
        return self.min[-1]   # 返回最小栈栈顶元素

工作原理示例

假设依次压入元素：5, 2, 7, 1, 3

操作 数据栈 最小栈 说明
push(5) [5] [5] 5是第一个元素，也是最小值
push(2) [5,2] [5,2] 2比5小，成为新的最小值
push(7) [5,2,7] [5,2,2] 7比2大，最小值仍是2
push(1) [5,2,7,1] [5,2,2,1] 1比2小，成为新的最小值
push(3) [5,2,7,1,3] [5,2,2,1,1] 3比1大，最小值仍是1

实现方法二：基于固定数组

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
32
33
34
35
36
class MinStack2:
    """
    最小栈实现方法二：使用固定大小数组
    适用于已知最大容量的场景，常数时间性能更好
    """
    def __init__(self):
        # 根据leetcode测试数据实验得出的容量上限
        # 如果测试数据增加导致溢出，需要调大此值
        self.MAXN = 8001

        self.data = [0] * self.MAXN  # 数据数组
        self.min = [0] * self.MAXN   # 最小值数组
        self.size = 0  # 当前栈大小

    def push(self, val):
        """压栈操作"""
        self.data[self.size] = val  # 在size位置存储val
        
        if self.size == 0 or val <= self.min[self.size - 1]:  # 第一个元素或新的最小值
            self.min[self.size] = val  # 存储val作为最小值
        else:  # val不是最小值
            self.min[self.size] = self.min[self.size - 1]  # 复制前一个最小值
        
        self.size += 1  # 栈大小加1

    def pop(self):
        """弹栈操作：只需将size减1，不需要实际删除数据"""
        self.size -= 1

    def top(self):
        """获取栈顶元素"""
        return self.data[self.size - 1]

    def getMin(self):
        """获取栈中最小元素"""
        return self.min[self.size - 1]

复杂度分析

时间复杂度

  • push操作：O(1) - 只需要常数次比较和赋值
  • pop操作：O(1) - 只需要移动指针或减少计数
  • top操作：O(1) - 直接访问数组元素
  • getMin操作：O(1) - 直接访问最小值栈顶

空间复杂度

  • 总空间复杂度：O(n) - 需要两个栈存储数据
  • 额外空间：O(n) - 最小值栈的空间开销

优化思考

虽然辅助栈法简单易懂，但存在空间冗余。可以考虑以下优化：

  1. 稀疏存储：最小值栈只在最小值更新时才压入新值
  2. 差值存储：存储与最小值的差值而非绝对值
  3. 链表实现：在节点中直接存储当前最小值

数据结构选择指南

性能对比

实现方式 时间复杂度 空间复杂度 常数因子 适用场景
Python内置容器 O(1)均摊 O(n) 较大 快速原型，不追求极致性能
固定数组 O(1) O(n) 较小 已知容量上限，追求性能
双栈/双队列 O(1)均摊 O(n) 中等 功能转换，教学示例

016【入门】双端队列-双链表和固定数组实现

双端队列的基本概念

双端队列（Deque，Double-ended Queue）是一种特殊的线性数据结构，允许在队列的两端进行插入和删除操作。与普通队列只能在一端插入、另一端删除不同，双端队列提供了更大的灵活性。

双端队列的基本操作

  • insertFront: 在队首插入元素
  • insertLast: 在队尾插入元素
  • deleteFront: 删除队首元素
  • deleteLast: 删除队尾元素
  • getFront: 获取队首元素
  • getRear: 获取队尾元素
  • isEmpty: 判断队列是否为空
  • isFull: 判断队列是否已满

循环双端队列的实现

循环双端队列是双端队列的一种特殊实现，使用固定大小的数组并通过循环索引来管理队列的边界。

实现方式一：基于Python列表

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class MyCircularDeque1:
    """
    基于Python列表实现的循环双端队列
    内部使用动态数组，操作简单但常数时间较慢
    测试链接: https://leetcode.cn/problems/design-circular-deque/
    """
    def __init__(self, k):
        """
        初始化循环双端队列
        参数: k - 队列容量上限
        """
        self.deque = []  # 用列表模拟双端队列
        self.size = 0    # 当前队列大小
        self.limit = k   # 队列容量

    def insertFront(self, value):
        """
        在队首插入元素
        时间复杂度: O(n) - 需要移动所有现有元素
        """
        if self.isFull():
            return False
        else:
            self.deque.insert(0, value)  # 在索引0位置插入，其他元素后移
            self.size += 1
            return True

    def insertLast(self, value):
        """
        在队尾插入元素
        时间复杂度: O(1)均摊
        """
        if self.isFull():
            return False
        else:
            self.deque.append(value)  # 直接添加到列表末尾
            self.size += 1
            return True

    def deleteFront(self):
        """
        删除队首元素
        时间复杂度: O(n) - 需要移动所有剩余元素
        """
        if self.isEmpty():
            return False
        else:
            self.size -= 1
            self.deque.pop(0)  # 删除索引0的元素，其他元素前移
            return True

    def deleteLast(self):
        """
        删除队尾元素
        时间复杂度: O(1)
        """
        if self.isEmpty():
            return False
        else:
            self.size -= 1
            self.deque.pop()  # 删除列表末尾元素
            return True

    def getFront(self):
        """获取队首元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            return self.deque[0]

    def getRear(self):
        """获取队尾元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            return self.deque[-1]

    def isEmpty(self):
        """判断队列是否为空"""
        return self.size == 0

    def isFull(self):
        """判断队列是否已满"""
        return self.size == self.limit

实现方式二：基于固定数组

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class MyCircularDeque2:
    """
    基于固定数组实现的循环双端队列
    使用循环索引管理队列边界，常数时间性能更好
    适用于已知容量上限的场景
    """
    def __init__(self, k):
        """
        初始化循环双端队列
        参数: k - 队列容量上限
        """
        self.deque = [0] * k  # 固定长度数组
        self.l = 0            # 队首指针
        self.r = 0            # 队尾指针
        self.size = 0         # 当前队列大小
        self.limit = k        # 队列容量

    def insertFront(self, value):
        """
        在队首插入元素
        时间复杂度: O(1)
        """
        if self.isFull():
            return False
        else:
            if self.isEmpty():
                # 空队列情况，队首和队尾指针都指向同一位置
                self.l = self.r = 0
                self.deque[0] = value
            else:
                # 队首指针向前移动（循环）
                self.l = self.l - 1 if self.l != 0 else self.limit - 1
                self.deque[self.l] = value
            self.size += 1
            return True

    def insertLast(self, value):
        """
        在队尾插入元素
        时间复杂度: O(1)
        """
        if self.isFull():
            return False
        else:
            if self.isEmpty():
                # 空队列情况
                self.l = self.r = 0
                self.deque[0] = value
            else:
                # 队尾指针向后移动（循环）
                self.r = 0 if self.r == self.limit - 1 else self.r + 1
                self.deque[self.r] = value
            self.size += 1
            return True

    def deleteFront(self):
        """
        删除队首元素
        时间复杂度: O(1)
        """
        if self.isEmpty():
            return False
        else:
            if self.size == 1:
                # 删除后队列变空，可选择重置指针
                pass  # 这里不重置l和r，因为逻辑上没有影响
            # 队首指针向后移动（循环）
            self.l = 0 if self.l == self.limit - 1 else self.l + 1
            self.size -= 1
            return True

    def deleteLast(self):
        """
        删除队尾元素
        时间复杂度: O(1)
        """
        if self.isEmpty():
            return False
        else:
            if self.size == 1:
                # 删除后队列变空
                pass  # 不重置指针
            # 队尾指针向前移动（循环）
            self.r = self.limit - 1 if self.r == 0 else self.r - 1
            self.size -= 1
            return True

    def getFront(self):
        """获取队首元素"""
        if self.isEmpty():
            return -1
        else:
            return self.deque[self.l]

    def getRear(self):
        """获取队尾元素"""
        if self.isEmpty():
            return -1
        else:
            return self.deque[self.r]

    def isEmpty(self):
        """判断队列是否为空"""
        return self.size == 0

    def isFull(self):
        """判断队列是否已满"""
        return self.size == self.limit

循环索引的关键理解

指针移动规律

在固定数组实现中，关键是理解循环索引的移动：

1
2
3
4
5
# 向后移动（队尾插入，队首删除）
next_index = 0 if current_index == limit - 1 else current_index + 1

# 向前移动（队首插入，队尾删除）  
prev_index = limit - 1 if current_index == 0 else current_index - 1

边界情况处理

  1. 空队列插入：第一个元素插入时，队首和队尾指针都指向同一位置
  2. 单元素删除：删除唯一元素后队列变空，但指针位置不需要重置
  3. 满队列检测：通过size变量而非指针位置来判断队列是否已满

性能分析

时间复杂度对比

操作 列表实现 数组实现 说明
insertFront O(n) O(1) 列表需要移动所有元素
insertLast O(1)均摊 O(1) 列表可能需要扩容
deleteFront O(n) O(1) 列表需要移动所有元素
deleteLast O(1) O(1) 两种实现都是常数时间
getFront/getRear O(1) O(1) 直接索引访问

空间复杂度

  • 列表实现：O(k)，但可能因为动态扩容导致额外开销
  • 数组实现：O(k)，固定空间，无额外开销

应用场景

双端队列的典型应用

  1. 滑动窗口问题：需要在窗口两端进行操作
  2. 回文检测：从两端向中间检查字符
  3. 撤销/重做功能：需要在两端添加和删除操作记录
  4. 广度优先搜索变种：某些图算法需要双向扩展

与其他数据结构的对比

数据结构 队首操作 队尾操作 适用场景
普通队列 删除O(1) 插入O(1) FIFO场景
栈 插入/删除O(1) 无操作 LIFO场景
双端队列 插入/删除O(1) 插入/删除O(1) 需要两端操作
动态数组 插入O(n)，删除O(n) 插入O(1)均摊，删除O(1) 随机访问

双端队列提供了比普通队列和栈更大的灵活性，在需要两端操作的算法中具有重要作用。固定数组的循环实现虽然代码复杂度稍高，但提供了最优的时间和空间性能。刷题中优先选择固定数组实现，性能更好，实际工程中如果容量不确定，可以考虑列表实现或者动态扩容的数组；此外，固定数据能使得内存使用更可控。