C++循環隊列實現模型

2020-01-26 15:11:05

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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、適用于實時和對性能有嚴格要求的應用程序。

還可以進一步擴展，當隊列滿的時候，從一端插入則覆蓋沖洗掉另一端的數據，這樣的一個模型可以應用于這些場合：