3.1.2 栈的顺序存储结构

教材导航 · 第3章

原书定位

印刷页P63起,对应PDF第75页。下文为目视整理的知识提要;完整内容见原书对照。

用数组加栈顶下标实现顺序栈,基本操作均为 O(1)O(1)。先确定 top 指向栈顶元素还是下一空位置,再写判空、判满和自增自减。

约定,数组为 data[0..M-1]空栈入栈出栈栈满
top 指栈顶元素top=-1data[++top]=xx=data[top--]top=M-1
top 指下一空位置top=0data[top++]=xx=data[--top]top=M

出栈只改变栈顶指针,原数组单元可能仍有旧值,但该值已不属于逻辑栈。读栈顶不改变 top。

图3.2 栈顶指针和栈中元素

图3.2 栈顶指针和栈中元素,原书P64。

下级知识点

对应练习

3.1 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P63,PDF第75页

原书对照,原书P64,PDF第76页

原书对照,原书P65,PDF第77页