数据结构第三章:栈和队列

1.栈:后进先出的线性表

基本操作:考试应该可以直接用

初始化:InitStack(S)

清空栈:ClearStack(S)

判栈空:IsEmpty(S)

判栈满:IsFull(S)

入栈:Push(S,x)

出栈:Pop(S,&x)

取栈顶元素:GetTop(S,&x)

栈的表示和实现:

顺序栈,链栈

2.队列:先进先出的线性表

(1)队列:队尾允许插入,队头允许删除

(2)队列存储:

链队列:包含队头指针和队尾指针 

顺序队列:一维数组表示,但这样会有假溢出问题(可能会考简答题)

假溢出:75页  队头指针指向当前队头元素队尾指针指向真正队尾元素的后                面一个单元,当队尾指针rear=MAXSIZE时,认为队满,但这是在没                有元素出队的情况下,一旦有元素出队,队头指针移动,但队尾指针                不动,仍然认为队满,但实际已经有单元空出,因此叫做“假溢出”。

(3)假溢出解决办法:循环队列  76页

当rear+1=MAXSIZE时,令rear = 0

或者利用取模运算,即让rear一直加一递增,但计算真正数组存储下标的时候,让rear = (rear+1)mod(MAXSIZE)

(4)判断循环队列满还是空的方法:

普通顺序队列判断队空的条件为rear = front,即队尾指针等于队头指针,顺序队列也一样,但这时候判断队满就会有歧义,所以我们规定循环队列的最后一个结点不用,当rear+1=front的时候表示队列已满,由于是循环队列rear真正的值需要取模运算,所以           判断循环队列是否为满的方法为:    (rear+1)mod(MAXSIZE)= front                                                                                            判断循环队列是否为空的方法为:       rear = front                                                                                                                                 这时候其实是有两个空单元的:队尾指针所指单元和队尾指针的后继单元

习题:3.1     3.2     3.9    

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容