C++数据结构,用链表(链式结构)实现队列
浏览数:2518 

数据结构:队列结构特点
1.基本特征:先进先出

2.基本操作:从后端(rear)压入(push),从前端(front)弹出(pop)

3.实现要点:初始化空间、从后端指针压入,从前端指针弹出,判空(链表结构只需要判空,不考虑容量不足情况)

下面使用链表实现队列结构,那么成员变量就是front和rear两个节点结构的指针变量,front指向前端,rear指向后端

<span style="font-size:18px;">#include <iostream>
using namespace std;
class Queue{
public:
Queue(void):front(NULL),rear(NULL){}
~Queue(void){
 for(Node *p;front;front=p){
  p=p->next;
  delete front;
 }
}
void push(int data){
 Node *node=new Node(data);
 if(rear)
  rear->next=node;
 else//如果是第一个节点,那么需要把front也指向node
  front=node;
 rear=node;
}
int pop(){
 if(empty())
  throw UnderFlow();
 int pdata;
 Node *p=front;
 pdata=front->data;
 delete front;
 front=NULL;
 front=p->next;
 if(front==NULL)//如果删除的是最后一个节点,那么需要把rear也置为NULL
  rear=NULL;
 return pdata;
}
bool empty(){
 return rear==NULL && front==NULL;
}
private:
class UnderFlow:public exception{
public:
 const char* what() const throw(){
  return "下溢";
 }
};
class Node{
 public:
  Node(int pdata=0,Node *pnext=NULL):data(pdata),next(pnext){}
  ~Node(void){}
  int data;
  Node *next;
};
Node *front;//前端
Node *rear;//后端
};
int main(){
try{
 Queue q;
 for(int i=1;i<=10;++i){
  q.push(i);
 }
 while(!q.empty())
  cout<<q.pop()<<endl;
}
catch(exception& ex){
 cout << ex.what() << endl;
 return -1;
}
}</span>

联系管理员
 
 
 
 
 工作时间
周一至周五 :9:30-17:30
马上建站
会员登录
登录
我的资料
留言
回到顶部