C++与数据结构第二次上机实验——堆栈和队列

[键入公司名称] 实验二 堆栈和队列 ——数据结构实验报告 实验二堆栈和队列 一、实验目的和要求： 1、 掌握堆栈和队列的基本概念； 2、 掌握堆栈和队列的基本操作。 二、实验原理： 1、 堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。 2、 堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。 3、 堆栈的存储结构： （1） 顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。 （2） 链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。 4、 队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。 5、 队列的存储结构 队列的存储结构同线性表一样，可以分为顺序结构和链式结构。 （1） 顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。 （2） 链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。 三、实验内容： 1、 试编写一个算法，建立一个学生成绩栈，要求从键盘上输入 N 个整数，按照下列要求分别进入不同的栈。 （1） 若输入的整数 X 小于60，则进入第一个栈； （2） 若输入的整数 x 大于等于60 并小于100，则进入第二个栈； （3） 若输入的整数 x 大于100，则进入第三个栈； （4） 分别输出每个栈的内容。 2、 编写一个程序，使用两个链队 q1 和 q2，用来分别存储由计算机产生的 20 个100以内的奇数和偶数，然后每行输出 q1 和 q2 的...