Abstract Data Types ADTs(抽象数据类型)
ADT 的含义就是数据集合及其可以执行的操作的规范(增删改查),通常涉及效率权衡,内存使用权衡等等问题.
- 描述一个集合可以做什么，而不是如何做
- 我们可以说，Vector 和 LinkedList 都实现了名为“列表”的抽象数据类型的操作。
其他的 ADT 实例：栈、队列、集合、映射、图。
Linkedlist(链表)
节点
- 数据域：存储数据元素
- 指针域：指向下一个节点的地址
当你想插入元素的时候，你只需要创建一个新的节点，将其数据域设置为你要插入的数据，然后将其指针域设置为指向链表中下一个节点的地址，然后将这个新的节点插入到链表中。
当你想删除元素的时候，你只需要找到你要删除的节点，然后将其前一个节点的指针域设置为指向被删除节点的下一个节点的地址，然后删除被删除节点。
在执行某些操作的时候链表往往会十分高效.这些都是运用内存换来的.
Stacks(栈)
栈是一种线性数据结构，它只允许在表尾进行插入和删除操作。栈顶元素是最近添加的元素，栈底元素是最近删除的元素。栈的操作有入栈、出栈、查看栈顶元素、查看栈底元素。
- Last-In-First-Out(LIFO)：栈顶元素是最近添加的元素，栈底元素是最近删除的元素。
- only add/remove/examine operations allowed at the top of the stack.只能在栈顶进行操作。
Stack 的基本函数：
- push: 入栈，将元素压入栈顶
- pop: 出栈，删除栈顶元素
- peek: 查看栈顶元素
include "stack.h"
- s.isEmpty(): 判断栈是否为空
- s.peek(): 查看栈顶元素
- s.pop(): 返回并删除栈顶元素
- s.push(x): 入栈元素 x
- s.size(): 返回栈的大小
栈在计算机中非常的常见 undo stack 撤销栈操作：
- 编辑器的撤销操作
- 编译器的错误恢复
- 数据库事务的回滚操作
- 程序的回退操作
注意事项
- 栈的大小是有限的，当栈满时，不能再入栈，当栈空时，不能再出栈。
- 中括号运算符不适用于栈，因为栈的操作是先进后出。他只允许你访问最顶部的元素
Queues(队列)
队列是一种线性数据结构，它只允许在表头进行插入和删除操作。队列的操作有入队、出队、查看队首元素、查看队尾元素。
- First-In-First-Out(FIFO)：队列的头部是最先进入队列的元素，尾部是最先离开队列的元素。
- Elements are stored in order of insertion.元素按照插入的顺序排列。
- Can add only to end of the queue,and can only examine/remove the front 只能在队列的末尾添加元素，并且只能检查和移除队列的前端元素。
基础函数
- enqueue: 入队，将元素添加到队尾
- dequeue: 出队，删除队首元素
- peek: 查看队首元素
- isEmpty: 判断队列是否为空
- size: 返回队列的大小
队列在计算机中也非常常见
- 打印队列：打印机、打印队列
- 任务调度：操作系统的进程调度
- 缓存：缓存的淘汰策略
- 排队：银行排队
注意事项
- 队列的大小是有限的，当队列满时，不能再入队，当队列空时，不能再出队。
- 队列的操作是先进先出，所以队首元素是最先进入队列的元素，队尾元素是最先离开队列的元素。