快捷導(dǎo)航

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

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

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

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

前段時(shí)間在知乎上看到這樣一個(gè)小題目：

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

constructor: 初始化隊(duì)列

enqueue:入隊(duì)

dequeue:出隊(duì)

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

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

基本實(shí)現(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

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

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

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

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

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

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

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

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

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

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

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

您可能感興趣的文章: