408数据结构第三章

这篇具有很好参考价值的文章主要介绍了408数据结构第三章。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

栈

特性后进先出
只允许在一端进行插入或删除操作的线性表
每接触一种新的数据结构类型，都应该分别从逻辑结构、存储结构和对数据的运算三方面入手

操作
initstack(&s)初始化一个空栈s
stackempty(s)判断一个栈是否为空
push(&s,x)进栈，未满成为新栈顶
pop(&s,&x)出栈，非空弹出栈顶元素
gettop(s,&x)读栈顶元素，用x返回栈顶元素
destroystack(&s)销毁栈

顺序存储结构
采用顺序存储的栈称为顺序栈
栈顶指针：S.top
初始设置S.top=-1
栈顶元素S.data[S.top]
栈空条件：S.top==-1
栈满条件：S.top==MaxSize-1
栈长：S.top+1

注意：
top指向的是栈顶元素
进栈操作为S.data[++S.top]=x
出栈操作为x=S.data[S.top–]

若栈顶指针初始化为S.top=0,top指向栈顶元素的下一位
入栈操作为S.data[S.top++]=x
出栈操作为x=S.data[–S.top]

共享栈
栈满：top1-top0=1

栈的链式存储结构
称为链栈
便于多个栈共享存储空间和提高效率，不存在栈满上溢情况
链式存储便于结点的插入删除
入栈和出栈都在链表表头进行
对于带不带头结点的链栈实现会有不同

每个元素需要1个存储单元，每进栈一次top+1，出栈一次top-1
单循环链表通过尾指针可以很方便找到表头结点，没有尾结点找需要花费O(n)时间

队列

先进先出
只允许一端进入另一端删除
队头：允许删除的一端，队首
队尾：允许插入的一端

操作
initQueue(&Q)初始化队列
QueueEmpty(Q)判断列空
EnQueue(&Q,&x)入队，未满将x加入成为新的队尾
DeQueue(&Q,&x)出队，非空删除队头元素并用x返回
GetHead(Q,&x)读队头元素，非空将队头元素赋值给x

顺序存储结构
初始(队空）：Q.front=Q.rear=0

循环队列
把存储队列元素的表从逻辑上视为一个环
队空：Q.front=Q.rear=0
队满：(Q.rear+1)%MaxSize==Q.front
队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize

链式存储
队列的链式表示称为链队列
实际上是一个同时带有队头指针的队尾指针的单链表
链队列为空：Q.frontNull且Q.rearNull
不带头结点的链式队列在操作上比较麻烦
单链表表示的链式队列特别适合于数据元素变动比较大的情形，不存在队满产生溢出问题

双端队列
允许两端都可以进行入队和出队操作的队列
输出受限的双端队列：一端只插入另一端允许插入删除
输入受限的双端队列：一端只删除另一端允许插入删除

1.循环队列存储在数组A[0…n]中，入队操作为rear=(rear+1) mod maxsize,这里maxsize等于n+1
2.循环队列存储在数组A[21]中，front指向队头元素的前一个位置，rear指向队尾元素，这里maxsize等于21
队长为**(rear-front+maxsize)%maxsize**
3.求值：
删:front=(front+1)%个数
插:rear=(rear+1)%个数
4.链式存储方式队列的队列进行删除操作时需要头尾指针可能都要修改