数据结构实验报告 栈和队列

第11页北京邮电大学电信工程学院第1页2007级数据结构实验报告实验名称：实验二栈和队列日期：2008年11月15日1．实验要求实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容2.1题目1根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。要求：实现一个共享栈实现一个链栈实现一个循环队列实现一个链队列编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构存储结构：特殊线性表：栈，队列下标：下标：01i-1共享栈a1a2……aibj……b2b1栈1底top1top2栈2底StackSize-1循环队列front循环队列frontreara6a5a4a7an-1ana1∧栈顶栈底top链栈∧∧a1a2an∧非空链队列∧空链队列frontrearfrontrear2.2关键算法分析共享栈的入栈算法伪码（Push）：1．如果栈满，抛出上溢异常。2．判断是插在栈1还是栈2：2.1如果在栈1插入，则栈顶指针top1加1，在top1处填入元素x；2.2如果在栈2插入，则栈顶指针top2加1，在top2处填入元素x。共享栈的出栈算法伪码（Pop）：1.判断是在栈1删除还是在栈2删除。2.若是在栈1删除，则2.1若栈1为空栈，抛出下溢异常；2.2删除并返回栈1的栈顶元素；3.若是在栈2删除，则3.1若栈2为空栈，抛出下溢异常；3.2删除并返回栈2的栈顶元素。共享栈的取栈顶元素算法伪码（GetTop）：判断是在栈1取还是栈2取；如果在栈1取，则2.1若栈1不空，返回栈顶元素的值，不删除；2.2若栈1空，返回0；3．如果在栈2取，则3.1若栈2不空，返回栈顶元素的值，不删除；3.2若栈2空，返回0。链栈的入栈算法伪码（Push）：申请一个新的结点，数据域为x；将新结点插在栈顶；栈顶指针重新指向栈顶元素。链栈的出栈算法伪码（Pop）：如果栈空，抛出下溢异常；暂存栈顶元素；将栈顶结点摘链；删除该结点，返回该元素的值。链栈的取栈顶元素算法的伪码（GetTop）：如果栈非空，返回栈顶元素的值，不删除。循环队列的入队算法伪码（EnQueue）：如果队满，抛出上溢异常；队尾指针在循环意义下加1；在队尾插入元素。循环队列的出队算法伪码（DeQueue）：如果队空，抛出下溢异常；队头指针在循环意义下加1；读取并返回出队前的队头元素。循环队列的取队头元素算法伪码（GetQueue）：如果队空，抛出下溢异常；值为队头指针的工作指针i在循环意义下加1，注意不给队头指针赋值；返回队头指针的队头元素。链队列的入队算法伪码（EnQueue）：申请一个数据域为x的新结点；该结点的next域置空；将其插到队尾。链队列的出队算法伪码（DeQueue）：如果队空，抛出下溢异常；暂存队头元素；将队头元素所在结点摘链；如果被删除的队头元素同时也是队尾元素，则修改队尾指针。链队列的取队头元素算法伪码（GetQueue）：如果队非空，返回队头元素的值，不删除。∧∧a1∧特殊情况：队列长度为1a1a2an∧一般情况：队列长度大于1链队列出队操作frontrearfrontrearpp以上算法的时间复杂度均为O(1)。可比较的是空间性能。初始时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。链栈没有栈满的问题，只有当内存没有可用空间时才会出现栈满。但是每个元素都需要一个指针域，所以产生了结构性开销。循环队列和链队列的空间性能的比较与顺序栈和链栈的空间性能比较类似，只是循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队列。3.程序运行结果开始开始新建共享栈B对B入栈操作判断两个栈是否为空并输出判断结果对B取栈顶元素操作判断两个栈是否为空并输出判断结果判断两个栈是否为空并输出判断结果对B出栈操作共享栈主函数流程图：新建链栈LS新建链栈LS对LS入栈操作对LS取栈顶元素操作判断栈是否为空并输出结果对LS出栈操作判断LS是否为空并输出结果开始链栈主函数流程图：新建循环队列CQ新建循环队列CQ对CQ入队操作对C Q取队头元素操作判断队是否为空并输出结果对CQ出队操作判断CQ是否为空并输出结果开始循环队列主函数流程图：对LQ出队操作对LQ出队操作新建链队列LQ判断链队列是否为空并输出结果对LQ入队操作判断队是否为空并输出结果对LQ取队头元素操作判断链队列是否为空并输出结果开始判断链队列是否为空并输出结果链队列主函数流程图：测试条件：主函数都大都采用了使用循环来入栈（队）（链队列除外），问题规模取决于栈本身的大小，而链队列和链栈不受限制（除非内存没了）。每次入栈（队）、出栈（队）、取栈顶（队头）元素前后都执行函数Empty()判断栈（队列）是否为空。测试结论：程序可以正常且正确运行。总结调试时出现的问题及解决的方法对循环队列进行测试时，由于之前设定的队列的大小是10，故在入队时设定的k最大为9了即k<10，然而运行时程序出错，于是试着把k<10改为了k<9，重新运行便无问题了。这是因为循环队列实际上是留出了一个空的数组元素空间，以便判断队是否已满，所以实际上最多只能储存9个元素。故k=0;k<9。但后来添加了异常处理，故而改为可以由用户自行输入元素值。心得体会这次选择的题目非常基本，是共享栈、链栈、循环队列、链队列的基本实现，相对也比较容易，但却是很基础的，有些细节部分是值得高度重视的，也是容易出错的地方，例如上所写的测试循环队列时出现的问题。对这些基本的特殊线性表的测试与实现是编写较复杂程序的基础，应该牢固掌握它们。这个实验也让我学会了异常处理的方法。下一步的改