大宇私人领地伊甸园丨宁愿做了后悔,也不要错过后悔[www.mrdayu.com]
注册

24小时联系邮箱:[email protected]

编程人生
您现在的位置: 首页 > 编程人生 > C/C++语言 > C++STL库QUEUE队列源码使用,实现以及原理

C++STL库QUEUE队列源码使用,实现以及原理

引:在很多时候,模块和模块之间交流非常频繁,程序员之间的内存读写操作竞争越发激烈,传统的解决死办法:NEW在写入时,下个模块读取后再析构,在经历每秒成千上万,或者上百万次循环后,程序运行计算时间变得越来越慢。

Queue的介绍:

一个先入先出(FIFO)的数据结构

Queue的使用:

queuer.push():推入

queuer.pop():弹出

queuer.size():队列中大小

queuer.isEmpty():队列是否为空

Queue的源码实现:

///C++实现
/***************************************************************************
**File name:RQueue.h **
**Author: CY **
**Function:Drawing base class **
**Date: 17.10.12 **
** **
**Version: 1.0 **
** **
**I'm not going to make you understand this sentence **
**If you have any problems, **
**Please visit:http://www.mrdayu.com/archives/263.html **
****************************************************************************
** **
**Version: 2.0[2017.10.01-NOW]:Cy **
****************************************************************************/
#ifndef __RQueueClassH__
#define __RQueueClassH__

#include <assert.h> // 错误检查

template <class RElem>
class RQueue
{
public:
    RQueue(int MaxSize = 4300); //init maxsize = 4300
    RQueue(const RQueue<RElem> &OtherQueue);
    ~RQueue(void);
    
    void Push(const RElem &Item); // Adds Item to Queue end
    RElem Pop(void); // Returns Item from Queue
    bool Pop(RElem &Item); // Returns Item from Queue
    bool Pop(unsigned char *Item,int size); // Returns Item from Queue
    bool NoDataPop(void); // quick pop no return
    void Clear(); // Clear Queue All Data
    inline int Size(void); // Returns Number of Elements
    inline bool isEmpty(void);
    
protected:
    RElem *Data; // The actual Data array
    const int MAX_NUM; // The actual spaces will be one more than this
    int Beginning, // Numbered location of the start and end
    End;
    
    // Instead of calculating the number of elements, using this variable
    // is much more convenient.
    int ElemCount; //
};

// Queue Constructor function
template <class RElem>
RQueue<RElem>::RQueue(int MaxSize) :
    MAX_NUM(MaxSize) // Initialize the constant
{
    // This extra space added will allow us to distinguish between
    // the Beginning and the End locations.
    Data = new RElem[MAX_NUM + 1];
    Beginning = 0;
    End = 0;
    ElemCount = 0;
}

// Queue Copy Constructor function
template <class RElem>
RQueue<RElem>::RQueue(const RQueue &OtherQueue) :
    MAX_NUM(OtherQueue.MAX_NUM) // Initialize the constant
{
    Beginning = OtherQueue.Beginning;
    End = OtherQueue.End;
    ElemCount = OtherQueue.ElemCount;
    
    Data = new RElem[MAX_NUM + 1];
    for (int i = 0; i < MAX_NUM; i++)
        Data[i] = OtherQueue.Data[i];
}

// Queue Destructor function
template <class RElem>
RQueue<RElem>::~RQueue(void)
{
    delete[] Data;
}

// push() function
template <class RElem>
void RQueue<RElem>::Push(const RElem &Item)
{
    // Error Check: Make sure we aren't exceeding our maximum storage space
    assert(ElemCount < MAX_NUM); Data[End++] = Item; ++ElemCount; // Check for wrap-around if (End > MAX_NUM)
    End -= (MAX_NUM + 1);
}

// Dequeue() function
template <class RElem>
RElem RQueue<RElem>::Pop(void)
{
    // Error Check: Make sure we aren't dequeueing from an empty queue
    assert(ElemCount > 0);
    
    RElem ReturnValue = Data[Beginning++];
    --ElemCount;
    
    // Check for wrap-around
    if (Beginning > MAX_NUM)
        Beginning -= (MAX_NUM + 1);
    
    return ReturnValue;
}

template <class RElem>
bool RQueue<RElem>::Pop(RElem &Item){
    // Error Check: Make sure we aren't dequeueing from an empty queue
    assert(ElemCount > 0);
    
    Item = Data[Beginning++];
    --ElemCount;
    
    // Check for wrap-around
    if (Beginning > MAX_NUM)
        Beginning -= (MAX_NUM + 1);
    
    return true;
}

// Returns SIZE of Items from Queue
template <class RElem>
bool RQueue<RElem>::Pop(unsigned char *Item, int SIZE){
    
    // Error Check: Make sure we aren't dequeueing from an empty queue
    assert((ElemCount > 0) && (ElemCount - SIZE > 0));
    
    for (int i = 0; i<SIZE; i++){ Item[i] = Data[Beginning++]; --ElemCount; // Check for wrap-around if (Beginning > MAX_NUM)
        Beginning -= (MAX_NUM + 1);
    }
    
    /*int tmp_End = End;
int BegintoEnd = MAX_NUM - Beginning;
if (BegintoEnd >= SIZE){
memcpy(Item, &Data[Beginning], SIZE);
Beginning += SIZE;
ElemCount -= SIZE;
if (Beginning > MAX_NUM)
Beginning -= (MAX_NUM + 1);
}
else{
int BegintoSize = SIZE - BegintoEnd;
memcpy(Item, &Data[Beginning], BegintoEnd);
memcpy(&Item[BegintoEnd], &Data[0], BegintoSize);
Beginning = BegintoSize;
ElemCount -= SIZE;
}*/
    
    //只有两种情况
    // 1:开始指标比结束指标大
    // 2:结束指标比开始指标大
    
    //if (Beginning>tmp_End){
    ////说明beginning+ElemCount>MaxCount
    // int BegintoEnd = MAX_NUM - Beginning;
    // if (BegintoEnd >=SIZE){
    // memcpy(Item, &Data[Beginning], SIZE);
    // Beginning += SIZE;
    // ElemCount -= SIZE;
    // if (Beginning > MAX_NUM)
    // Beginning -= (MAX_NUM + 1);
    // }
    // int BegintoSize = SIZE - BegintoEnd;
    // memcpy(Item, &Data[Beginning], BegintoEnd);
    // memcpy(&Item[BegintoEnd], &Data[0], BegintoSize);
    // Beginning = BegintoSize;
    // ElemCount -= SIZE;
    //}
    //else{
    ////说明beginning+ElemCount<MaxCount[可以直接启动] 
    // memcpy(Item, &Data[Beginning], SIZE); 
    // Beginning += SIZE; // ElemCount -= SIZE; 
    // if (Beginning > MAX_NUM)
    // Beginning -= (MAX_NUM + 1);
    //}
    
    //return
    return true;
}
template <class RElem>
bool RQueue<RElem>::NoDataPop(void){
    // Error Check: Make sure we aren't dequeueing from an empty queue
    assert(ElemCount > 0);
    
    Beginning++;
    --ElemCount;
    
    // Check for wrap-around
    if (Beginning > MAX_NUM)
        Beginning -= (MAX_NUM + 1);
    
    return true;
}
/// Clear Queue All Data /////////////////////////////////////////////////
template <class RElem>
void RQueue<RElem>::Clear(){
    Beginning = 0;
    End = 0;
    ElemCount = 0;
}
template <class RElem>
inline int RQueue<RElem>::Size(void)
{
    return ElemCount;
}

template <class RElem>
inline bool RQueue<RElem>::isEmpty(void)
{
    return ElemCount <= 0 ? true:false;
}
#endif /*__RQueueClassH__*/
56.2K

您好!请登录

合作网站快捷登录:
点击取消回复

已有1评论

  • 大宇丨
    大宇丨 回复

    [/给力]


    2017年10月13日23:27

购物盒子

点击这里给我发消息点击这里给我发消息