链队是采用链式存储结构实现的队列，通常链队用单链表来表示。一个链队需要两个分别指向队头和队尾的指针才能唯一确定。
创建队列的链式存储结构//创建链队列结点
typedef struct LinkNode{
int data;
LinkNode* next;
}*LinkNodePtr;
//链队列
typedef struct LinkQueue{
LinkNodePtr front; //队头指针
LinkNodePtr rear; //队尾指针
}*LinkQueuePtr;
初始化
LinkQueuePtr initQueue(){
LinkNodePtr headerPtr=(LinkNodePtr)malloc(sizeof(struct LinkNode));
LinkQueuePtr resultPtr=(LinkQueuePtr)malloc(sizeof(struct LinkQueue));
headerPtr->data=-1;
headerPtr->next=NULL;
resultPtr->front=headerPtr;
resultPtr->rear=headerPtr;
return resultPtr;
}
打印队列
void outputLinkQueue(LinkQueuePtr paraQueuePtr){
LinkNodePtr tempPtr=paraQueuePtr->front->next;
while(tempPtr!=NULL){
printf("%d ",tempPtr->data);
tempPtr=tempPtr->next;
}
printf("rn");
}
入队
void enqueue(LinkQueuePtr paraQueuePtr,int e){
//创建新节点
LinkNodePtr p=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
p->data=e;
p->next=NULL;
//移动rear指针,让p入队
paraQueuePtr->rear->next=p;
paraQueuePtr->rear=p;
}
出队
int dequeue(LinkQueuePtr paraQueuePtr){
if(paraQueuePtr->front==paraQueuePtr->rear){
//队列为空
printf("队列为空，无法删除rn");
return -1;
}
//找到队列最前面结点
LinkNodePtr p=paraQueuePtr->front->next;
int e=p->data;
//删除此结点
paraQueuePtr->front->next=paraQueuePtr->front->next->next;
if(paraQueuePtr->rear==p){
paraQueuePtr->rear=paraQueuePtr->front;
}
free(p);
return e;
}
测试函数
void test(){
LinkQueuePtr tempQueuePtr=initQueue();
enqueue(tempQueuePtr, 5);
enqueue(tempQueuePtr, 7);
enqueue(tempQueuePtr, 58);
outputLinkQueue(tempQueuePtr);
printf("删除%drn",dequeue(tempQueuePtr));
outputLinkQueue(tempQueuePtr);
printf("删除%drn",dequeue(tempQueuePtr));
outputLinkQueue(tempQueuePtr);
printf("删除%drn",dequeue(tempQueuePtr));
outputLinkQueue(tempQueuePtr);
printf("删除%drn",dequeue(tempQueuePtr));
}
完整代码
#include运行结果#include //创建链队列结点 typedef struct LinkNode{ int data; LinkNode* next; }*LinkNodePtr; //链队列 typedef struct LinkQueue{ LinkNodePtr front; //队头指针 LinkNodePtr rear; //队尾指针 }*LinkQueuePtr; //初始化 LinkQueuePtr initQueue(){ LinkNodePtr headerPtr=(LinkNodePtr)malloc(sizeof(struct LinkNode)); LinkQueuePtr resultPtr=(LinkQueuePtr)malloc(sizeof(struct LinkQueue)); headerPtr->data=-1; headerPtr->next=NULL; resultPtr->front=headerPtr; resultPtr->rear=headerPtr; return resultPtr; } //打印队列 void outputLinkQueue(LinkQueuePtr paraQueuePtr){ LinkNodePtr tempPtr=paraQueuePtr->front->next; while(tempPtr!=NULL){ printf("%d ",tempPtr->data); tempPtr=tempPtr->next; } printf("rn"); } //入队 void enqueue(LinkQueuePtr paraQueuePtr,int e){ //创建新节点 LinkNodePtr p=(LinkNodePtr)malloc(sizeof(LinkNodePtr)); p->data=e; p->next=NULL; //移动rear指针,让p入队 paraQueuePtr->rear->next=p; paraQueuePtr->rear=p; } //出队 int dequeue(LinkQueuePtr paraQueuePtr){ if(paraQueuePtr->front==paraQueuePtr->rear){ //队列为空 printf("队列为空，无法删除rn"); return -1; } //找到队列最前面结点 LinkNodePtr p=paraQueuePtr->front->next; int e=p->data; //删除此结点 paraQueuePtr->front->next=paraQueuePtr->front->next->next; if(paraQueuePtr->rear==p){ paraQueuePtr->rear=paraQueuePtr->front; } free(p); return e; } //测试 void test(){ LinkQueuePtr tempQueuePtr=initQueue(); enqueue(tempQueuePtr, 5); enqueue(tempQueuePtr, 7); enqueue(tempQueuePtr, 58); outputLinkQueue(tempQueuePtr); printf("删除%drn",dequeue(tempQueuePtr)); outputLinkQueue(tempQueuePtr); printf("删除%drn",dequeue(tempQueuePtr)); outputLinkQueue(tempQueuePtr); printf("删除%drn",dequeue(tempQueuePtr)); outputLinkQueue(tempQueuePtr); printf("删除%drn",dequeue(tempQueuePtr)); } int main(){ test(); }
5 7 58 删除5 7 58 删除7 58 删除58 队列为空，无法删除 删除-1二、循环队列
初始化创建空队列时，令front=rear=0。每当插入新的队尾元素时，rear+1；删除队头元素时，front+1。循环队列则是保持头尾指针及元素之间的关系不变，只是在循环队列中，头、尾指针“依环状增一”的操作可用“模”运算来实现。
因为队列无论是满还是空，头尾指针都相同，故而无法用front=rear这个条件判断队列的状态。对于这个问题，处理方法是少用一个元素空间，即当队列中有n-1个元素时就认为队满。这样队空时判断条件不变，即front=rear时；队满的判断条件则为（rear+1）%n=front。
typedef struct CircleQueue{
int data[5];
int front;
int rear;
}*CircleQueuePtr;
初始化
CircleQueuePtr initCircleQueue(){
CircleQueuePtr resultPtr = (CircleQueuePtr)malloc(sizeof(struct CircleQueue));
resultPtr->front=0;
resultPtr->rear=0;
return resultPtr;
}
入队
void enqueue(CircleQueuePtr paraQueuePtr,int e){
if((paraQueuePtr->rear+1)%5==paraQueuePtr->front%5){
printf("队满无法添加rn");
return;
}
paraQueuePtr->data[paraQueuePtr->rear%5]=e;
paraQueuePtr->rear++;
}
出队
int dequeue(CircleQueuePtr paraQueuePtr){
if(paraQueuePtr->rear==paraQueuePtr->front){
printf("队空无法删除rn");
return -1;
}
int resultValue=paraQueuePtr->data[paraQueuePtr->front%5];
paraQueuePtr->front++;
return resultValue;
}
打印队列
void outputCircleQueue(CircleQueuePtr paraQueuePtr){
if(paraQueuePtr->rear==paraQueuePtr->front){
printf("队空rn");
return;
}
for(int i=paraQueuePtr->front;irear;i++){
printf("%d ",paraQueuePtr->data[i%5]);
}
printf("rn");
}
测试函数
void test(){
CircleQueuePtr tempPtr=initCircleQueue();
enqueue(tempPtr,10);
enqueue(tempPtr,15);
enqueue(tempPtr,20);
enqueue(tempPtr,15);
outputCircleQueue(tempPtr);
enqueue(tempPtr,30);
outputCircleQueue(tempPtr);
printf("删除：%dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("删除：%dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("删除：%dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("删除：%dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
printf("删除：%dn",dequeue(tempPtr));
outputCircleQueue(tempPtr);
}
完整代码
#include运行结果#include typedef struct CircleQueue{ int data[5]; int front; int rear; }*CircleQueuePtr; //初始化 CircleQueuePtr initCircleQueue(){ CircleQueuePtr resultPtr = (CircleQueuePtr)malloc(sizeof(struct CircleQueue)); resultPtr->front=0; resultPtr->rear=0; return resultPtr; } //入队 void enqueue(CircleQueuePtr paraQueuePtr,int e){ if((paraQueuePtr->rear+1)%5==paraQueuePtr->front){ printf("队满无法添加rn"); return; } paraQueuePtr->data[paraQueuePtr->rear%5]=e; paraQueuePtr->rear++; } //出队 int dequeue(CircleQueuePtr paraQueuePtr){ if(paraQueuePtr->rear==paraQueuePtr->front){ printf("队空无法删除rn"); return -1; } int resultValue=paraQueuePtr->data[paraQueuePtr->front%5]; paraQueuePtr->front++; return resultValue; } //打印队列 void outputCircleQueue(CircleQueuePtr paraQueuePtr){ if(paraQueuePtr->rear==paraQueuePtr->front){ printf("队空rn"); return; } for(int i=paraQueuePtr->front;i rear;i++){ printf("%d ",paraQueuePtr->data[i%5]); } printf("rn"); } //测试 void test(){ CircleQueuePtr tempPtr=initCircleQueue(); enqueue(tempPtr,10); enqueue(tempPtr,15); enqueue(tempPtr,20); enqueue(tempPtr,15); outputCircleQueue(tempPtr); enqueue(tempPtr,30); outputCircleQueue(tempPtr); printf("删除：%dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("删除：%dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("删除：%dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("删除：%dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); printf("删除：%dn",dequeue(tempPtr)); outputCircleQueue(tempPtr); } int main(){ test(); }
10 15 20 15 队满无法添加 10 15 20 15 删除：10 15 20 15 删除：15 20 15 删除：20 15 删除：15 队空 队空无法删除 删除：-1 队空
