基础数据结构——栈和队列

该篇内容来自作者观看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指针为头结点

初始化：

入队和出队：

销毁链队：

取头结点元素：