数据结构实验报告 实验名称:实验二——栈和队列 学生姓名: 班级: 班内序号: 学号: 日期: 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 ...