第5篇 C++数据结构 -环形队列

2020-02-12 本文已影响0人铁甲万能狗

ss8.png

循环队列是一种线性数据结构，其中的操作是基于FIFO（先进先出）原理执行的，最后一个位置又连接回第一个位置以构成一个闭合的环形队列。也称为“环形缓冲区”。

在普通队列中，我们可以插入元素，直到队列变满。但是，一旦队列已满,再无法插入下一个元素。因为在环形队列里面有两个索引计数器，每次插入队列rear会递增1,每次出队操作,front索引会递增+1，那么会存在两种状态

空载:当front和rear计算器指向同一个元素级别的内存块,定义为空环,此时,你可能认为front=rear时是判断空环的状态,事实上这样做会对出问题的，因此我们使其front或rear重置为一个负数，例如-1就是表示空环状态。
满载:当rear计数器随着在入队操作递增逼近front计数器，见下图最后一个环的状态，
此时rear=size-1并且front=0，或者rear=front-1

环形状态

环形队列的常见操作

enque:在队列末端插入元素,但是我们在插入元素时候必须检测环形是否已满，这个检查逻辑很简单,分为两个步骤
- 首先检测是否环形队列已满载
```
bool is_full(){
    return (rear==size_1 && front==0) || rear==front-1
}
```
- 其次,如果队列就反馈一个错误信息表示环形队列已满，如果队列未满，我们就检测rear==size-1 && front!=0若为true，那么将rear重置为0，并且插入元素
deque:在环形队列首端移除元素
rear:返回队列末端的元素
front:返回队列首端的元素
is_full:队列是否满载
is_empty:队列是否空载

性能问题:

从内存角度考虑，既然环形队列经常作为一个事务处理的缓存区,那么缓存去必定有固有的内存空间，因此最好的实现形式是选择固定长度的数组，OK，我们看看下面的接口代码和前文基于链表实现的队列的类成员接口是一样的。但从空间开销来说，选择基于固定长度的数组有一个好处就是，空间开销会比基于单链表的实现更有优势。再者，enque和deque操作都是通过改变d_front和d_rear两个索引计数器来模拟的，因为数组的索引访问时间消耗是O(1)，因此环形队列的最佳实现形式就是固定长度的数组

接口文件

#ifndef __CIRCLE_QUEUE_HH__
#define __CIRCLE_QUEUE_HH__
#include <iostream>
#include <stdlib.h>

template <class T>
class CircleQueue
{
private:
    //内部元素队列指针
    long d_rear, d_front;

    size_t d_size;
    size_t d_maxsize;
    T *d_arr;

public:
    //默认构造函数
    CircleQueue();

    //自定义构造函数
    CircleQueue(size_t);

    //析构函数
    ~CircleQueue();

    //拷贝构造函数
    CircleQueue(const CircleQueue &);

    //移动构造函数
    CircleQueue(CircleQueue &&);

    //踢队操作
    T deque();

    //入队操作
    void enque(const T &);

    //获取尺寸
    size_t size() const;

    //查看队列首端元素
    T front() const;

    //查看队列末端元素
    T rear() const;

    //队列是否非空
    bool is_empty() const;

    //队列是否已满
    bool is_full() const;

    //返回队列已有数量
    const size_t size();

    //缓存
    const T *buffer();

    //打印队列
    template <class R>
    friend std::ostream &operator<<(std::ostream &, CircleQueue<R> &);
};
#endif

代码实现

#include "../headers/CircleQueue.hh"
#define DEFAULT_SIZE 15

template <class T>
CircleQueue<T>::CircleQueue()
{
    d_front = d_rear = -1;
    d_maxsize = DEFAULT_SIZE;
    d_size = 0;
    d_arr = new T[d_maxsize];
}

//构造函数
template <class T>
CircleQueue<T>::CircleQueue(size_t size)
{
    d_size = 0;
    d_maxsize = size;
    d_front = d_rear = -1;
    d_arr = new T[d_maxsize];
}

//析构函数
template <class T>
CircleQueue<T>::~CircleQueue()
{
    delete[] d_arr;
}

//检查环形队列是否为满载
template <class T>
bool CircleQueue<T>::is_full() const
{
    return (d_rear == d_maxsize - 1 && d_front == 0) || (d_rear == d_front - 1);
}

//判断环形队列是否为空
template <class T>
bool CircleQueue<T>::is_empty() const
{
    return d_front == -1 || d_rear == -1;
}

//入队操作
template <class T>
void CircleQueue<T>::enque(const T &value)
{
    if (is_full())
    {
        std::cout << "环形队列已满" << std::endl;
        return;
    }
    else if (d_front == -1)
    {
        d_rear = d_front = 0;
    }
    else if (d_rear == d_maxsize - 1 && d_front != 0)
    {
        d_rear = 0;
    }
    else
    {
        d_rear++;
    }
    d_arr[d_rear] = value;
    d_size++;
}

//踢队操作
template <class T>
T CircleQueue<T>::deque()
{
    if (is_empty())
    {
        std::cout << "环形队列为空!!" << std::endl;
        return T();
    }

    T data = d_arr[d_front];

    if (d_front == d_rear)
    {
        d_front = -1;
        d_rear = -1;
    }
    else if (d_front == d_size - 1)
    {
        d_front = 0;
    }
    else
    {
        d_front++;
    }
    d_size--;
    return data;
}

//获取队头部元素
template <class T>
T CircleQueue<T>::front() const
{
    return d_arr[d_front];
}

//获取队尾元素
template <class T>
T CircleQueue<T>::rear() const
{
    return d_arr[d_rear];
}

//获取队列尺寸
template <class T>
const size_t CircleQueue<T>::size()
{
    return d_size;
}

//获取队列内部的缓存指针
template <class T>
const T *CircleQueue<T>::buffer()
{
    return d_arr;
}

//遍历
template <class R>
std::ostream &operator<<(std::ostream &os, CircleQueue<R> &q)
{

    const R *buf = q.d_arr;

    if (q.d_front == -1)
    {
        os << "CircleQueue为空" << std::endl;
    }
    else if (q.d_rear >= q.d_front)
    {
        for (auto i = q.d_front; i <= q.d_rear; i++)
        {
            os << buf[i] << ",";
        }
    }
    else
    {
        for (auto i = q.d_front; i < q.d_size; i++)
        {
            os << buf[i] << ",";
        }

        for (auto i = 0; i <= q.d_rear; i++)
        {
            os << buf[i] << ",";
        }
    }
    os << std::endl;
    return os;
}

第5篇 C++数据结构 -环形队列

性能问题:

接口文件

代码实现

猜你喜欢

热点阅读