C/C++ code
7.顺序队列
SeqQueue.h
template<typename Type> class SeqQueue{
public:
SeqQueue(int sz):m_nrear(0),m_nfront(0),m_ncount(0),m_nMaxSize(sz){
m_pelements=new Type[sz];
if(m_pelements==NULL){
cout<<"Application Error!"<<endl;
exit(1);
}
}
~SeqQueue(){
delete[] m_pelements;
}
void MakeEmpty(); //make the queue empty
bool IsEmpty();
bool IsFull();
bool Append(const Type item); //insert data
Type Delete(); //delete data
Type Get(); //get data
void Print(); //print the queue
private:
int m_nrear;
int m_nfront;
int m_ncount;
int m_nMaxSize;
Type *m_pelements;
};
template<typename Type> void SeqQueue<Type>::MakeEmpty(){
this->m_ncount=0;
this->m_nfront=0;
this->m_nrear=0;
}
template<typename Type> bool SeqQueue<Type>::IsEmpty(){
return m_ncount==0;
}
template<typename Type> bool SeqQueue<Type>::IsFull(){
return m_ncount==m_nMaxSize;
}
template<typename Type> bool SeqQueue<Type>::Append(const Type item){
if(IsFull()){
cout<<"The queue is full!"<<endl;
return 0;
}
m_pelements[m_nrear]=item;
m_nrear=(m_nrear+1)%m_nMaxSize;
m_ncount++;
return 1;
}
template<typename Type> Type SeqQueue<Type>::Delete(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
Type temp=m_pelements[m_nfront];
m_nfront=(m_nfront+1)%m_nMaxSize;
m_ncount--;
return temp;
}
template<typename Type> Type SeqQueue<Type>::Get(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
return m_pelements[m_nfront];
}
template<typename Type> void SeqQueue<Type>::Print(){
cout<<"front";
for(int i=0;i<m_ncount;i++){
cout<<"--->"<<m_pelements[(m_nfront+i+m_nMaxSize)%m_nMaxSize];
}
cout<<"--->rear"<<endl<<endl<<endl;
}
Test.cpp
#include <iostream>
using namespace std;
#include "SeqQueue.h"
int main(){
SeqQueue<int> queue(10);
int init[10]={1,6,9,0,2,5,8,3,7,4};
for(int i=0;i<5;i++){
queue.Append(init[i]);
}
queue.Print();
cout<<queue.Delete()<<endl;
queue.Print();
for(int i=5;i<10;i++){
queue.Append(init[i]);
}
queue.Print();
cout<<queue.Get()<<endl;
queue.MakeEmpty();
queue.Print();
queue.Append(1);
queue.Print();
return 0;
}
8、链式队列
QueueNode.h
template<typename Type> class LinkQueue;
template<typename Type> class QueueNode{
private:
friend class LinkQueue<Type>;
QueueNode(const Type item,QueueNode<Type> *next=NULL)
:m_data(item),m_pnext(next){}
private:
Type m_data;
QueueNode<Type> *m_pnext;
};
LinkQueue.h
#include "QueueNode.h"
template<typename Type> class LinkQueue{
public:
LinkQueue():m_prear(NULL),m_pfront(NULL){}
~LinkQueue(){
MakeEmpty();
}
void Append(const Type item); //insert data
Type Delete(); //delete data
Type GetFront(); //get data
void MakeEmpty(); //make the queue empty
void Print(); //print the queue
bool IsEmpty() const{
return m_pfront==NULL;
}
private:
QueueNode<Type> *m_prear,*m_pfront;
};
template<typename Type> void LinkQueue<Type>::MakeEmpty(){
QueueNode<Type> *pdel;
while(m_pfront){
pdel=m_pfront;
m_pfront=m_pfront->m_pnext;
delete pdel;
}
}
template<typename Type> void LinkQueue<Type>::Append(const Type item){
if(m_pfront==NULL){
m_pfront=m_prear=new QueueNode<Type>(item);
}
else{
m_prear=m_prear->m_pnext=new QueueNode<Type>(item);
}
}
template<typename Type> Type LinkQueue<Type>::Delete(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
QueueNode<Type> *pdel=m_pfront;
Type temp=m_pfront->m_data;
m_pfront=m_pfront->m_pnext;
delete pdel;
return temp;
}
template<typename Type> Type LinkQueue<Type>::GetFront(){
if(IsEmpty()){
cout<<"There is no element!"<<endl;
exit(1);
}
return m_pfront->m_data;
}
template<typename Type> void LinkQueue<Type>::Print(){
QueueNode<Type> *pmove=m_pfront;
cout<<"front";
while(pmove){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->rear"<<endl<<endl<<endl;
}
Test.cpp
#include <iostream>
using namespace std;
#include "LinkQueue.h"
int main(){
LinkQueue<int> queue;
int init[10]={1,3,6,8,9,2,0,5,4,7};
for(int i=0;i<10;i++){
queue.Append(init[i]);
}
queue.Print();
queue.Delete();
queue.Print();
cout<<queue.GetFront()<<endl;
queue.Print();
queue.MakeEmpty();
queue.Print();
queue.Delete();
return 0;
}
9、优先级队列
QueueNode.h
template<typename Type,typename Cmp> class PriorityQueue;
template<typename Type,typename Cmp> class QueueNode{
private:
friend class PriorityQueue<Type,Cmp>;
QueueNode(const Type item,QueueNode<Type,Cmp> *next=NULL)
:m_data(item),m_pnext(next){}
private:
Type m_data;
QueueNode<Type,Cmp> *m_pnext;
};
Compare.h
template<typename Type> class Compare{ //处理一般比较大小
public:
static bool lt(Type item1,Type item2);
};
template<typename Type> bool Compare<Type>::lt(Type item1, Type item2){
return item1<item2;
}
struct SpecialData{
friend ostream& operator<<(ostream& ,SpecialData &);
int m_ntenor;
int m_npir;
};
ostream& operator<<(ostream& os,SpecialData &out){
os<<out.m_ntenor<<" "<<out.m_npir;
return os;
}
class SpecialCmp{ //处理特殊比较大小,用户可添加适当的类
public:
static bool lt(SpecialData item1,SpecialData item2);
};
bool SpecialCmp::lt(SpecialData item1, SpecialData item2){
return item1.m_npir<item2.m_npir;
}
PriorityQueue.h
#include "QueueNode.h"
#include "Compare.h"
template<typename Type,typename Cmp> class PriorityQueue{ //Cmp is Designed for compare
public:
PriorityQueue():m_prear(NULL),m_pfront(NULL){}
~PriorityQueue(){
MakeEmpty();
}
void MakeEmpty(); //make the queue empty
void Append(const Type item); //insert data
Type Delete(); //delete data
Type GetFront(); //get data
void Print(); //print the queue
bool IsEmpty() const{
return m_pfront==NULL;
}
private:
QueueNode<Type,Cmp> *m_prear,*m_pfront;
};
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::MakeEmpty(){
QueueNode<Type,Cmp> *pdel;
while(m_pfront){
pdel=m_pfront;
m_pfront=m_pfront->m_pnext;
delete pdel;
}
}
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Append(const Type item){
if(m_pfront==NULL){
m_pfront=m_prear=new QueueNode<Type,Cmp>(item);
}
else{
m_prear=m_prear->m_pnext=new QueueNode<Type,Cmp>(item);
}
}
template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::Delete(){
if(IsEmpty()){
cout<<"There is no elements!"<<endl;
exit(1);
}
QueueNode<Type,Cmp> *pdel=m_pfront,*pmove=m_pfront;
while(pmove->m_pnext){ //get the minimize priority's data
//cmp:: lt is used for compare the two data, if the front one
// is less than the back, then return 1
if(Cmp::lt(pmove->m_pnext->m_data,pdel->m_pnext->m_data)){
pdel=pmove;
}
pmove=pmove->m_pnext;
}
pmove=pdel;
pdel=pdel->m_pnext;
pmove->m_pnext=pdel->m_pnext;
Type temp=pdel->m_data;
delete pdel;
return temp;
}
template<typename Type,typename Cmp> Type PriorityQueue<Type,Cmp>::GetFront(){
if(IsEmpty()){
cout<<"There is no elements!"<<endl;
exit(1);
}
QueueNode<Type,Cmp> *pdel=m_pfront,*pmove=m_pfront->m_pnext;
while(pmove){ //get the minimize priority's data
if(Cmp::lt(pmove->m_data,pdel->m_data)){
pdel=pmove;
}
pmove=pmove->m_pnext;
}
return pdel->m_data;
}
template<typename Type,typename Cmp> void PriorityQueue<Type,Cmp>::Print(){
QueueNode<Type,Cmp> *pmove=m_pfront;
cout<<"front";
while(pmove){
cout<<"--->"<<pmove->m_data;
pmove=pmove->m_pnext;
}
cout<<"--->rear"<<endl<<endl<<endl;
}
Test.cpp
#include <iostream>
#include <cstdlib>
using namespace std;
#include "PriorityQueue.h"
int main(){
PriorityQueue<int,Compare<int> > queue;
int init[10]={1,9,3,5,0,8,2,4,6,7};
for(int i=0;i<10;i++){
queue.Append(init[i]);
}
queue.Print();
queue.Delete();
queue.Print();
system("pause");
system("cls");
PriorityQueue<SpecialData,SpecialCmp> spe_queue;
int init2[5][2]={{34,2},{64,1},{18,3},{24,2},{55,4}};
SpecialData data[5];
for(int i=0;i<5;i++){
data[i].m_npir=init2[i][1];
data[i].m_ntenor=init2[i][0];
}
for(int i=0;i<5;i++){
spe_queue.Append(data[i]);
}
spe_queue.Print();
cout<<spe_queue.GetFront()<<endl<<endl;
spe_queue.Delete();
spe_queue.Print();
return 0;
}
