这里用链表来存储队列，我下面的代码是通过自定义的一个结构体，用来做链队的数据类型
分析：
插入元素1，2，3，4
出队：
删除到最后，那么最后一个元素就变为了头结点：
链队：
1，有节点，用结构体来标识
typedef struct sNode{ //自定义的链队列节点
struct Node *n;
struct sNode *next;
};
2，链队的数据结构
typedef struct Linklist{ //定义链队列的数据结构
sNode *front;
sNode *rear;
};
3，初始化队列，构造一个空的队列，定义头结点
void Init_linklist(Linklist *&l){ //初始化栈队列
sNode *s=new sNode;
s->next=NULL; //头结点
l->front=s;
l->rear=s;
}
4，判断队列是否为空
int empty_queue(Linklist *&l){
if(sum==0){
return 1;
}else{
return 0;
}
}
5，进队
void en_queue(Linklist *&p,Node *&q){ //入队
sNode *s=new sNode;
s->n=q;
s->next=NULL;
p->rear->next=s;
p->rear=s;
sum++;
}
6，出队
Node* de_queue(Linklist *&p){ //出队
Node *s=p->front->next->n;
sNode *l=p->front;
p->front=l->next;
if(p->front==p->rear){
p->rear=p->front; //重新定义头结点，到结尾了
}
delete l;
sum--;
return s;
}
7，队列长度，我定义了一个sum全局变量，用来统计队列的长度，进队，我+1，出队，我-1，因为是链表，所以如果单纯的统计长度，需要遍历，所以定义一个全局变量，更方便
int ll_size(Linklist *&p){ //队列长度
return sum;
}
8，队首元素
Node* ll_front(Linklist *&p){ //队首元素
return p->front->next->n;
}
9，队尾元素
Node* ll_rear(Linklist *&p){ //队尾元素
return p->rear->n;
}
完整测试代码：
#include <iostream>
using namespace std;
typedef struct Node{ //测试的自定义的节点
int data;
struct Node *next;
};
typedef struct sNode{ //自定义的链队列节点
struct Node *n;
struct sNode *next;
};
typedef struct Linklist{
sNode *front;
sNode *rear;
};
int sum=0;//统计链队的长度
void Init_Node(Node *&p){ //初始化测试队列
Node *s=p;
p->next=NULL;
}
int insert_Node(Node *&p,int i,int m){ //插入测试数据队列数据
int j=0;
Node *l=p;
while(l&&j<i-1){
j++;
l=l->next;
}
if(!l||j>i-1){
return 0;
}
Node *s=new Node;
s->data=m;
s->next=l->next;
l->next=s;
l=s;
l->next=NULL;
}
void Init_linklist(Linklist *&l){ //初始化栈队列
sNode *s=new sNode;
s->next=NULL; //头结点
l->front=s;
l->rear=s;
}
int empty_queue(Linklist *&l){
if(sum==0){
return 1;
}else{
return 0;
}
}
void en_queue(Linklist *&p,Node *&q){ //入队
sNode *s=new sNode;
s->n=q;
s->next=NULL;
p->rear->next=s;
p->rear=s;
sum++;
}
Node* de_queue(Linklist *&p){ //出队
Node *s=p->front->next->n;
sNode *l=p->front;
p->front=l->next;
if(p->front==p->rear){
p->rear=p->front; //重新定义头结点，到结尾了
}
delete l;
sum--;
return s;
}
int ll_size(Linklist *&p){ //队列长度
return sum;
}
Node* ll_front(Linklist *&p){ //队首元素
return p->front->next->n;
}
Node* ll_rear(Linklist *&p){ //队尾元素
return p->rear->n;
}
int main()
{
Node *p=new Node;
//初始化测试链表
Init_Node(p);
int m;
int i=0;
cout<<"插入测试数据，输入1-结束："<<endl;
while(1){
cin>>m;
if(m==-1){
break;
}
insert_Node(p,++i,m); //插入测试数据队列
}
Linklist *ll=new Linklist;
cout<<"初始化链队"<<endl;
Init_linklist(ll);//初始化链队
//进队
Node *s=p->next;
cout<<"进队序列："<<endl;
while(s!=NULL){
cout<<s->data<<" ";
en_queue(ll,s);
s=s->next;
}
cout<<endl;
cout<<"链队长度："<<ll_size(ll)<<endl;
cout<<"队首元素："<<ll_front(ll)->data<<endl;
cout<<"队尾元素："<<ll_rear(ll)->data<<endl;
cout<<"出队序列："<<endl;
while(!empty_queue(ll)){
Node *s=de_queue(ll);
cout<<s->data<<" ";
}
cout<<endl;
cout<<"链队长度："<<ll_size(ll)<<endl;
return 0;
}
结果截图;
