如何实现一个循环队列

news/2024/7/7 4:10:12

 下面是一个循环队列的完整实现,欢迎读者朋友参考和指正:

template
class CyclicQueue {
public:
    typedef T                    value_type;
    typedef size_t               size_type;
    typedef T&                   reference;
    typedef const T&             const_reference;

    CyclicQueue() : m_popPos(0), m_count(0) {
        assert(N > 0);
        m_beginPtr = (T*)(::operator new(sizeof(T) * N)); // 分配原始空间
        }

    ~CyclicQueue() {
        _Clear();                                 // this->_Clear();
        ::operator delete((void*)m_beginPtr);
        }

    CyclicQueue(const CyclicQueue & copy) : m_popPos(0), m_count(0) {
        assert(N > 0);
        m_beginPtr = (T*)(::operator new(sizeof(T) * N));  // 分配原始空间
        size_t copyPos = copy.m_popPos;
        for (size_type idx = 0; idx < copy.m_count; ++idx) {
            _Copy(idx, copy.m_beginPtr[copyPos]);   // this->_Copy();
            ++copyPos; copyPos %= N; ++m_count;
            }
        }

    CyclicQueue& operator=(const CyclicQueue & other) {
        if (this != &other) {                  // 检查自赋值
             CyclicQueue temp(other);    // 调用拷贝构造函数
             _Swap(temp);                      //  this->_Swap();
            }
        return (*this);
        }

    bool is_empty() const { return (m_count == 0); }
    bool is_full() const { return (m_count == N); }

    value_type front() {
        assert(m_count != 0);
        return (m_beginPtr[m_popPos]);
    }

    value_type front() const {
        assert(m_count != 0);
        return (m_beginPtr[m_popPos]);
    }

    value_type back() {
        return _Back();            // this->_Back();
    }
   
    value_type back() const {
        return _Back();           // this->_Back();
    }
 
   bool push(const_reference data = T()) {
        if (m_count < N) {                 // 不满!
            size_type pushPos = (m_popPos + m_count) % N;
            _Copy(pushPos, data);          // this->_Copy();
            ++m_count;
            return true;
            }
        return false;
    }

    bool pop(reference data) {
        if (m_count > 0) {                    // 不空!
            data = m_beginPtr[m_popPos];      // operator=
            _Destroy(m_popPos);               // this->_Destroy();
            --m_count; ++m_popPos; m_popPos %= N;   // 新的pop位置
            return true;
            }
        return false;
    }

    size_type size() const { return m_count; }
    size_type capacity() const { return N; }
    void clear() { _Clear(); }             // this->_Clear();
    void swap(CyclicQueue & other) {
        _Swap(other);                     // this->_Swap();
    }

private:
    void _Clear() {
        for (; m_count > 0; --m_count) {
            _Destroy(m_popPos);           // this->_Destroy();
            ++m_popPos; m_popPos %= N;
            }
        m_popPos = 0;
    }
 
    void _Destroy(size_type idx) {
        assert(idx < N);
        T *pTemp = (m_beginPtr + idx);
        pTemp->~T();                   // 调用析构函数销毁元素对象
    }

    void _Copy(size_type idx, const_reference data) {
        assert(idx < N);
        T *pTemp = (m_beginPtr + idx);
        new ((void*)pTemp) T(data);  // 调用placement new和拷贝构造函数复制对象
    }

    void _Swap(CyclicQueue & other) {
        std::swap(m_beginPtr, other.m_beginPtr);
        std::swap(m_popPos, other.m_popPos);
        std::swap(m_count, other.m_count);
    }

    value_type _Back() const {
        assert(m_count != 0);
        size_type pushPos = (m_popPos + m_count) % N;
        if (pushPos == 0)
            return (*(m_beginPtr + N - 1));
        return (m_beginPtr[pushPos - 1]);
    }

    value_type        *m_beginPtr;        // 队列存储空间起始位置
    size_type          m_popPos;          // 下次pop位置
    size_type          m_count;             // 有效元素个数
};





http://www.niftyadmin.cn/n/3654889.html

相关文章

Android学习第五天————ExpandableListView组件通过适配器BaseExpandableListAdapter实现两层列表项

ExpandableListView是对ListView的扩展&#xff0c;实现了当点击列表项时弹出下一层的列表项 同时它必须要通过相对应的适配器来实现数据的绑定 1、首先在布局文件中创建好组件 <ExpandableListViewandroid:id"id/extendview" android:layout_width"wrap_c…

关于char类型的取值范围

《高质量》一书page 104倒数第三行&#xff0c;说“char的取值范围为[-128, 127)”是不对的&#xff0c;正确的范围表示应该为[-128, 127]或者[-128, 128)。这是个笔误&#xff0c;特此更正&#xff01;感谢读者赵为民&#xff01;

Android学习第五天————AdapterViewFlipper组件

AdapterViewFlipper用来实现显示上一个组件&#xff0c;或显示下一个组件&#xff0c;或者自动播放组件 AdapterViewFlipper也是一个需要适配器来填充数据的组件 首先创建一个AdapterViewFlipper组件&#xff0c;同时添加几个按钮来实现显示上一个或下一个或自动播放的功能 …

两本小书的命运 --- 记《Effective STL》和《The Art Of Deception》两本书的出版翻译过程

这两年来&#xff0c;时常听到读者或者朋友们问我“最近还有新书要出版吗”&#xff0c;我的回答是&#xff0c;有两本拖了很久的书快要出版了。我乐观地估计&#xff0c;这两本书在2005年都能出版&#xff0c;然而&#xff0c;不幸的是&#xff0c;这两本书都未能如期出版。从…

Android学习第六天————android中数据存储的五种方式

数据的存取 1、通过键值对的形式来存读数据 SharedPreferences存储共享变量的文件路径位于“/data/data/应用程序包/shared_prefs”目录下 获取SharedPreferences的两种方式: 1 调用Context对象的getSharedPreferences()方法 2 调用Activity对象的getPreferences()方法 两种方式…

Android学习第七天————通过android提供的XmlPullParserFactory解析XML文件

示例代码 XML文件 <?xml version"1.0" encoding"UTF-8"?><users><user><name>小王</name><age>22</age></user><user><name>小李</name><age>23</age></user><…

关于《Visual C++技术内幕》(第四版)

书名&#xff1a;《Visual C技术内幕》&#xff08;第四版&#xff09;原作者&#xff1a;David J. Kruglinski翻译&#xff1a;潘爱民、王国印出版&#xff1a;清华大学出版社日期&#xff1a;1999年1月第1版价格&#xff1a;96元ISBN&#xff1a;ISBN 7-302-03243-2/TP.1738《…

Android学习第七天————将数据保存为JSON格式,通过JSONObject和JSONReader来解析JSON数据

一、将数据保存为JSON格式 //将数据用JSON写入文本public void jsonwrite() {// 创建一组姓名数据String[] nameArr new String[] { "小李", "萧晨", "小张", "小王" };// 创建一组年龄数据int[] ageArr new int[] { 23, 24, 22, 25…