栈
- 后进先出
- 栈顶指针始终指向最上方元素
- 栈为空时栈顶指针为-1
常用操作
- 清空（clear）：
TOP = -1 - 获取栈内元素个数（size）：
size = TOP + 1 - 判空（empty）：
TOP == -1 - 进栈（push）：
st[++TOP] = x - 出栈（pop）：
TOP-- - 取栈顶（top）：
st[TOP]
注意：在进行出栈和取栈顶操作前必须判空。
队列
- 先进先出
- 队首指针
front指向首元素前一个位置 - 队尾指针
back指向尾元素
常用操作
- 清空（clear）：
front = back = -1 - 获取队内元素个数（size）：
size = back - front - 判空（empty）：
front == back - 入队（push）：
q[++back] = x - 出队（pop）：
front++ - 取队首（get_front）：
q[front + 1] - 取队尾（get_back）：
q[back]
注意：在进行出队、取队首和取队尾操作前必须判空。
链表
- 不连续
- 由数据域和指针域构成
为链表分配空间
-
malloc函数位于
<cstdlib>，返回void*int* p = (int*)malloc(sizeof(int)); -
new运算符typename* p = new typename; -
free函数释放
malloc函数分配的空间 -
delete运算符释放
new运算符分配的空间
基本操作
-
创建链表
略
-
查找元素
从第一个节点开始不断判断数据域是否等于x
-
插入元素
注意保存前驱节点指针
-
删除元素
注意保存前驱节点指针
静态链表
直接用结构体数组当链表用，适用于数据较少的情况