循环队列.txt

数据结构循环队列的实现 实现用指针的删除查找功能 性能良好

/*循环队列*/
#include<iostream>
#include<assert.h>
using namespace std;
typedef int TypeData;
typedef struct Node{
 TypeData data;
 Node *next;
}Node;
class SeqQueue
{
 private:
  Node *front;
  Node *rear;

 public:
  SeqQueue();
  ~SeqQueue(){makeEmpty();};
  bool EnQueue(const TypeData& x);
  bool DeQueue(TypeData& x);
  bool getFront(TypeData& x);
  void makeEmpty();
  bool IsEmpty() {return (front==NULL)?true:false;}
  int getSize() const;
  void TranElement();
 
};

//=========类的实现=====================
SeqQueue::SeqQueue()
{
 rear=front=NULL;
}
void SeqQueue::makeEmpty()
{
 Node *p;
 while(front!=NULL)
 {
  p=front;
  front=front->next;
  delete p;
 }
}
bool SeqQueue::EnQueue(const TypeData& x)
{
 Node*newNode=new Node;
 newNode->data=x;
 newNode->next=NULL;
 if(front==NULL)
 {  
  //队首指针指向队首
   front=rear=newNode;
   if(front==NULL){cerr<<"分配错误！";return false;}
 }else
 {
  rear->next=newNode;
  if(rear->next==NULL){cerr<<"分配错误！";return false;}
  rear=rear->next;
 }
 return true;
}
bool SeqQueue::DeQueue(TypeData& x)
{
 if(front==NULL) return false;
 Node *delNode=new Node;
 delNode=front;
 x=delNode->data;
 front=front->next;
 delete delNode;
 return true;
}
bool SeqQueue::getFront(TypeData& x)
{
 if(front==NULL) return false;
 x=front->data;
 return true;
}
int SeqQueue::getSize() const
{
 int k=0;
 Node *p=front;
 while(p!=NULL){p=p->next;k++;}
 return k;
}
void SeqQueue::TranElement()
{
 Node *current=front;
 while(current!=NULL)
 {
  cout<<" "<<current->data;
  current=current->next;
 }
}
void main()
{
 int n,m,i,j,k;
 SeqQueue mylink;
 cout<<"构造循环队列list1,请确定数组元素个数:";cin>>n;
 cout<<"请输入元素:";
 for(i=0;i<n;i++){cin>>m;mylink.EnQueue(m);}
 cout<<"由队头到队尾的顺序为:"<<endl;
 mylink.TranElement();
 cout<<" 总共有"<<mylink.getSize()<<"个元素"<<endl;
 while(true)
 {
  cout<<"请输入你想添加的元素(若输入'0'不添加!): ";cin>>j;
  if(j!=0) mylink.EnQueue(j);
  if(j==0) break;
 }
 cout<<"现在由队头到队尾的顺序为:"<<endl;
 mylink.TranElement(); 
 cout<<" 总共有"<<mylink.getSize()<<"个元素"<<endl;

 while(true)
 {
  cout<<"是否删除队头元素(若输入'0'不删除;输入'1'则删除): ";cin>>k;
  if(mylink.IsEmpty()==true){cout<<"队列中已经没元素了!"; break;}
  if(k!=0){mylink.DeQueue(k);}
  if(k==0) break;
 }
 if(mylink.IsEmpty()!=true)
 {
  cout<<" 现在由栈顶到栈底的顺序为:"<<endl;
  mylink.TranElement();
 }
 cout<<endl;

}