快捷導(dǎo)航

C++循環(huán)隊列實現(xiàn)模型

更新時間：2014年12月31日 08:59:15 投稿：shichen2014

這篇文章主要介紹了C++循環(huán)隊列實現(xiàn)模型,較為詳細(xì)的分析了循環(huán)隊列算法的原理與實現(xiàn)方法,具有一定的參考借鑒價值,需要的朋友可以參考下

本文實例講述了C++循環(huán)隊列實現(xiàn)模型。分享給大家供大家參考。具體分析如下：

前段時間在知乎上看到這樣一個小題目：

用基本類型實現(xiàn)一隊列，隊列要求size是預(yù)先定義好的的。而且要求不可以使用語言自帶的api，如C++的STL。普通的實現(xiàn)很簡單，但是現(xiàn)在要求要盡可能的時間和空間復(fù)雜度的優(yōu)化，要和語言自帶的api比較時間和空間。這個隊列還要支持如下的操作：

constructor: 初始化隊列

enqueue:入隊

dequeue:出隊

隊列是一種基本的數(shù)據(jù)結(jié)構(gòu)，在平常的應(yīng)用中十分廣泛，多數(shù)情況隊列都是用鏈表實現(xiàn)的。但是對于本題而言，用鏈表實現(xiàn)就有這樣一個問題：由于每個結(jié)點都存在至少一個指向前一個結(jié)點或后一個結(jié)點的指針，這就帶來了空間復(fù)雜度的加大，所以并不太適合要求。

這個時候我想到了boost中的boost::circular_buffer，它是通過類似于數(shù)組的底層結(jié)構(gòu)實現(xiàn)的一個循環(huán)buffer。而數(shù)組的優(yōu)點是空間復(fù)雜度夠小(除去維持?jǐn)?shù)據(jù)結(jié)構(gòu)的索引項，空間復(fù)雜度為線性)，再實現(xiàn)成循環(huán)結(jié)構(gòu)可以最大化的利用空間。而且在隊列這樣一種只在前后端插入刪除的情況下，其push和pop的時間復(fù)雜度也只有O(1)。

基本實現(xiàn)如下：

復(fù)制代碼代碼如下:

#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

隊列長度 = 數(shù)組長度 - 1

預(yù)留了一個單位的數(shù)組元素空間作為隊尾標(biāo)記。

這個只是簡陋的實現(xiàn)，沒有考慮到一些情況，比如線程安全、STL算法，函數(shù)對象的兼容等。代碼只是簡單的測試了一下，如有錯誤歡迎指正:)

總的來說，這種思路的循環(huán)隊列有以下優(yōu)點：

1、使用固定的內(nèi)存，不需要隱式或意外的內(nèi)存分配。

2、從前端或后端進(jìn)行快速的常量時間的插入和刪除元素。

3、快速的常量時間的對元素進(jìn)行隨機(jī)訪問。(如果需要的話可以定義operator[])

4、適用于實時和對性能有嚴(yán)格要求的應(yīng)用程序。

還可以進(jìn)一步擴(kuò)展，當(dāng)隊列滿的時候，從一端插入則覆蓋沖洗掉另一端的數(shù)據(jù)，這樣的一個模型可以應(yīng)用于這些場合：

保存最近接收到的取樣數(shù)據(jù)，在新的取樣數(shù)據(jù)到達(dá)時覆蓋最舊的數(shù)據(jù)。
一種用于保存特定數(shù)量的最后插入元素的快速緩沖。
高效的固定容量FIFO(先進(jìn)先出)或LIFO(后進(jìn)先出)隊列，當(dāng)隊列滿時刪除最舊的(即最早插入的)元素。

希望本文所述對大家的C++程序算法設(shè)計有所幫助。

您可能感興趣的文章: