【栈的定义】

栈（Stack），是只允许在一端进行插入或删除操作的线性表，其中，允许插入、删除的那一端称为栈顶，不允许插入、删除的那一端称为栈底，当线性表中不含元素时，称为空栈

栈具有后进先出（Last In First Out，LIFO）的操作性质，如下图所示，假设某个栈 $S=(a_1,a_2,a_3,a_4,a_5)$ ，其中 $a_1$ 为栈底元素，$a_5$ 为栈顶元素，由于栈只能在栈顶进行插入、删除，故而进栈顺序为：$a_1,a_2,a_3,a_4,a_5$，出栈顺序为：$a_5,a_4,a_3,a_2,a_1$

【数据管理技术】

数据管理是数据处理的中心问题，即对数据进行分类、组织、编码、存储、检索和维护

随着应用需求的扩大以及计算机软件硬件的发展，数据管理技术也不断的在发展，数据管理技术的发展过程经历了以下三个阶段：

【数据】

数据（Data）是数据库中存储的基本对象，是描述事物的符号记录，描述事物的符号可以是数字，也可以是文字、图形、图象、声音

数据记录是计算机中表示和存储数据的一种格式，是有结构的数据，例如：(张三，男，25，北京)

【静态链表】

静态链表是借助数组实现的链表，与顺序表相比，其在进行增删操作时不需要移动大量元素，同时，其具有不能随机存取，固定容量不变的特点

可见，静态链表适用于不支持指针的编程语言（如：Lisp）和数据元素固定不变的场景（如：文件分配表FAT）

【概述】

循环链表分为循环单链表和循环双链表，两者分别是在单链表和双链表的基础上进行的改进，其最大的特点就是在遍历时，从一个结点出发总能到达链表的任一结点

对于循环单链表来说，其结点类型与单链表类型相同，只是表尾结点 p 的指针 next 指向头结点，此外，基本操作与单链表相似

【双链表】

双链表是在单链表的基础上在每个结点中多加入了前驱指针 prior，其指向当前结点的前驱结点

1
2
3
4
5
6

template <typename T> 
struct DNode {       //双链表结点
    T data;          //数据域
    DNode<T> *prior; //前驱指针
    DNode<T> *next;  //后继指针
};

【单链表】

概述

线性表的链式存储方式称为链表，其通过一组任意存储单元来存储线性表中的数据元素，最基本一种链接方式构成的链表称为单链表

【顺序表】

线性表的顺序存储又称顺序表，其使用一组地址空间连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两元素在物理存储空间上也相邻

顺序表具有以下特点：

【逻辑结构】

线性表是具相同数据类型的 $n$ 个数据元素的有限序列，其中，相同数据类型意味着每个数据元素所占的存储空间相同，数据元素个数 $n$ 为线性表的长度，当 $n=0$ 时称为空表，反之 $n\neq 0$ 时称为非空表

一个非空表常记为：

【算法】

算法是对特定问题求解步骤的描述，是指令的有限序列，每个指令表示一或多个操作，其具有以下特性：

• 有穷性：能在有穷步、有穷时间内执行完毕
• 确定性：相同输入会获得相同输出
• 可行性：算法是可行的
• 输入：具有零到多个输入
• 输出：具有一到多个输出