循环队列的实现

Chynna ·

更新时间:2024-11-15

· 519 次阅读

我认为用数组做队列，首先要考虑的是队列的容量问题。解决队列的容量大家都是用循环队列的方式。但是使用循环队列需要考虑的问题是下标的控制。还有就是线程安全的问题。不能够出现对同一位置多次入队，多次出队问题。
再考虑到以上问题的同时，在下又想到一个问题就是一个线程入队的同时另一个线程能不能出队那？要衡量这个问题就需要考虑，当同时出现时，这个线程的操作是否影响另一个线程的操作问题。思虑再三，个人觉得出队和入队修改的下标并不是同一个变量，只是读取了下下标变量，因为读写是可以同时的所以应该是没问题的。除了上述解释，又想到了其实这个可以在宏观上大概理解为一个线程在往文件里面写一个在从文件里面读，只是不能存在多个一起写一起从相同偏移读。

所以代码实现如下(windows)

#include “stdafx.h”
#include
#include
#include
using namespace std;

void writeFile(LPCSTR path,LPCSTR content)
{
std::ofstream outfile(path,ios::app);
outfile << content << endl;
}
//个人认为队列可以存在一个线程入队的同时一个线程出队
//临界区
static CRITICAL_SECTION _wcritical; //写
static CRITICAL_SECTION _rcritical; //读
static CONDITION_VARIABLE _wconditon; //写条件变量
static CONDITION_VARIABLE _rcondition;//读条件变量
template
class CQUEUE{
public:
//创建队列
static CQUEUE* createQueue(int length)
{
CQUEUE* lpQueue = new CQUEUE;
lpQueue->iheadIndex = 0;
lpQueue->itailIndex = 0;
lpQueue->length = length;
lpQueue->array = new T[length];
memset(lpQueue->array,0,sizeof(T)*length);
InitializeCriticalSection(&_wcritical);
InitializeCriticalSection(&_rcritical);
return lpQueue;
}
//入栈
void pushQueue(T v_value)
{
EnterCriticalSection(&_wcritical); //控制不能多个线程同时入队
//队列是否为满
while(length == itailIndex - iheadIndex)
{
//队满挂起当前线程
SleepConditionVariableCS(&_wconditon,&_wcritical,INFINITE);
}
array[(itailIndex++) % length] = v_value;
WakeConditionVariable(&_rcondition);
LeaveCriticalSection(&_wcritical);
}
T popQueue()
{
EnterCriticalSection(&_rcritical);
T rtValue = 0;
while(itailIndex == iheadIndex)
{
//队空
SleepConditionVariableCS(&_rcondition,&_rcritical,INFINITE);
}
rtValue = array[(iheadIndex++)%length];
WakeConditionVariable(&_wconditon);
LeaveCriticalSection(&_rcritical);
return rtValue;
}
int iheadIndex;
int itailIndex;
int length;
T *array;
};

DWORD WINAPI PushThreadProc(LPVOID lpParam)
{
int iCount = 1000;
int number = (int)lpParam;
while(iCount–)
{
g_pQueue->pushQueue(number);
printf(“pushnum:%d ThreadId:%d pushvalue:%d\n”,number,GetCurrentThreadId(),number);
/std::string strPath = “C:/Users/Administrator/Desktop/”;
char buf[10];
memset(buf,0,sizeof(buf));
itoa(number,buf,10);
strPath += buf;
strPath += “.txt”;
string strContent = “pushnum:”;
memset(buf,0,sizeof(buf));
itoa(iCount,buf,10);
strContent += buf;
writeFile(strPath.c_str(),strContent.c_str());/ //输出文件日志观察是否出现死锁用的
}
return 0;
}
DWORD WINAPI PopThreadProc(LPVOID lpParam)
{
int number = (int)lpParam;
int iCount = 1000;
while(iCount–)
{
int rtValue = g_pQueue->popQueue();
printf(“popnum:%d ThreadId:%d popvalue:%d\n”,number,GetCurrentThreadId(),rtValue);
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
g_pQueue = CQUEUE::createQueue(10);
int number1 = 1,number2 = 2,number3 = 3,number4 = 4,number5 = 5,number6 = 6;
CreateThread(NULL,0,PushThreadProc,&number1,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number2,0,NULL);
CreateThread(NULL,0,PushThreadProc,&number3,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number4,0,NULL);
CreateThread(NULL,0,PushThreadProc,&number5,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number6,0,NULL);
char c = 0;
cin >> c;
return 0;
}

对以上的代码简单的说下，以上的队列是线程安全的，使用了类模版，考虑到的是因为存储的数据类型可以不一样。存储类型要有构造函数因为在分配空间的时候是调用的该类型的构造。（其实一般也不用，因为基本类型有隐式的转换，一般的类和结构体都有默认的构造）
2
int number1 = 1,number2 = 2,number3 = 3,number4 = 4,number5 = 5,number6 = 6;
CreateThread(NULL,0,PushThreadProc,&number1,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number2,0,NULL);
CreateThread(NULL,0,PushThreadProc,&number3,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number4,0,NULL);
CreateThread(NULL,0,PushThreadProc,&number5,0,NULL);
CreateThread(NULL,0,PopThreadProc,&number6,0,NULL);
这一块为什么不用循环？
像这个样子
for(int i= 0；i < 3;i++)
{
CreateThread(NULL,0,PushThreadProc,&i,0,NULL);
CreateThread(NULL,0,PopThreadProc,&i,0,NULL);
}
因为传递的是指针可能出现当主线程 i已经+1后开启的线程才运行那么就会出现本来考虑的是传 1 进去，但是由于线程执行的慢此时读取到的就是2.所以不是本来的意图。
以上实测没什么问题。