山东大学《数据结构》实验指导03栈与队列.docx
194 浏览量
2022-12-15
23:22:51
上传
评论
收藏 19KB DOCX 举报
实验三栈与队列
一实验任务
1)栈的应用
2)队列的表示与实现二实验目的
1)了解栈与队列的特性
2)掌握栈的顺序、链式存储表示及实现
3)掌握队列的顺序、链式存储表示及实现
4)掌握栈与队列在实际问题中的应用三实验原理
1 .栈的特性
栈(Stack)又称堆栈，是一种特殊的线性表，可定义为插入、删除和访问 只能在
某一端进行的线性数据结构。堆栈允许插入、删除和访问的一端称为栈顶 (Top),另一
端称为栈底(Bottom)。栈顶的第一个元素被称为栈顶元素。
堆栈的性质决定它的数据是按''先进后出〃的顺序被访问，即最先存储的元素 最
后被访问、删除，最后存储的元素最先被访问、删除，所以栈也称为、'LIFO"
(Last_In, First_Out)。
栈济抽象数鬼类型定义如下：
ADT Stack{
D={ai | a； E ElemSet, i = 1,2,…,n, n>0}R = { v an, ai > |
ai-i, ai eD, i = 2,…，n }
约定dn端为栈顶，dl端为栈底。
基本操作：
InitStack(&S)操作结果：构造一个空栈S。
Push(&S, e)初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(&S, &e)初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。
GetTop(S, &e)初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
StackEmpty(S)初始条件：栈S已存在。
操作结果：假设S为空栈，那么返回TRUE,否那么返回FALSE。
StackLength(S)初始条件：栈S已存在。
操作结果：返回S的元素个数，即栈的长度。
StackTraverse(S, visit())初始条件：栈S已存在且非空。
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit ()o 一
旦visit。失败，那么操作失败。
数据对象:
数据对象:
数据关系:
资源评论
