C/C++线程安全型队列的实现？

Question

编写一个线程安全的队列，所谓线程安全，就是该队列能够实现多个线程同时正确的增删改队列结点，也就是能够实现对队列这个临界资源的保护。需要实现的函数包括：
（1） InitQueue函数：初始化一个空的队列，并初始化各个用于保护队列的信号量。
（2） EnQueue函数：在队列尾部加入一个结点
（3） DeQueue函数：删除队列头部结点
（4） Clear函数：删除队列中的所有结点
（5） Find函数：查找队列中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL。
（6） Print函数：打印当前队列中的所有元素。
完成该队列后，自己编写一个测试程序，生成多个线程同时读写该队列，验证你的队列执行是否正确。
我基本不会，所以请具体给出代码（可以把代码发我邮箱[e-mail]），简单的介绍我不会采纳，我会先测试，无错的话可以追加悬赏分。
其中线性安全请用到互斥量Mutex，这是我先在在学的，所以很关键。

Answer 1

首先，互斥量这种线程相关的内容是平台相关的，我假设你用的是windows平台开发。其次，说明一下我的开发环境，vs2008，控制台程序，空的工程。最后给你贴代码，分文件来看。===头文件QueueNode.h======你需要的节点数据可能不是整数，只要将typedef int QUEUEDATA这一句的int换成你想要的类型即可，但要注意，这个类型必须实现赋值操作符重载，相等比较操作符重载，以及复制构造函数===#ifndef _QUEUE_NODE_H_#define _QUEUE_NODE_H_typedef int QUEUEDATA;typedef struct node{QUEUEDATA data;node* m_pNext;}QUEUENODE;#endif===队列头文件Queue.h，有平台相关内容，请注意===#ifndef _QUEUE_H_#define _QUEUE_H_#include "QueueNode.h"#include <Windows.h>class ThreadSafeQueue{public:ThreadSafeQueue();virtual ~ThreadSafeQueue();bool InitQueue();void EnQueue(const QUEUEDATA& data);void DeQueue();void Clear();const QUEUENODE* Find(const QUEUEDATA& data) const;void Print();protected:HANDLE m_hMutex;QUEUENODE* m_pQueueHead;};#endif===队列函数实现文件Queue.cpp===#include "Queue.h"#include <iostream>ThreadSafeQueue::ThreadSafeQueue(){m_pQueueHead = new QUEUENODE;m_pQueueHead->m_pNext = 0;}ThreadSafeQueue::~ThreadSafeQueue(){Clear();delete m_pQueueHead;CloseHandle(m_hMutex);}bool ThreadSafeQueue::InitQueue(){m_hMutex = CreateMutex(0, FALSE, 0);return (m_hMutex!=0);}void ThreadSafeQueue::EnQueue(const QUEUEDATA& data){WaitForSingleObject(m_hMutex, INFINITE);QUEUENODE* pNode = new QUEUENODE;pNode->data = data;pNode->m_pNext = 0;QUEUENODE* pTemp = m_pQueueHead;while (pTemp->m_pNext != 0){pTemp = pTemp->m_pNext;}pTemp->m_pNext = pNode;ReleaseMutex(m_hMutex);}void ThreadSafeQueue::DeQueue(){WaitForSingleObject(m_hMutex, INFINITE);QUEUENODE* pNode = m_pQueueHead->m_pNext;if (pNode != 0){m_pQueueHead->m_pNext = pNode->m_pNext;delete pNode;pNode = 0;}ReleaseMutex(m_hMutex);}const QUEUENODE* ThreadSafeQueue::Find(const QUEUEDATA& data) const{WaitForSingleObject(m_hMutex, INFINITE);QUEUENODE* pNode = m_pQueueHead->m_pNext;while (pNode != 0){if (pNode->data == data){break;}pNode = pNode->m_pNext;}return pNode;ReleaseMutex(m_hMutex);}void ThreadSafeQueue::Clear(){WaitForSingleObject(m_hMutex, INFINITE);QUEUENODE* pNode = m_pQueueHead->m_pNext;QUEUENODE* pTemp = 0;while (pNode != 0){pTemp = pNode->m_pNext;delete pNode;pNode = pTemp;}m_pQueueHead->m_pNext = 0;ReleaseMutex(m_hMutex);}void ThreadSafeQueue::Print(){WaitForSingleObject(m_hMutex, INFINITE);QUEUENODE* pNode = m_pQueueHead->m_pNext;while (pNode != 0){std::cout << pNode->data << "\t";pNode = pNode->m_pNext;}std::cout << std::endl;ReleaseMutex(m_hMutex);}===测试代码文件main.cpp，包含了测试用可执行程序，两个操作queue的线程，需要说明的是，我本来打算用WaitMultipleObjects函数来等待两个线程都结束，但是没搞清楚是什么问题没有卡住，不打算继续纠缠它了，所以让主线程Sleep了5秒钟===#include "Queue.h"#include <iostream>DWORD WINAPI HandleQueue(void* pParam);DWORD WINAPI HandleQueue2(void* pParam);int main(){ThreadSafeQueue queue;queue.InitQueue();HANDLE hThread[2] = {0};DWORD threadID = 0;hThread[0] = CreateThread(NULL, 0, HandleQueue, (void*)(&queue), NULL, &threadID);hThread[0] = CreateThread(NULL, 0, HandleQueue2, (void*)(&queue), NULL, &threadID);//WaitForMultipleObjects(2, hThread, TRUE, INFINITE);Sleep(5000);queue.Print();queue.Clear();return 0;}DWORD WINAPI HandleQueue(void* pParam){ThreadSafeQueue* pQueue =&nbsp;reinterpret_cast<ThreadSafeQueue*>(pParam);for (int i = 0; i < 100; i++){std::cout << "HandleQueue EnQueue" << std::endl;pQueue->EnQueue(i);}for (int i = 0; i < 50; i++){std::cout << "HandleQueue DeQueue" << std::endl;pQueue->DeQueue();}return 0;}DWORD WINAPI HandleQueue2(void* pParam){ThreadSafeQueue* pQueue =&nbsp;reinterpret_cast<ThreadSafeQueue*>(pParam);for (int i = 0; i < 100; i++){std::cout << "HandleQueue2 EnQueue" << std::endl;pQueue->EnQueue(i+100);}for (int i = 0; i < 50; i++){std::cout << "HandleQueue2 DeQueue" << std::endl;pQueue->DeQueue();}return 0;}新建一个空的控制台程序工程，向工程中加入这几个文件，编译之后可以直接运行。第一个线程投入队列100个元素，出队50个元素，第二个线程同样。最后主线程输出队列中最后的内容，然后清空。队列用链表实现，可以试想一下，如果线程同步没有处理，指针操作时一定会引起崩溃