C++实现循环队列和链式队列的示例
更新时间:2020年4月25日 17:29 点击:1268
循环队列:
1.循环队列中判断队空的方法是判断front==rear,队满的方法是判断front=(rear+1)%maxSize。(我曾经想过为什么不用一个length表示队长,当length==maxSize时队满)原因就是,在频繁的队列操作中,多出一个变量会大量的增加执行时间,所以不如浪费一个数组空间来得划算。
2.用单链表表示的链式队列特别适合于数据元素变动较大的情形,而且不存在溢出的情况。
template<class T> class SeqQueue{ protected: T *element; int front,rear; int maxSize; public: SeqQueue(int sz=10){ front=rear=0; maxSize=sz; element=new T[maxSize]; } ~SeqQueue(){ delete[] element; } bool EnQueue(const T& x){//入队 if(isFull()) return false; element[rear]=x; rear=(rear+1)%maxSize; return true; } bool DeQueue(T& x){//出队 if(isEmpty()) return false; x=element[front]; front=(front+1)%maxSize; return true; } bool getFront(T& x){//获取队首元素 if(isEmpty()) return false; x=element[front]; return true; } void makeEmpty(){//队列置空 front=rear=0; } bool isEmpty()const{//判断队列是否为空 return (rear==front)?true:false; } bool isFull()const{//队列是否为满 return ((rear+1)%maxSize==front)?true:false; } int getSize()const{ return (rear-front+maxSize)%maxSize; } };
测试代码如下:
void menu(){ cout<<"1.入队"<<endl; cout<<"2.获取队首元素"<<endl; cout<<"3.出队"<<endl; cout<<"4.队列置空"<<endl; cout<<"5.获取队中元素数量"<<endl; cout<<"6.退出"<<endl; } void function(int num,SeqQueue<int> *sq){ switch(num){ int x; case 1: cin>>x; sq->EnQueue(x); break; case 2: sq->getFront(x); cout<<x<<endl; break; case 3: sq->DeQueue(x); break; case 4: sq->makeEmpty(); break; case 5: x=sq->getSize(); cout<<x<<endl; break; default: exit(1); } } int main(int argc, char** argv) { SeqQueue<int> *sq=new SeqQueue<int>; int num; while(true){ menu(); cin>>num; function(num,sq); } delete sq; return 0; }
之后是链式队列,实现类代码和测试代码如下:
#include <iostream> using namespace std; template<class T> struct LinkNode{ T data; LinkNode<T> *link; LinkNode(T& x,LinkNode<T> *l=NULL){ data=x; link=l; } }; template<class T> class LinkedQueue{ protected: LinkNode<T> *front,*rear; public: LinkedQueue(){ front=rear=NULL; } ~LinkedQueue(){ makeEmpty(); } bool enQueue(T& x){ if(front==NULL) front=rear=new LinkNode<T>(x); else{ rear=rear->link=new LinkNode<T>(x); } return true; } bool deQueue(T& x){ if(isEmpty()) return false; LinkNode<T> *p=front; x=front->data; front=front->link; delete p; return true; } bool getFront(T& x)const{ if(isEmpty()) return false; x=front->data; return true; } void makeEmpty(){ LinkNode<T> *p; while(front!=NULL){ p=front; front=front->link; delete p; } } bool isEmpty()const{ return (front==NULL)?true:false; } int getSize()const{ LinkNode<T> *p; int count=0; p=front; while(p!=NULL){ count++; p=p->link; } return count; } }; void menu(){ cout<<"1.入队"<<endl; cout<<"2.获取队首元素"<<endl; cout<<"3.出队"<<endl; cout<<"4.队列置空"<<endl; cout<<"5.获取队中元素数量"<<endl; cout<<"6.退出"<<endl; } void function(int num,LinkedQueue<int> *lq){ switch(num){ int x; case 1: cin>>x; lq->enQueue(x); break; case 2: lq->getFront(x); cout<<x<<endl; break; case 3: lq->deQueue(x); break; case 4: lq->makeEmpty(); break; case 5: x=lq->getSize(); cout<<x<<endl; break; default: exit(1); } } int main(int argc, char** argv) { LinkedQueue<int> *lq=new LinkedQueue<int>; int num; while(true){ menu(); cin>>num; function(num,lq); } delete lq; return 0; }
以上这篇C++实现循环队列和链式队列的示例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
下一篇: 浅谈C++模板元编程
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 在本篇内容里小编给大家分享了关于C++实现递归函数的教学步骤,需要的朋友跟着参考下。...2020-04-25