基础数据结构——栈和队列
该篇内容来自作者观看b站青岛大学王卓老师的数据结构与算法基础课的个人笔记https://space.bilibili.com/40323036?spm_id_from=333.788.b_765f7570696e666f.2
栈和队列
特点：
栈：
具有“先进后出”,”后进先出”的特性
队列：
具有“先进先出” “后进后出”的特性
只能限定在表的“端点”进行操作的线性表
栈的定义和特点：
栈 是 仅在表尾进行插入和删除的线性表
表尾称作栈顶；表头称作栈尾
插入到栈顶，称为入栈 压入 Push
从栈顶删除最后一个元素，称为出栈 弹出 Pop
栈和一般线性表的不同
仅在于运算规则不同
队列的定义和特点：
队列 是 在一端插入，在另一端删除的线性表，具有”先进先出“的特点
插入的操作称为”入队”，删除的操作称为“出队”
队列的相关概念
栈的表示和实现：
栈是一种线性表，所以有顺序存储和链式存储，即顺序栈和链栈
顺序栈的表示和实现：
创建栈：
top指针表示栈顶的上一位
base指针表示栈底
stacksize表示栈可使用的最大容量
顺序栈的建立：
判断是否为空栈：
看top==base
栈满：
看top-base==stacsize
当栈已经满了，仍插入元素，导致溢出，称为上溢
当栈已经空了，仍删除元素，导致溢出，称为下溢
初始化栈：
入栈和出栈：
入栈：
1.将元素存入栈顶
2.栈顶指针后移一位
出栈：
1.栈顶指针前移一位
2.取出栈顶元素
栈的其他操作：![]()
链栈的表示和实现：
创建：
这里指针的方向与一般的链表方向相反，后入栈的元素指向先入栈的元素，方便操作
入栈和出栈：
入栈：
1.生成新结点
2.将新结点数据域置e
3.新结点插入栈顶
4.修改栈顶指针
出栈：
1.将栈顶数据置e
2.临时保存栈顶结点
3.修改栈顶指针
4.释放临时指针，即原栈顶
取栈顶元素：
队列的表示和实现：
顺序队的表示和实现：
初始化：
队头队尾指针指向0
队空和队满的判断方法：
队空：出队时队头指针不断后移，最终两指针会相遇
q.front=q.rear;
队满：
因为队满和队空，一般情况下队尾指针都会和队头指针相遇，所以需要用别的表示方式表示队满情况。
1.另外设计一个变量，表示队列元素个数
2.少用一个元素空间
(rear+1)%MAXQSIZE==front;
预留一个空间，这时候如果执行入队操作，先进行(rear+1)%MAXQSIZE==front;
就能够得到队满的情况，如果执行出队操作，front指针后移，取模不为0，队不满
入队：
在执行过程，如果队列已经满了，队头的元素出队后，后面无法继续入队，而此时的队列却不为满，这将造成内存浪费，称为“假溢出”
假溢出解决办法：循环队列
利用模运算，当队尾指针+1对队列长度取模为0时，即队尾指针指向最大长度，赋值为0即可让尾指针回到队头
出队：
循环取模，队头到最大长度下标可以自动归0
取队头元素：
在初始化时，base指向new出来的数组空间的首地址，可以当成数组用
注：数组名，本质就是一个不能改变的指针；指针，本质就是一个能改变的数组名。
销毁队列：
链队的表示和实现：
指针变化情况
创建：
front指针为头结点
初始化：
![]()
入队和出队：
![]()
销毁链队：