溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
循環隊列：
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++實現循環隊列和鏈式隊列的示例就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
