循環(huán)隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，其中的操作是基于FIFO（先進(jìn)先出）原理執(zhí)行的，最后一個(gè)位置又連接回第一個(gè)位置以構(gòu)成一個(gè)閉合的環(huán)形隊(duì)列。 也稱為“環(huán)形緩沖區(qū)”承绸。
在普通隊(duì)列中，我們可以插入元素挣轨，直到隊(duì)列變滿军熏。 但是，一旦隊(duì)列已滿,再無法插入下一個(gè)元素卷扮。因?yàn)樵诃h(huán)形隊(duì)列里面有兩個(gè)索引計(jì)數(shù)器荡澎，每次插入隊(duì)列rear會(huì)遞增1,每次出隊(duì)操作,front索引會(huì)遞增+1，那么會(huì)存在兩種狀態(tài)
- 空載:當(dāng)front和rear計(jì)算器指向同一個(gè)元素級(jí)別的內(nèi)存塊,定義為空環(huán),此時(shí),你可能認(rèn)為front=rear時(shí)是判斷空環(huán)的狀態(tài),事實(shí)上這樣做會(huì)對(duì)出問題的晤锹，因此我們使其front或rear重置為一個(gè)負(fù)數(shù)摩幔，例如-1就是表示空環(huán)狀態(tài)。
- 滿載:當(dāng)rear計(jì)數(shù)器隨著在入隊(duì)操作遞增逼近front計(jì)數(shù)器鞭铆，見下圖最后一個(gè)環(huán)的狀態(tài)或衡，
此時(shí)rear=size-1并且front=0，或者rear=front-1
環(huán)形隊(duì)列的常見操作
-
enque:在隊(duì)列末端插入元素,但是我們?cè)诓迦朐貢r(shí)候必須檢測環(huán)形是否已滿车遂，這個(gè)檢查邏輯很簡單,分為兩個(gè)步驟
- 首先檢測是否環(huán)形隊(duì)列已滿載
bool is_full(){ return (rear==size_1 && front==0) || rear==front-1 }- 其次,如果隊(duì)列就反饋一個(gè)錯(cuò)誤信息表示環(huán)形隊(duì)列已滿封断，如果隊(duì)列未滿，我們就檢測rear==size-1 && front!=0若為true舶担，那么將rear重置為0澄港，并且插入元素
deque:在環(huán)形隊(duì)列首端移除元素
rear:返回隊(duì)列末端的元素
front:返回隊(duì)列首端的元素
is_full:隊(duì)列是否滿載
is_empty:隊(duì)列是否空載
性能問題:
從內(nèi)存角度考慮，既然環(huán)形隊(duì)列經(jīng)常作為一個(gè)事務(wù)處理的緩存區(qū),那么緩存去必定有固有的內(nèi)存空間柄沮，因此最好的實(shí)現(xiàn)形式是選擇固定長度的數(shù)組回梧，OK废岂，我們看看下面的接口代碼和前文基于鏈表實(shí)現(xiàn)的隊(duì)列的類成員接口是一樣的。但從空間開銷來說狱意，選擇基于固定長度的數(shù)組有一個(gè)好處就是湖苞，空間開銷會(huì)比基于單鏈表的實(shí)現(xiàn)更有優(yōu)勢。再者详囤，enque和deque操作都是通過改變d_front和d_rear兩個(gè)索引計(jì)數(shù)器來模擬的财骨，因?yàn)閿?shù)組的索引訪問時(shí)間消耗是O(1)，因此環(huán)形隊(duì)列的最佳實(shí)現(xiàn)形式就是固定長度的數(shù)組
接口文件
#ifndef __CIRCLE_QUEUE_HH__
#define __CIRCLE_QUEUE_HH__
#include <iostream>
#include <stdlib.h>
template <class T>
class CircleQueue
{
private:
//內(nèi)部元素隊(duì)列指針
long d_rear, d_front;
size_t d_size;
size_t d_maxsize;
T *d_arr;
public:
//默認(rèn)構(gòu)造函數(shù)
CircleQueue();
//自定義構(gòu)造函數(shù)
CircleQueue(size_t);
//析構(gòu)函數(shù)
~CircleQueue();
//拷貝構(gòu)造函數(shù)
CircleQueue(const CircleQueue &);
//移動(dòng)構(gòu)造函數(shù)
CircleQueue(CircleQueue &&);
//踢隊(duì)操作
T deque();
//入隊(duì)操作
void enque(const T &);
//獲取尺寸
size_t size() const;
//查看隊(duì)列首端元素
T front() const;
//查看隊(duì)列末端元素
T rear() const;
//隊(duì)列是否非空
bool is_empty() const;
//隊(duì)列是否已滿
bool is_full() const;
//返回隊(duì)列已有數(shù)量
const size_t size();
//緩存
const T *buffer();
//打印隊(duì)列
template <class R>
friend std::ostream &operator<<(std::ostream &, CircleQueue<R> &);
};
#endif
代碼實(shí)現(xiàn)
#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];
}
//構(gòu)造函數(shù)
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];
}
//析構(gòu)函數(shù)
template <class T>
CircleQueue<T>::~CircleQueue()
{
delete[] d_arr;
}
//檢查環(huán)形隊(duì)列是否為滿載
template <class T>
bool CircleQueue<T>::is_full() const
{
return (d_rear == d_maxsize - 1 && d_front == 0) || (d_rear == d_front - 1);
}
//判斷環(huán)形隊(duì)列是否為空
template <class T>
bool CircleQueue<T>::is_empty() const
{
return d_front == -1 || d_rear == -1;
}
//入隊(duì)操作
template <class T>
void CircleQueue<T>::enque(const T &value)
{
if (is_full())
{
std::cout << "環(huán)形隊(duì)列已滿" << 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++;
}
//踢隊(duì)操作
template <class T>
T CircleQueue<T>::deque()
{
if (is_empty())
{
std::cout << "環(huán)形隊(duì)列為空!!" << 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;
}
//獲取隊(duì)頭部元素
template <class T>
T CircleQueue<T>::front() const
{
return d_arr[d_front];
}
//獲取隊(duì)尾元素
template <class T>
T CircleQueue<T>::rear() const
{
return d_arr[d_rear];
}
//獲取隊(duì)列尺寸
template <class T>
const size_t CircleQueue<T>::size()
{
return d_size;
}
//獲取隊(duì)列內(nèi)部的緩存指針
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;
}
