文档介绍：2008级数据结构实验报告
实验名称: 实验二——栈和队列
学生姓名:
班级:
班内序号:
学号:
日期: 2009年11月7日

根据栈和队列的抽象数据类型的定义,按要求实现一个栈或一个队列。
要求:
实现一个共享栈
实现一个链栈
实现一个循环队列
实现一个链队列
编写测试main()函数测试线性表的正确性。
2. 程序分析
存储结构

关键算法分析

开辟一个空间,两个栈共享。top1和top2分别为栈1和栈2的栈顶指针。Stack_Size为整个数组空间的大小;栈1的底固定在下标为0的一端;栈2的底固定在下标为StackSize-1的一端。如果是压栈,则栈1的top1加1,栈2的top2减1;如果是出栈,则栈1的top1减1,栈2的top2加1。
压栈: 1、如果栈满,则抛出上溢异常;
2、判断是插在栈1还是栈2;
若是在栈1插入,则栈顶指针top1加1,在top1处填入x;
若是在栈2插入,则栈顶指针top2减1,在top2处填入x;
时间复杂度为O(1)
出栈:1、判断是在栈1删除还是在栈2删除。
2、若是在栈1删除,则
若栈1为空栈,抛出下溢异常;
删除并返回栈1的栈顶元素;
3、若是在栈2删除,则
若栈2为空栈,抛出下溢异常;
删除并返回栈2的栈顶元素;
时间复杂度为O(1)

链栈在压栈的时候先创造一个新的结点,将要加入的元素作为它的元素。将top->next指向这个新的结点。top指向这个新的结点。在出栈的时候,先构造一个工作节点,把当前的栈顶结点赋给它。将栈顶结点摘链,并释放工作结点。
压栈:1、工作指针p初始化;
2、生成一个元素值为x的新结点;
3、将新结点s插入到结点p之后;
时间复杂度为O(1)
ai
a1 ∧
top
x
s
①
②
top
出栈:1、判断链栈是否为空;
2、工作指针初始化;
3、x暂存被删元素值;
4、top下移;
5、释放工作指针;
时间复杂度为O(1)
ai-1
ai
a1 ∧
top
top
p
程序运行结果

开始
A、B初始化
输入num1,data1
溢出
输出A、B
输入num2
输出A、B
输出异常
结束

链栈:
开始
初始化
压栈
出栈
输出链栈
输出