C++实现循环队列和链式队列的示例

2020-05-23 13:31:50

字体：大中小

来源：转载

供稿：网友

循环队列：

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++实现循环队列和链式队列的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持VEVB武林网。

上一篇：浅谈C++模板元编程

下一篇：c语言实现基数排序解析及代码示例