循环队列和链式队列（C++实现）
2024-10-16 16:37:58
循环队列：
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=){
front=rear=;
maxSize=sz;
element=new T[maxSize];
}
~SeqQueue(){
delete[] element;
}
bool EnQueue(const T& x){//入队
if(isFull()) return false;
element[rear]=x;
rear=(rear+)%maxSize;
return true;
}
bool DeQueue(T& x){//出队
if(isEmpty()) return false;
x=element[front];
front=(front+)%maxSize;
return true;
}
bool getFront(T& x){//获取队首元素
if(isEmpty()) return false;
x=element[front];
return true;
}
void makeEmpty(){//队列置空
front=rear=;
}
bool isEmpty()const{//判断队列是否为空
return (rear==front)?true:false;
}
bool isFull()const{//队列是否为满
return ((rear+)%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 :
cin>>x;
sq->EnQueue(x);
break;
case :
sq->getFront(x);
cout<<x<<endl;
break;
case :
sq->DeQueue(x);
break;
case :
sq->makeEmpty();
break;
case :
x=sq->getSize();
cout<<x<<endl;
break;
default:
exit();
}
}
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 ;
}
之后是链式队列，实现类代码和测试代码如下：
#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=;
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 :
cin>>x;
lq->enQueue(x);
break;
case :
lq->getFront(x);
cout<<x<<endl;
break;
case :
lq->deQueue(x);
break;
case :
lq->makeEmpty();
break;
case :
x=lq->getSize();
cout<<x<<endl;
break;
default:
exit();
}
}
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 ;
}
最新文章
- knn-伪代码与实现过程
- iptables四个表与五个链间的处理关系
- C语言实现四则运算
- MCMC: The Metropolis Sampler
- Facebook 网络模拟工具 ATC部署及使用
- java-io-FileReader和FileWriter类
- hadoop输入格式(InputFormat)
- C#：WebBrowser控件设置代理IP访问网站【附源码】
- .net,微软，薪资及其他
- PO_PO系列 - 安全文件管控管理分析（案例）
- centos 升级GCC/G++
- Nginx - HTTP Configuration, the Location Block
- Regex阅读笔记(二)之环视
- 2015 asia xian regional F Color (容斥 + 组合数学)
- easyUI progressbar组件
- jacascript document对象
- 20180328 Redis和MSMQ
- html5-新增表单的小结details summary
- Codeforces 808G Anthem of Berland - KMP - 动态规划
- 【洛谷】【单调队列】P2032 扫描