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 = 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 = 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个元素，第二个线程同样。最后主线程输出队列中最后的内容，然后清空。
队列用链表实现，可以试想一下，如果线程同步没有处理，指针操作时一定会引起崩溃