24.8.9.11数据结构|链栈和队列

链栈

1、理解

实际上是一个仅在表头进行操作的单链表,头指针指向栈顶结点或头结点,以下恋栈均指带头结点的链栈.

2、 基本操作

1、定义结构：节点含有数据域和指针域

2、初始化操作：建立一个带头结点的空栈

3、取栈顶元素操作：取出栈的栈顶元素，将栈中第一个节点的值送到e所指向的内存单元，不删除栈顶结点

4、求栈长操作：从栈顶开始统计栈中元素个数直到栈底为止

5、入栈操作：将值为X的数据元素插入栈中使X成为新的栈顶元素

（先创建一个新结点，其数据域的值为X，然后将该结点插入到头节点之后作为栈顶结点）考虑空间申请是否成功

6、出栈操作：删除S的栈顶元素（先将栈S的栈顶结点的值送到一所指的内存单元然后删除栈顶结点）考虑栈空

7、栈空操作：判断栈是否为空

8、输出栈：输出自栈顶到栈底的元素值

 3、代码

 4、课后练习

例题1

编写算法利用栈将带头结点的单链表逆置

例题2

设计一个算法判断一个字符串是否对称若是则返回一否则返回零

 队列

顺序队列8.11

1、理解

顺序队列，即队列的顺序存储结构，就是嗯嗯利用一组地址连续的存储单元依次存放从对头到队尾的数据元素，同时利用两个变量分别记录当前队列中队头元素和队尾元素的位置。

特殊的线性表,只允许在一端插入另一端删除，队尾插入，队头删除。对头指针和队尾指针并不一定是指针变量，也可以是下标变量。在用下标变量来描述队列时，在初始化空队列时，队头指针和队尾指针的值都为零。当当front==rear时，队列为空，当rear==Maxsize时，队列为满。

入队时尾指针rear加一，出队时头指针front加一

2、基本操作（顺序队列、循环队列）

1、顺序队列的类型定义：基地址、队头指针、队尾指针

2、初始化操作：构建一个空队列

3、求队列长度操作：返回队列的元素个数

4、取队头元素操作：通过一返回队列的队头元素值

5、入队操作：将值为X的元素插入到队列中使X成为新的队尾元素

6、出队操作：删除队列中的队头元素同时将队头元素值通过E代回，原队列中的第二个元素成为新的队头元素。

7、判断队空操作：判断队列queue是否为空若队列为空则返回一否则返回零

8、输出队列操作：从对头到队尾依次输出队列queue中的所有元素

代码

顺序队列

循环队列

队列也是一个线性表其存储结构也分为顺序存储和链式序存储两种分别称为顺序队列和链队列

循环队列

1、理解

为了解决入队列操作产生假溢出现象，可以把顺序队列从逻辑上看成是一个环，即当队列为指针或队头指针达到最大下标值Maxsize时，再从下标为零的位置开始举，这种队列称为循环队列。、

循环队列中队头指针和队尾指针的后移可以利用除最大下标值取余的运算来实现

队头指针后移操作：

front=（front+1）%MAXQSIZE；

队列长度的计算公式为：

（ rear+Maxsize-front）%Maxsize

链式队列

 实际上是一个带头指针和尾指针的单链表。

基本操作

1、结构定义

2、初始化操作

3、求队列长度操作

4、判断队列为空

5、取队头元素

6、入队列操作

7、出队操作

8、输出队列操作

代码