ACSL -> 数据结构

AquaVision

1. ​栈（Stack）​
栈是一种线性数据结构，遵循后进先出​的原则。它只允许在一端（栈顶）进行数据的插入和删除操作。比如你倒水到水杯里，然后喝水。

特点：

• 基本操作包括 PUSH（将元素压入栈顶）和 POP（从栈顶弹出元素）。
  
• 栈顶是唯一可以访问的位置，栈底是固定的。
  

PUSH("A")的命令将键"A"放在队列的顶部；命令"X=POP()"从队列的底部移除项，并将其值存储到变量X 中。

2. ​队列（Queue）​
队列是一种线性数据结构，遵循先进先出​的原则。它允许在一端（称为队尾）插入元素，在另一端（称为队头）删除元素。

特点：

• 基本操作包括 PUSH（将元素插入队尾）和 POP（从队头删除元素）。
  
• 插入、删除和查询时：找出在项目列表中是否发现了特定项目，如果没有，则找出哪个项目与所讨论的项目接近
  

Example: 实现一个循环队列。

• Func1()：将元素插入队尾。
  
• Func2()：删除队头元素并返回。
  
• Func3()：检查队列是否为空。
  
• Func4()：检查队列是否已满。
  
• 当队尾指针到达数组末尾时，将其重置到数组开头，实现循环。
  
• 通过队头和队尾指针的位置判断队列是否为空或已满。
  

3. ​二叉搜索树（BinarySearch Tree, BST）​
二叉搜索树是一种非线性数据结构，每个节点最多有两个子节点（左子节点和右子节点）。对于任意节点，左子树的所有节点值都小于该节点的值，右子树的所有节点值都大于该节点的值。

特点：

• 支持高效的查找、插入和删除操作，时间复杂度为     ​O(log n)。
  
• 常用遍历法: 中序遍历 -> 先遍历左子树，然后访问当前节点，最后遍历右子树, 可以得到一个小到大的序列。
  

​4.堆（Heap）​

堆是一种特殊的完全二叉树，它满足以下性质：

• ​堆序性质：对于最大堆，每个节点的值都大于或等于其子节点的值；对于最小堆，每个节点的值都小于或等于其子节点的值。
  
• ​完全二叉树性质：除了最后一层，其他层都是满的，且最后一层的节点尽可能靠左排列。
  

堆通常用于实现优先级队列，支持高效地插入元素和删除最大（或最小）元素。

​特点:

堆序性质：

  
• 最大堆：父节点的值 ≥ 子节点的值。
    
• ​最小堆：父节点的值 ≤ 子节点的值。
  

完全二叉树：

  
• 堆的存储结构紧凑，通常用数组实现。
    
• 对于数组中的第 i 个元素：左子节点：2i + 1， 右子节点：2i + 2， 父节点：(i - 1) / 2
  

高效操作：

  
• 插入元素的时间复杂度：​O(log n)
    
• 删除最大（或最小）元素的时间复杂度：​O(log n)
    
• 查找最大（或最小）元素的时间复杂度：​O(1)