简述

栈是一种常见的数据结构，由于其“后进先出”（LIFO）的特性而被广泛使用。栈的常见逻辑结构如下：

图源：@Rella 《glow》 91882132

简述

广义表是线性表的一种推广。线性表要求表中元素拥有统一的类型，而广义表无此限制。需要注意的是，广义表和线性表长度一般认为是有限的，但广义表的深度可以是无限的（即递归表）。

广义表是一种数据结构。对广义表的常见操作包括：

• 创建
• 从字符串形式创建
• 销毁
• 复制
• 取表头
• 取表尾
• 判空
• 求长度
• 求深度
• 从表头插入
• 从表头删除
• 遍历

广义表是Lisp语言的基本数据结构。后文以Common Lisp和C++给出各基本操作的示例。

名词注解

长度

指广义表中的元素个数。举例如下：

例一

1

(a, b)

该表中共有两个元素：原子项a，原子项b。因而该表的长度为2。

例二

1

(a, (b, c))

该表中共有两个元素：原子项a，广义表(b, c)。因而该表的长度为2。

深度

指广义表中子表的嵌套层数。举例如下：

例一

1

(a, b)

该表中没有子表，因而该表的深度为1。

例二

1

(a, (b, c))

该表中嵌套了一个无嵌套的子表，因而该表的深度为2。

由于高中接触过，大学本科期间又深入了些，以防忘记记一些注意事项、概念和模板之类的东西。

简单分类

数据结构

• 一维：

  • 基础：数组（Array），链表（Linked list)

  • 高级：栈（Stack），队列（Queue），双端队列（Deque），集合（Set），映射（Map）等。

• 二维：

  • 基础：树（Tree），图（Graph）

  • 高级：二叉搜索树（BST），堆（Heap），并查集（Disjoint Set），字典树（Trie）等。

• 特殊结构：

  • 位运算（Bitwise），布隆过滤器（BloomFilter）

  • 缓存（LRU）

  • ……

• ……

算法

• 分支（if-else，switch）

• 迭代（for，while）

• 递归（分治法，回溯法等）

• 搜索（深搜，广搜，A*等）

• 动态规划

• 二分查找

• 贪心

• 计算几何

• ……