序列

问题描述

序列是一种动态数组数据结构，可以根据需要动态调整大小。
在C++中为vector，Java中为ArrayList，Python中为list。
它们都提供了添加、删除、访问等基本操作。

基本概念

特点

1. 动态调整大小
2. 支持随机访问
3. 支持尾部快速操作
4. 内存连续存储
5. 支持迭代遍历

代码实现

1. C++ Vector

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 创建vector
    vector<int> nums;                    // 空vector
    vector<int> nums1(5);               // 包含5个0
    vector<int> nums2(5, 1);            // 包含5个1
    vector<int> nums3 = {1, 2, 3, 4, 5};  // 初始化列表
    
    // 基本操作
    nums.push_back(1);      // 在末尾添加元素
    nums.pop_back();        // 删除末尾元素
    nums.insert(nums.begin() + 1, 2);  // 在位置1插入元素2
    nums.erase(nums.begin() + 1);      // 删除位置1的元素
    
    // 访问元素
    cout << nums[0] << endl;         // 使用下标访问
    cout << nums.at(0) << endl;      // 使用at()访问（带边界检查）
    cout << nums.front() << endl;    // 第一个元素
    cout << nums.back() << endl;     // 最后一个元素
    
    // 容量操作
    cout << nums.size() << endl;     // 当前大小
    cout << nums.capacity() << endl; // 当前容量
    nums.reserve(10);               // 预分配空间
    nums.resize(5);                // 调整大小
    
    // 迭代器操作
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 范围for循环
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

2. Java ArrayList

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        // 创建ArrayList
        ArrayList<Integer> nums = new ArrayList<>();           // 空列表
        ArrayList<Integer> nums1 = new ArrayList<>(5);         // 指定初始容量
        ArrayList<Integer> nums2 = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));  // 使用数组初始化
        
        // 基本操作
        nums.add(1);           // 在末尾添加元素
        nums.remove(nums.size() - 1);  // 删除末尾元素
        nums.add(1, 2);       // 在位置1插入元素2
        nums.remove(1);       // 删除位置1的元素
        
        // 访问元素
        System.out.println(nums.get(0));         // 获取元素
        nums.set(0, 10);                         // 修改元素
        System.out.println(nums.get(nums.size() - 1));  // 最后一个元素
        
        // 容量操作
        System.out.println(nums.size());         // 当前大小
        nums.ensureCapacity(10);                // 确保容量
        nums.trimToSize();                      // 调整容量
        
        // 迭代器操作
        Iterator<Integer> it = nums.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
        System.out.println();
        
        // 增强for循环
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

3. Python List

# 创建列表
nums = []                      # 空列表
nums1 = [0] * 5               # 包含5个0
nums2 = [1, 2, 3, 4, 5]       # 直接初始化
nums3 = list(range(5))        # 使用range创建

# 基本操作
nums.append(1)       # 在末尾添加元素
nums.pop()          # 删除末尾元素
nums.insert(1, 2)   # 在位置1插入元素2
nums.pop(1)         # 删除位置1的元素
del nums[1]         # 另一种删除方式

# 访问元素
print(nums[0])       # 第一个元素
print(nums[-1])      # 最后一个元素
nums[0] = 10         # 修改元素

# 切片操作
print(nums[1:4])     # 位置1到3的元素
print(nums[::2])     # 步长为2
print(nums[::-1])    # 反转列表

# 列表方法
nums.extend([6, 7])  # 扩展列表
nums.count(1)        # 统计元素出现次数
nums.index(1)        # 查找元素位置
nums.reverse()       # 反转列表
nums.sort()          # 排序（升序）
nums.sort(reverse=True)  # 排序（降序）

# 列表推导式
squares = [x**2 for x in range(5)]  # [0, 1, 4, 9, 16]
evens = [x for x in nums if x % 2 == 0]  # 获取偶数

应用场景

1. 动态数据存储
2. 栈和队列实现
3. 数据缓存
4. 序列处理
5. 算法实现

注意事项

1. 扩容机制
2. 内存管理
3. 插入删除性能
4. 随机访问效率
5. 迭代器失效

常见示例

1. 实现栈

class Stack {
private:
    vector<int> elements;
public:
    void push(int x) {
        elements.push_back(x);
    }
    
    int pop() {
        int x = elements.back();
        elements.pop_back();
        return x;
    }
    
    int top() {
        return elements.back();
    }
    
    bool empty() {
        return elements.empty();
    }
};

class Stack {
    private ArrayList<Integer> elements;
    
    public Stack() {
        elements = new ArrayList<>();
    }
    
    public void push(int x) {
        elements.add(x);
    }
    
    public int pop() {
        return elements.remove(elements.size() - 1);
    }
    
    public int top() {
        return elements.get(elements.size() - 1);
    }
    
    public boolean empty() {
        return elements.isEmpty();
    }
}

class Stack:
    def __init__(self):
        self.elements = []
    
    def push(self, x: int) -> None:
        self.elements.append(x)
    
    def pop(self) -> int:
        return self.elements.pop()
    
    def top(self) -> int:
        return self.elements[-1]
    
    def empty(self) -> bool:
        return len(self.elements) == 0