数据结构实验报告 实验名称：实验二——栈和队列 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 2.1 题目 1 根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。 要求： 1、实现一个共享栈 2、实现一个链栈 3、实现一个循环队列 4、实现一个链队列 编写测试 main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 共享栈： 链栈： 2.2 关键算法分析 2.2.1 共享栈 入栈： if (top1 == top2 - 1) //判断栈是否已满 { throw "上溢"; } if (i == 1) //如果要入栈1 { data[++top1] = x; //top 指针加一，然后赋值 } if (i == 2)//如果要入栈2 { data[--top2] = x; //top 指针减 1，赋值 } 出栈： if (i == 1) { if (top1 == -1) //判断栈1 是否为空 { throw "下溢"; } return data[top1--]; //返回出栈元素的值并且栈顶指针下移 } if (i == 2) { if (top2 == StackSize) { throw "下溢"; } return data[top2++]; //返回出栈元素的值并且栈顶指针上移 } 查找栈顶元素： if (i == 1) { if (top1 != -1) //如果栈1 非空 { return data[top1]; } } if (i == 2) { if (top2 != StackSize) //如果栈2 非空 { return data[top2]; } } 判断栈是否为空： if (i == 1) { if (top1 == -1) { return true; } else { return false; } } if (i == 2) { if (top2 == StackSize) { return true; } else { return false; } } return false; 输出栈中元素： int temp1 = top1; //工作指针 while (temp1 != -1) //判断栈一是否为空 { cout<< data[temp1--] << " "; //输出元素，工作指针减一 } int temp2 = top2; //工作指针 while (temp2 != StackSize) //判断栈二是否为空 { cout<< data[temp2++] << " "; //输出元素，工作指针加一 } 2.2.2 链栈 析构函数： while (top) //判断是否为空 { struct Node*p = top; //新建工作指针，并用 top指针初始化 top = top->next; //top指针后移 delete p; } 入栈： struct Node*p = new Node; //新建工作指针指向新结点 p->data = x; //新结点的数据域赋值为 x p->next = top; //新节点的 next域记录 top指针指向地址 top ...
