[键入公司名称]实验二堆栈和队列——数据结构实验报告实验二堆栈和队列实验目的和要求：掌握堆栈和队列的基本概念；掌握堆栈和队列的基本操作。实验原理：堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。堆栈的存储结构：顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。队列的存储结构队列的存储结构同线性表一样，可以分为顺序结构和链式结构。顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。实验内容：试编写一个算法，建立一个学生成绩栈，要求从键盘上输入N个整数，按照下列要求分别进入不同的栈。若输入的整数X小于60，则进入第一个栈；若输入的整数x大于等于60并小于100，则进入第二个栈；若输入的整数x大于100，则进入第三个栈；分别输出每个栈的内容。编写一个程序，使用两个链队q1和q2，用来分别存储由计算机产生的20个100以内的奇数和偶数，然后每行输出q1和q2的一个值，即奇数和偶数配对输出，直到任一队列为空为止。假设一个算术表达式中可以包括三种括号：“（”和“）”，方括号“[”和“]”及花括号“{”和“}”，且这三种括号可以任意顺序的嵌套使用。编写算法判断给定表达式中所包含的括号是否配对出现。实验设计：伪代码该算法的核心是将成绩分类，并将其分别插入到不同的栈中，栈顶指针加1；入栈函数用模板voidPushStack(ElemTypex)函数。将输入的数据进行条件选择，分别插入到新栈l,m,h中。程序代码：#include<stdlib.h>#include<time.h>#include"iostream"usingnamespacestd;classList;typedefintElemType;classSeqStack{unsignedheight;inttop;intmaxsize;ElemType*elements;public:SeqStack(intsize);//构造函数，size用来设置栈的大小~SeqStack(){delete[]elements;}//析构函数voidPushStack(ElemTypex);//进栈函数，将元素x压入栈中ElemTypePopStack(ElemTypex);//出栈函数，将栈顶元素值放入x中voidClearStack(){top=-1;}//清栈函数，用于释放所占的内存空间boolIsFullStack(){returntop==maxsize-1;}//判断栈是否为满boolIsEmptyStack();//判断栈是否为空voidPrintStack();//将栈中元素输入到屏幕上};SeqStack::SeqStack(intsize){height=0;top=-1;maxsize=size;//设置最大栈高elements=newElemType[size];}voidSeqStack::PushStack(ElemTypex){if(IsFullStack())cout<<"栈已满~";else{elements[++top]=x;height++;}}ElemTypeSeqStack::PopStack(ElemTypex){x=elements[top];top--;height--;returnx;}boolSeq