循环队列实现(C++) Ring Buffer
2023-09-11 14:17:25 时间
循环队列:队列有着先入先出的特性。但是对于队列如果删除队头以后剩下的空间将不会被释放,又由于队列只能由队尾插入这就导致
被删除部分的空间被浪费。解决这个问题就是循环队列。循环队列顾名思义就是将队列串起来形成一个类似与环的结构。如图所示。对照着图很容易理解:
对于原来队列里的操作自然有不同的地方:
1.判断满:循环队列的满不再是rear=front 而是改成(rear-front+maxn)%maxn。
2.入队操作: data[rear] = x; rear = (rear+1)%maxn;
总体思想就是不让rear和front的值超过maxn的大小。于是就在rear和front自增时候模maxn。
其实就是Ring Buffer
空队时指针(下标)front和rear在一起都指向队前方,当有元素进队,则rear后移;有元素出队,则front后移,最后,开始时分配给队的前端不再被利用。(查看动画演示)
为了充分利用队列,顺序队列总是做成一个逻辑上的循环队列。
注意:空队时rear等于front,满队时必须空一个位置。
#include <iostream> using namespace std; template <class T> class cycleQueue { private: unsigned int m_size; int m_front; int m_rear; T* m_data; public: cycleQueue(unsigned size) :m_size(size), m_front(0), m_rear(0) { m_data = new T[size]; } ~cycleQueue() { delete [] m_data; } bool isEmpty() { return m_front == m_rear; } bool isFull() { return m_front == (m_rear + 1)%m_size; } void push(T ele)throw(bad_exception) { if(isFull()) { throw bad_exception(); } m_data[m_rear] = ele; m_rear = (m_rear + 1)%m_size; } T pop() throw(bad_exception) { if(isEmpty()) { throw bad_exception(); } T tmp = m_data[m_front]; m_front = (m_front + 1)%m_size; return tmp; } }; int main() { cycleQueue<int> q(5); q.push(1); q.push(2); q.push(3); q.push(4); for (int i = 0; i < 4 ; i++) cout << q.pop() << endl; q.push(5); q.push(5); q.push(5); cout << q.pop() << endl; cout << q.pop() << endl; cout << q.pop() << endl; cout << q.pop() << endl; return 0; }
相关文章
- qt实现web服务器加载vue应用进行C++和html混合编程-连载【6】-企业级系统开发实战连载系列 -技术栈(vue、element-ui、qt、c++、sqlite)
- C/C++fflush(stdout)循环打印输出避免缓存区错误
- 利用OpenCV的函数threshold()实现双阈值二值化操作的C++代码
- Python中的枚举对象有什么用?怎样用内置函数enumerate()得到枚举对象?Python的for循环和C++的for循环有何区别?Python中for循环的本质是什么?
- 【c/c++】刷算法题时常用的函数手册 持续更新--
- C++第10周项目1参考——利用循环求和
- [C++]:万字超详细讲解多态以及多态的实现原理(面试的必考的c++考点)
- 《C++覆辙录》——1.5:对引用的认识误区
- 《C++游戏编程入门(第4版)》——2.7 使用do循环
- 《C++入门经典(第5版•修订版)》——6.4 for循环
- 《C和C++代码精粹》——1.10 操纵器
- 《C和C++代码精粹》——2.13 指向成员函数的指针
- 基于C++实现一个平面上的形状编辑程序【100010121】
- 设计Qt风格的C++API
- Linux环境下配置vscode的C/C++ 的make编译环境(编写makefile方式)代码Demo版
- C++开发人脸性别识别教程(7)——搭建MFC框架之界面绘制
- [C++] 反编译器
- C++和Java中枚举enum的用法
- 教外谈(5):C++ STL最全详解(下)
- C/C++ 装载问题