程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++輪回隊列完成模子

C++輪回隊列完成模子

編輯：關於C++

C++輪回隊列完成模子。本站提示廣大學習愛好者：（C++輪回隊列完成模子）文章只能為提供參考，不一定能成為您想要的結果。以下是C++輪回隊列完成模子正文

本文實例講述了C++輪回隊列完成模子。分享給年夜家供年夜家參考。詳細剖析以下：

前段時光在知乎上看到如許一個小標題：

用根本類型完成一隊列，隊列請求size是事後界說好的的。並且請求弗成以應用說話自帶的api，如C++的STL。通俗的完成很簡略，然則如今請求要盡量的時光和空間龐雜度的優化，要和說話自帶的api比擬時光和空間。這個隊列還要支撐以下的操作：

constructor: 初始化隊列

enqueue:入隊

dequeue:出隊

隊列是一種根本的數據構造，在平凡的運用中非常普遍，多半情形隊列都是用鏈表完成的。然則關於本題而言，用鏈表完成就有如許一個成績：因為每一個結點都存在至多一個指向前一個結點或後一個結點的指針，這就帶來了空間龐雜度的加年夜，所以其實不太合適請求。

這個時刻我想到了boost中的boost::circular_buffer，它是經由過程相似於數組的底層構造完成的一個輪回buffer。而數組的長處是空間龐雜度夠小(除去保持數據構造的索引項，空間龐雜度為線性)，再完成成輪回構造可以最年夜化的應用空間。並且在隊列如許一種只在前後端拔出刪除的情形下，其push和pop的時光龐雜度也只要O(1)。

根本完成以下：

#ifndef __CIRCULAR_QUEUE_H__
#define __CIRCULAR_QUEUE_H__

#include <stddef.h>

template<typename T>
class circular_queue
{
public:
    explicit circular_queue(size_t maxsize)
        : maxsize_(maxsize + 1), head_(0), rear_(0)
    {
        array_ = new T[maxsize_];
    }

    circular_queue(size_t maxsize, const T& val)
        : maxsize_(maxsize + 1), head_(0), rear_(0)
    {
        array_ = new T[maxsize_];
        for (size_t i = 0; i != maxsize; ++i)
        {
            array_[i] = val;
        }
        rear_ = maxsize;
    }

    circular_queue(const circular_queue& rhs)
        : maxsize_(rhs.maxsize_), head_(rhs.head_), rear_(rhs.rear_)
    {
        array_ = new T[maxsize_];
        for (int i = 0; i != maxsize_; ++i)
        {
            array_[i] = rhs.array_[i];
        }
    }

    ~circular_queue()
    {
        delete [] array_;
    }

    circular_queue& operator=(const circular_queue& rhs)
    {
        if (this == &rhs)
        {
            return *this;
        }
        delete [] array_;
        maxsize_ = rhs.maxsize_;
        head_ = rhs.head_;
        rear_ = rhs.rear_;
        array_ = new T[maxsize_];
        for (int i = 0; i != maxsize_; ++i)
        {
            array_[i] = rhs.array_[i];
        }
        return *this;
    }

    bool empty() const
    {
        return head_ == rear_;
    }

    size_t size() const
    {
        return (rear_ - head_ + maxsize_) % maxsize_;
    }

    T& front()
    {
        return array_[head_];
    }

    const T& front() const
    {
        return array_[head_];
    }

    void push(const T& val)
    {
        if ((rear_ + 1) % maxsize_ != head_)
        {
            array_[rear_] = val;
            rear_ = (rear_ + 1) % maxsize_;
        }
    }

    void pop()
    {
        if (head_ != rear_)
        {
            head_ = (head_ + 1) % maxsize_;
        }
    }

private:
    size_t maxsize_;
    int     head_;
    int     rear_;
    T*      array_;
};

#endif

隊列長度 = 數組長度 - 1

預留了一個單元的數組元素空間作為隊尾標志。

這個只是粗陋的完成，沒有斟酌到一些情形，好比線程平安、STL算法，函數對象的兼容等。代碼只是簡略的測試了一下，若有毛病迎接斧正:)

總的來講，這類思緒的輪回隊列有以下長處：

1、應用固定的內存，不須要隱式或不測的內存分派。

2、早年端或後端停止疾速的常量時光的拔出和刪除元素。

3、疾速的常量時光的對元素停止隨機拜訪。(假如須要的話可以界說operator[])

4、實用於及時和對機能有嚴厲請求的運用法式。

還可以進一步擴大，當隊列滿的時刻，從一端拔出則籠罩沖刷失落另外一真個數據，如許的一個模子可以運用於這些場所：