数据结构知识点-栈和队列

栈和队列

一、栈

栈又称为“后入先出（LIFO：Last In First Out）”线性表

空栈：0单元使用则TOP=-1；0单元不用则TOP=0

顺序栈可能发生上溢或者下溢，而链栈一般不会发生上溢

链栈的栈顶指针，相当于链表的头指针。链栈的栈顶结点，相当于链表的开始结点，入栈采用头插的方法

注意函数中形参不能反向传递，故函数中对指针形参指向的修改，不能带回主调函数。但是对指针形参所指空间的内容的修改，是可以带回主调函数的。

解决形参不能反向传递的方法：

将要带回主调函数的形参定义为全局变量（缺点：函数的独立性下降，不利于移植）

将要带回主调函数的形参作函数返回值

传地址（指针或多重指针）（C语言，定义新形参为指向原形参类型的指针，即将传值改为传址）

传引用（C++，形参定义为引用类型）

为解决不带头结点的链栈可能出现形参不能反向传递的问题，一般可采用上6所述方法，常用的方法是

将栈顶指针定义为全局变量

将修改后的栈顶指针作为函数返回值

改用带头结点的链栈，

双重封装构造仅含栈顶指针的头结点，

定义二重指针，即指向指针（栈顶指针）的指针，此时即可通过修改二重指针所指空间的内容（栈顶指针）来带回修改后的栈顶指针（但是双重指针比较复杂，不建议使用）

函数的设计原则之一是，不改变无关量。如在取栈顶元素等“引用（拷贝）型而非加工型”操作时，不应该将原栈顶结点作为结果返回，而应该开辟新的空间拷贝并存储取栈顶结点并返回之，否则后续对取到的栈顶结点进行操作时可能会影响原链栈数据，而返回拷贝结点可以避免之

void类型函数返回主调函数的语句：

二、队列

队列：只允许在表的一端（队头）进行删除操作，在表的另一端（队尾）进行插入的特殊线性表

顺序队列队头指针front总是指向当前队头元素的前一个位置，队尾指针rear指向当前队尾元素（队头在低位序处，队尾在高位序处）

顺序队列队空：rear\==front；队满：rear-front\==maxsize

顺序队列的假上溢：顺序队列中存在未用的存储单元，但是不能继续进行入队操作

解决方法：

将队列元素依次前移，但缺点是数据移动量大

将顺序队列构造为循环序列

链队列

循环队列解决队满和队空无法区分的方法

设置队头、队尾、及空/满标志

设置队头、队长

牺牲一个存储单元（front所指单元），即使得队满时rear指向front前一个单元，队空时二者指向同一个单元（此时队列长度为MAXSIZE-1）（推荐）

循环队列进行操作时，应该进行循环意义（%maxsize）下的操作

循环意义下的加法：（a+b）%maxsize

循环意义下的减法：（a-b+maxsize)%maxsize；加上maxsize为了使结果为正数

入队：

出队：

求队长：

队满：

队空：

数据结构初始化：开辟空间+成员赋初值

链队列仅限在表头删除，表尾插入（表头为链表的开始结点，表尾为终端结点）

链队列的头结点也是采用二次封装，内含头、尾指针

与顺序对不同的是，链队的头指针指向头结点，而非其前一个结点

链队列s头结点p出队操作

更改头指针（)

判断出队后是否为空，是则置空队（）

释放p（）