This action will force synchronization from cyberdash/数据结构(C++模板实现), which will overwrite any changes that you have made since you forked the repository, and can not be recovered!!!
Synchronous operation will process in the background and will refresh the page when finishing processing. Please be patient.
/*!* @file double_ended_queue.h* @author cyberdash@163.com(抖音: cyberdash_yuan)* @brief 循环双端队列* @version 0.2.1* @date 2023年06月03日*/#ifndef CYBER_DASH_DOUBLE_ENDED_QUEUE_H#define CYBER_DASH_DOUBLE_ENDED_QUEUE_H#include <cstdlib>#include <iostream>#include "queue.h"using namespace std;template<typename TData> class DoubleEndedQueue;template<typename TData> ostream& operator<<(ostream& os, const DoubleEndedQueue<TData>& circular_queue);/*!* @brief **双端队列*** @tparam TData 数据项类型模板参数*/template<typename TData>class DoubleEndedQueue {public:/*!* @brief **构造函数*** @param capacity 容量* @note* 构造函数* -------* -------** -------* capacity_使用参数capacity, front(队头索引)初始化为-1, rear(队尾索引)初始化为-1\n\n* mem_data_分配内存\n* **if** 内存分配失败 :\n*   抛出bad_alloc()\n*** -------*/DoubleEndedQueue(int capacity = 20) : capacity_(capacity), front_(-1), rear_(-1) {this->mem_data_ = new TData[this->capacity_];if (!this->mem_data_) {throw bad_alloc();}}/*!* @brief **析构函数*** @note* 析构函数* -------* -------** -------* 释放mem_data_*** -------*/~DoubleEndedQueue() { delete[] this->mem_data_; }// 队尾入队bool PushBack(const TData& data);// 队头入队bool PushFront(const TData& data);// 队头出队(保存数据)bool PopFront(TData& data);// 队头出队(不保存数据)bool PopFront();// 队尾出队(保存数据)bool PopBack(TData& data);// 队尾出队bool PopBack();// 获取队头数据bool Front(TData& data) const;// 获取队尾数据bool Rear(TData& data) const;// 判断是否空队bool IsEmpty() const;// 判断是否满队bool IsFull() const;// 获取长度int Length() const;// 清空队列void Clear();// 重载<<(打印队列)friend ostream& operator<< <>(ostream& os, const DoubleEndedQueue<TData>& seq_queue);private:TData* mem_data_; //!< **元素数组**int capacity_; //!< **容量**int front_; //!< **队头索引**int rear_; //!< **队尾索引**};/*!* @brief **队尾入队*** @tparam TData 数据项类型模板参数* @param data 数据项值* @return 执行结果* @note* 队尾入队* -------* -------** -------* + **1 合法性判断**\n\n* **if** 容量已满 :\n*   返回false\n\n* + **2 空队的特殊处理**\n\n* **if** 空队 :\n*   front_置为0\n\n* + **3 入队操作**\n\n* rear_值更新\n* mem_data_[rear_]的值设为参数data\n\n* + **4 退出函数**\n\n* 返回true\n*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::PushBack(const TData& data) {// ---------- 1 合法性判断 ----------if (IsFull()) { // if 容量已满return false; // 返回false}// ---------- 2 空队的特殊处理 ----------if (Length() == 0) { // if 空队this->front_ = 0; // front_置为0}// ---------- 3 入队操作 ----------this->rear_ = (this->rear_ + 1 + this->capacity_) % this->capacity_; // rear_值更新this->mem_data_[this->rear_] = data; // mem_data_[rear_]的值设为参数data// ---------- 4 退出函数 ----------return true; // 返回true}/*!* @brief **队头入队*** @tparam TData 数据项类型模板参数* @param data 数据项值* @return 执行结果* @note* 队头入队* -------* -------** -------* + **1 合法性判断**\n\n* **if** 容量已满 :\n*   返回false\n\n* + **2 空队的特殊处理**\n\n* **if** 空队 :\n*   rear_置为0\n\n* + **3 入队操作**\n\n* front_值更新\n* mem_data_[front_]的值设为参数data\n\n* + **4 退出函数**\n\n* 返回true\n*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::PushFront(const TData& data) {// ---------- 1 合法性判断 ----------if (IsFull()) { // if 容量已满return false; // 返回false}// ---------- 2 空队的特殊处理 ----------if (Length() == 0) { // if 空队this->rear_ = 0; // rear_置为0}// ---------- 3 入队操作 ----------this->front_ = (this->front_ - 1 + this->capacity_) % this->capacity_; // front_值更新this->mem_data_[this->front_] = data; // mem_data_[front_]的值设为参数data// ---------- 4 退出函数 ----------return true; // 返回true}/*!* @brief **队头出队(保存数据)*** @tparam TData 数据项类型模板参数* @param data 数据项保存变量* @return 执行结果* @note* 队头出队(保存数据)* ---------------* ---------------** ---------------* + **1 合法性判断**\n\n* **if** 空队:\n*   返回false\n\n* + **2 取队尾值和索引处理**\n\n* mem_data_[front_]赋给参数data\n\n* **if** 队列长度为1 :\n*   front_置为-1\n*   rear_置为-1\n* **else**\n* front_值更新\n\n* + **3 退出函数**\n\n* 返回true\n*** ---------------*/template<typename TData>bool DoubleEndedQueue<TData>::PopFront(TData& data) {// ---------- 1 合法性判断 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 取队尾值和索引处理 ----------data = this->mem_data_[this->front_]; // mem_data_[front_]赋给参数dataif (Length() == 1) { // if 队列长度为1this->front_ = -1; // front_置为-1this->rear_ = -1; // rear_置为-1} else {front_ = (front_ + 1 + capacity_) % capacity_; // front_值更新}// ---------- 3 退出函数 ----------return true; // 返回true}/*!* @brief **队头出队*** @tparam TData 数据项类型模板参数* @return 执行结果* @note* 队头出队* -------* -------** -------* + **1 合法性判断**\n\n* **if** 空队:\n*   返回false\n\n* + **2 索引处理**\n\n* **if** 队列长度为1 :\n*   front_置为-1\n*   rear_置为-1\n* **else**\n* front_值更新\n\n* + **3 退出函数**\n\n* 返回true\n*** ---------------*/template<typename TData>bool DoubleEndedQueue<TData>::PopFront() {// ---------- 1 合法性判断 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 长度为1的队列的特殊处理 ----------if (Length() == 1) { // if 队列长度为1this->front_ = -1; // front_置为-1this->rear_ = -1; // rear_置为-1} else {front_ = (front_ + 1 + capacity_) % capacity_; // front_值更新}// ---------- 3 退出函数 ----------return true; // 返回true}/*!* @brief **队尾出队(保存数据)*** @tparam TData 数据项类型模板参数* @return 执行结果* @note* 队尾出队(保存数据)* ---------------* ---------------** ---------------* + **1 合法性判断**\n\n* **if** 空队 :\n*   返回false\n\n* + **2 取队尾值和索引处理**\n\n* mem_data_[rear_]赋给参数data\n\n* **if** 队列长度为1 :\n*   front设置为-1\n*   rear设置为-1\n* **else**\n*   rear_设置为(rear_ - 1 + capacity_) % capacity_\n\n* + **3 退出函数**\n\n* 返回true\n*** ---------------*/template<typename TData>bool DoubleEndedQueue<TData>::PopBack(TData& data) {// ---------- 1 合法性判断 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 索引处理 ----------data = this->mem_data_[this->rear_]; // mem_data_[rear_]赋给参数dataif (Length() == 1) { // if 队列长度为1this->front_ = -1; // front设为-1this->rear_ = -1; // rear设为-1} else {rear_ = (rear_ - 1 + capacity_) % capacity_; // rear_设置为(rear_ - 1 + capacity_) % capacity_}// ---------- 3 退出函数 ----------return true; // 返回true}/*!* @brief **队尾出队*** @tparam TData 数据项类型模板参数* @return 执行结果* @note* 队尾出队* -------* -------** -------* + **1 合法性判断**\n\n* **if** 空队 :\n*   返回false\n\n* + **2 索引处理**\n\n* **if** 队列长度为1 :\n*   front设置为-1\n*   rear设置为-1\n* **else**\n*   rear_设置为(rear_ - 1 + capacity_) % capacity_\n\n* + **3 退出函数**\n\n* 返回true\n*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::PopBack() {// ---------- 1 合法性判断 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 索引处理 ----------if (Length() == 1) { // if 队列长度为1this->front_ = -1; // front设为-1this->rear_ = -1; // rear设为-1} else {rear_ = (rear_ - 1 + capacity_) % capacity_; // rear_设置为(rear_ - 1 + capacity_) % capacity_}// ---------- 3 退出函数 ----------return true; // 返回true}/*!* @brief **获取队头数据*** @tparam TData 数据项类型模板参数* @param data 数据项保存变量* @return 执行结果* @note* 获取队头数据* ----------* ----------** ----------* + **1 非法情况处理**\n\n* **if** 空队 :\n*   返回false\n\n* + **2 取队头数据**\n\n* mem_data_[front_]赋给data\n\n* + **3 退出函数**\n\n* 返回false\n*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::Front(TData& data) const {// ---------- 1 非法情况处理 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 取队头数据 ----------data = this->mem_data_[front_]; // mem_data_[front_]赋给data// ---------- 3 退出函数 ----------return true; // 返回false}/*!* @brief **获取队尾数据*** @tparam TData 数据项类型模板参数* @param data 数据项保存变量* @return 执行结果* @note* 获取队尾数据* ----------* ----------** ----------* + **1 非法操作处理**\n\n* **if** 空队 :\n*   返回false\n\n* + **2 获取队尾数据**\n\n* mem_data_[rear_]赋给参数data\n\n* + **3 退出函数**\n\n* 返回true\n*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::Rear(TData& data) const {// ---------- 1 非法操作处理 ----------if (IsEmpty()) { // if 空队return false; // 返回false}// ---------- 2 获取队尾数据 ----------data = this->mem_data_[rear_]; // mem_data_[rear_]赋给参数data// ---------- 3 退出函数 ----------return true; // 返回true}/*!* @brief **判断是否为空*** @tparam TData 数据项类型模板参数* @return 是否为空* @note* 判断是否为空* ----------* ----------** ----------* 返回Length() == 0*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::IsEmpty() const {return this->Length() == 0;}/*!* @brief **判断队列是否为空*** @tparam TData 数据项类型模板参数* @return 是否为空* @note* 判断队列是否为空* -------------* -------------** -------------* 返回this->front_ == NULL*** -------*/template<typename TData>bool DoubleEndedQueue<TData>::IsFull() const {return this->Length() == capacity_;}/*!* @brief **获取队列长度*** @tparam TData 数据项类型模板参数* @return 队列长度* @note* 获取队列长度* ----------* ----------** ----------* 初始化count(队列结点数量)为0\n\n* **for loop** cur指向front_; cur != NULL; cur指向自身next :\n*   count加1\n\n* 返回count\n*** -------*/template<typename TData>int DoubleEndedQueue<TData>::Length() const {// ---------- 1 空队情况 ----------if (this->rear_ == -1 && this->front_ == -1) { // if rear_和front_都为-1return 0; // 返回0}// ---------- 2 非空队情况 ----------return (rear_ - front_ + 1 + capacity_) % capacity_; // 返回(rear_ - front_ + 1 + capacity_) % capacity_}/*!* @brief **清空*** @tparam TData 数据项类型模板参数* @note* 清空* ---* ---** ---* rear_和front_都设为-1*** -------*/template<typename TData>void DoubleEndedQueue<TData>::Clear() {this->rear_ = -1;this->front_ = -1;}/*!* @brief **重载<<*** @tparam TData 数据项类型模板参数* @param os 输出流* @param circular_queue 循环队列* @return 输出流(引用)* @note* 重载<<* -----* -----** -----* 打印队列长度\n\n* **for loop** 遍历队列: \n*   获取当前结点的数组索引\n*   打印当前结点的数据项\n\n* 返回os\n*** -------*/template<typename TData>ostream& operator<<(ostream& os, const DoubleEndedQueue<TData>& circular_queue) {os << "The size of link queue: " << circular_queue.Length() << endl; // 打印队列长度for (int i = 0; i < circular_queue.Length(); i++) { // for loop 遍历队列int actual_index = (circular_queue.front_ + i + circular_queue.capacity_) % circular_queue.capacity_; // 获取当前结点的数组索引os << circular_queue.mem_data_[actual_index] << endl; // 打印当前结点数据项}return os; // 返回os}#endif // CYBER_DASH_DOUBLE_ENDED_QUEUE_H
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。