1. 栈的定义
是限定仅在表尾进行插入或删除操作的线性表
表尾即栈顶Top
表头即栈底Base
特点:后进先出
2. 栈的存储结构
栈的顺序存储:顺序栈
栈顶链式存储:链栈
2.1 顺序栈
设置Top指针:top指在栈顶元素之后一个位置
设置Base指针:指示栈底元素在顺序的位置
stackszie表示栈可使用的最大容量
2.2 链栈
链栈是运算受限的单链表,只能在链表表头进行操作
链表的头指针是栈顶
不需要头结点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处进行
3.栈的应用
数制转换
括号匹配
迷宫求解(深度优先搜索?
表达式求值
后缀表达式
4.队列的定义
是限定只能在表的一段(表尾)进行插入,在表的另一端(表头)进行删除的线性表
队尾rear:允许插入的一端
队头front:允许删除的一端
先进先出
5.队列的存储结构
队列的顺序表示
5.1 循环队列
1.初始化建空队列时,令front = rear =0
2. 每当插入新的队列尾元素时,队尾指针增1
3. 每当删除队列头元素时,头指针增1
头指针始终指向队列头元素
尾指针始终指向队列尾元素的下一个位置
约定:队列头指针在队列尾指针的下一位置上时,作为队列呈满状态的标志
循环队列的队满条件:(sq. rear +1)%maxsize == sq.front
链队列结构