2007级数据结构实验报告
实验名称：实验二栈和队列日期：2008年11月15日
1．实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容21题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：1、实现一个共享栈2、实现一个链栈3、实现一个循环队列4、实现一个链队列编写测试mai
函数测试线性表的正确性。
2程序分析21存储结构存储结构：特殊线性表：栈，队列
第1页
f下标：0
1a2……
i1aitop1
共享栈
StackSize1
a1
bjtop2
……
b2b1
栈2底
栈1底
top
a
a
1
栈顶
fro
trear
a6a5a4
a7
循环队列
a1
链栈
∧栈底
fro
trear
空链队列
∧
fro
t
a1
非空链队列
a2
a
rear∧
∧
22关键算法分析共享栈的入栈算法伪码（Push）：1．如果栈满，抛出上溢异常。2．判断是插在栈1还是栈2：21如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x；22如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x。共享栈的出栈算法伪码（Pop）：1判断是在栈1删除还是在栈2删除。2若是在栈1删除，则21若栈1为空栈，抛出下溢异常；22删除并返回栈1的栈顶元素；3若是在栈2删除，则31若栈2为空栈，抛出下溢异常；32删除并返回栈2的栈顶元素。
第2页
f共享栈的取栈顶元素算法伪码（GetTop）：1．判断是在栈1取还是栈2取；2．如果在栈1取，则21若栈1不空，返回栈顶元素的值，不删除；22若栈1空，返回0；3．如果在栈2取，则31若栈2不空，返回栈顶元素的值，不删除；32若栈2空，返回0。链栈的入栈算法伪码（Push）：1．申请一个新的结点，数据域为x；2．将新结点插在栈顶；3．栈顶指针重新指向栈顶元素。链栈的出栈算法伪码（Pop）：1．如果栈空，抛出下溢异常；2．暂存栈顶元素；3．将栈顶结点摘链；4．删除该结点，返回该元素的值。链栈的取栈顶元素算法的伪码（GetTop）：1．如果栈非空，返回栈顶元素的值，不删除。循环队列的入队算法伪码（E
Queue）：1．如果队满，抛出上溢异常；2．队尾指针在循环意义下加1；3．在队尾插入元素。循环队列的出队算法伪码（DeQueue）：1．如果队空，抛出下溢异常；2．队头指针在循环意义下加1；3．读取并返回出队前的队头元素。循环队列的取队头元素算法伪码（GetQueue）：1．r