【上海海事大学】C++线程安全型队列的实现
线程安全型队列的实现。编写一个线程安全的队列，所谓线程安全，就是该队列能够实现多个线程同时正确的增删改队列结点，也就是能够实现对队列这个临界资源的保护。需要实现的函数包括: (1)InitQueue函数:初始化一个空的队列，并初始化各个用于保护队列的信号量。 (2)EnQueue函数:在队列尾部加入一个结点 (3)DeQueue函数:删除队列头部结点 (4)Clear函数:删除队列中的所有结点 (5)Find函数:查找队列中是否有指定的元素，若有，返回能够访问该结点的指针;若无，返回NULL。 (6)Print函数:打印当前队列中的所有元素。 完成该队列后，自己编写一个测试程序，生成多个线程同时读写该队列，验证你的队列行是否正确，并给出测试报告。
编程提示: (1)使用多线程编程，线程间可以共享一份待排序数据数组，建立多个线程，每个线程处理该数组的一部分。 (2)程序的关键是如何通过划分数据，把排序过程分成多个子任务，然后每个子任务就可以有一个线程来完成。 (3)数据划分和排序，可以考虑数据结构中列举的各种内部排序算法。例如:快速排序通过选择枢轴元素，容易把待排数据分割成几块:归并排序对于两个已经有序的数组进行合并，比较有效率，等等。 (4)在数据划分阶段和数据合并阶段，不需要每个线程都在执行，根据自己的设计，可能有某个或某几个线程来完成即可。 (5)排序线程数量是你自己定义的，最好是2N形式，比较容易计算。
(1)必须实现“读者-写者”模型。插入、删除等影响数据的操作函数是“写者”，查找和打印函数是“读者”。课设要求多个线程并发执行插入、删除、查找等函数，允许多个线程同时执行“查找”操作。 (2)必须对程序进行全方位的测试。包括单元测试(对每个函数进行的测试)和集成测试。在单元测试通过后，将各个函数组合在一起后，可能会引入新的bug，因此需要对程序进行集成测试。在集成测试中，建立多个线程，每个线程执行上万次的插入、删除、查找操作，测试程序结果是否正确。 (3)集成测试要求必须是全自动测试。测试过程中不需要人工输入数据，所有需要输入数据的地方，可以借助类似“rand()”的随机数生成函数自动生成一个随机数，或者固定指定一个数或数组。 (4)集成测试中判定测试结果正确的方法。 在单元测试中，可以通过观察程序输出结果来判断函数是否存在bug。但在集成测试中，因为测试次数是上万次，无法通过眼睛观察屏幕输出来判定。因此需要辅助判定方法。例如:如果你使用3个线程同时插入，每个线程插入的结点数量分别为N1、N2和N3，在程序运行结束后，统计链表中的结点数量N，如果插入正确，则N=N1+N2+N3(即:i(N== N1+N2+N3){ 本次测试通过.})。同样，你可以采用插入和删除相结合的方式进行数量判定。测试数据量要大，规模至少为“万次”。在查找测试中，你可以“特意”向链表中插入一些指定元素，从而保证能够找到结果;即使是全部随机生成，查找不到指定元素也是可以的。 要求使用多种不同的集成测试用例，反复测试运行结果是否存在bug。测试用例通不能说明你的程序是正确的，只能说这次测试没有发现你程序的bug。
