C使用两个stack实现queue类实验报告.doc

实 验 报 告 姓 名：黄雄镖 学 号院系专业：软件学院2013级教务4班 完成日期：2014 年 10 月 14 日 实验题目：使用两个stack实现queue类 ??需求分析： 使用两个stack实现根据给出的queue类的定义实现queue的基本功能，如.入队：q.push(x):将x元素加到队列的末端；.出队：q.pop() 弹出队列的第一个元素；访问队头元素：如q.front()；判断队列空：q.IsEmpty()，当队列空时，返回true。 ??概要设计 实现方法： 用一个栈(firstStack)存放最新的数据，另外一个栈(secondStack)存放旧的数据 在进行front操作或者pop操作时，如果存放旧元素的栈(secondStack)不空，直接返回存放旧元素的栈的栈顶元素即可 如果存放旧元素的栈(secondStack)为空，则需要把存放新元素的栈(firstStack)的元素全部倒出来压到存放旧元素的栈(secondStack)内 进行该操作之后，存放旧元素的栈(secondStack)的栈顶元素就是firstStack的栈底元素，也就是队列的列头元素 ??调试分析 测试过程中基本没有存在问题，IsEmpty操作的时间复杂度为O(1)，front()操作的时间复杂度为O(n)，push操作的时间复杂度为O(1)，pop操作的时间复杂度为O(n) ??用户使用说明 基本操作说明如下: 声明一个队列q:Queue q； 入队：q.push(x):将x元素加到队列的末端；. 出队：q.pop() 弹出队列的第一个元素； 访问队头元素：如q.front()； 判断队列空：q.IsEmpty()，当队列空时，返回true。 ??测试结果 测试中使用STL中的queue与我自己编写的queue进行入队，访问队头元素，出队等比较，测试是否与STL中的queue存在差别 过程: 进行500次向两个队列加入40个随机元素，然后判断队头元素是否一致，再将对头元素出队的操作。接下来把剩下的元素弹出，每次弹出前判断队头元素是否一致。最后判断两个队列是否都为空，输出存在错误的个数，结束测试 ??实验心得 通过此次实验，我加深了对stack和queue的理解，也对写测试用的程序和写代码注释有了更深刻的理解，体验到良好的代码风格以及注释的重要性 ??附录 程序文件名的清单:02.h 实现Queue类 Test.cpp 用于测试实现的Queue类