大宇私人领地伊甸园丨宁愿做了后悔,也不要错过后悔[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__*/
The bottom line, for me, is simple.

Let’s hope it doesn’t take 500 years for a discipline of testing to becomes the standard for software developers.

From:dayu

您好!请登录

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

已有2评论

  • CarlosEvoth
    CarlosEvoth 回复

    Many webmasters be sure the worth of having backlinks to their sites. Divers be got rid of about the tiring function of obtaining backlinks on themselves which takes time and patience. In the past, it seemed that contrariwise big corporations could exterior out the banknotes compulsory to actually obtaining https://otvet.mail.ru/answer/1806194253 backlinks. So they were the ones who ended up basic in the search motor rankings. But things drink changed and there are diverse services from time to time accessible to the small business owner.


    2018年08月02日23:33
  • 大宇丨
    大宇丨 回复

    [/给力]


    2017年10月13日23:27

大宇博客

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