我们先来看个问题：
【问题描述】
实现循环队列的基本操作。（循环队列最大长度不超过20）
【输入形式】
输入若干个整数（以空格分隔），其中0表示做出队操作，不为0的整数为入队元素。
【输出形式】
依次输出队列的全部元素，若队列为空，则输出“empty”
【样例输入1】
1 2 3 4 5 6
【样例输出1】
1 2 3 4 5 6
【样例输入2】
1 2 3 0 0 4 0 5
【样例输出2】
4 5
【样例输入3】
1 0 2 0 3 0
【样例输出3】
empty
【样例输入4】
1 0 2 0 0 3 0 0 0
【样例输出4】
empty
下面我们将分别通过顺序循环队列和链队列来实现以上操作
一、顺序循环队列
顺序循环队列需要两个指针，一个用来入队，一个用来出队
顺序循环队列是个在数组中移动的队列
顺序循环队列主要要考虑“假溢出”的问题，为了防止“假溢出”，我们通过(front+1)%MAX来实现
1.1 初始化一个顺序循环队列
#include<stdio.h>
#include<malloc.h>
#define MAX 10
typedef struct Queue{
int *base; //可以理解为一个数组
int front; //指向队头的指针 可以理解为数组的下标
int rear; //指向队尾的指针 可以理解为数组的下标
int len; //队列的长度，方便打印队列
}Queue,*PQueue;
int Init_Queue(PQueue Q){
Q->base=(int *)malloc(MAX*sizeof(int)); //初始化分配一个空间
Q->front=Q->rear=0; //初始化队头队尾在一起
Q->len=0; //初始化队列长度为0
return 1;
}1.2 判断队列是否为空
int Empty_Queue(PQueue Q){
if(Q->front==Q->rear) //当队头和队尾指针在一起的时候，说明是个空队
return 1;
else
return 0;
}1.3 入队
入队前一定要先判断队列是否已经满了，满了就不能再入队了
int Push_Queue(PQueue Q,int e){
if((Q->rear+1)%MAX==Q->front) return 0; //首先要判断队列是否满了
Q->base[Q->rear]=e; //满了无法入队，没满可以入队
Q->rear=(Q->rear+1)%MAX; //这个方法可以让队列成为循环队列
Q->len++; //每次入队队列长度增加1
return 1;
}1.4 出队
出队前一定要判断队列是否已经空了，如果队列空了，那么就没办法出队了
int Pop_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0; //出队前要先判断是否队空
*e=Q->base[Q->front]; //队列不空可以出队
Q->front=(Q->front+1)%MAX; //这个方法可以循环出队
Q->len--; //出队后队长减1
return 1;
}1.5 打印队列
int Print_Queue(PQueue Q){
int i;
for(i=0;i<Q->len;i++){
printf("%d ",Q->base[Q->front+i]); //将队列打印出来
}
printf("\n");
return 1;
}1.6 代码实现
1.6.1 完整代码
#include<stdio.h>
#include<malloc.h>
#define MAX 10
typedef struct Queue{
int *base;
int front;
int rear;
int len;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
Q->base=(int *)malloc(MAX*sizeof(int));
Q->front=Q->rear=0;
Q->len=0;
return 1;
}
int Empty_Queue(PQueue Q){
if(Q->front==Q->rear)
return 1;
else
return 0;
}
int Push_Queue(PQueue Q,int e){
if((Q->rear+1)%MAX==Q->front) return 0;
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAX;
Q->len++;
return 1;
}
int Pop_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAX;
Q->len--;
return 1;
}
int Get_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
return 1;
}
int Print_Queue(PQueue Q){
int i;
for(i=0;i<Q->len;i++){
printf("%d ",Q->base[Q->front+i]);
}
printf("\n");
return 1;
}
int main(){
Queue Q;
int e;
Init_Queue(&Q);
while(scanf("%d",&e)==1){
if(e==0){
Pop_Queue(&Q,&e);
}else{
Push_Queue(&Q,e);
}
}
if(Empty_Queue(&Q)==1){
printf("empty\n");
}else{
Print_Queue(&Q);
}
return 0;
}1.6.2 运行结果
二、链队列（带头结点单链表）
我们用的是带头结点的单链表，方便出队
链队列需要两个指针，分别用来入队和出队
链队列不用考虑“假溢出”问题，操作起来更加方便
2.1 初始化一个链队列
#include<stdio.h>
#include<malloc.h>
typedef struct Node{ //每个结点
int data;
struct Node *next;
}Node,*PNode;
typedef struct Queue{ //保存两个指针
PNode front,rear;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
PNode P=(PNode)malloc(sizeof(Node));
P->next=NULL;
Q->front=Q->rear=P; //初始队尾指针在队头指针位置
return 1;
}2.2 判断队列是否为空
int Empty_Queue(PQueue Q){
if(Q->front==Q->rear) //当队尾指针在队头指针处时，队列为空
return 1;
else
return 0;
}2.3 入队
链队列入队不用考虑“假溢出”问题，操作起来方便
int Push_Queue(PQueue Q,int e){
PNode Pnew=(PNode)malloc(sizeof(Node)); //新建一个结点，用于入队
Pnew->next=NULL;
Pnew->data=e;
Q->rear->next=Pnew; //入队操作只用尾指针rear
Q->rear=Pnew;
return 1;
}2.4 出队
int Pop_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0; //出队先判断是否队空
*e=Q->front->next->data;
if(Q->front->next==Q->rear){ //当只剩一个有效结点的时候，为了避免尾指针丢失
Q->front->next=NULL;
Q->rear=Q->front; //我们删除结点后要让尾指针指向头结点
}else{
Q->front->next=Q->front->next->next;
}
return 1;
}2.5 打印队列
int Print_Queue(PQueue Q){
PNode P=Q->front->next;
while(P){
printf("%d ",P->data); //和打印单链表类似
P=P->next;
}
printf("\n");
}2.6 代码实现
2.6.1 完整代码
#include<stdio.h>
#include<malloc.h>
typedef struct Node{
int data;
struct Node *next;
}Node,*PNode;
typedef struct Queue{
PNode front,rear;
}Queue,*PQueue;
int Init_Queue(PQueue Q){
PNode P=(PNode)malloc(sizeof(Node));
P->next=NULL;
Q->front=Q->rear=P;
return 1;
}
int Empty_Queue(PQueue Q){
if(Q->front==Q->rear)
return 1;
else
return 0;
}
int Push_Queue(PQueue Q,int e){
PNode Pnew=(PNode)malloc(sizeof(Node));
Pnew->next=NULL;
Pnew->data=e;
Q->rear->next=Pnew;
Q->rear=Pnew;
return 1;
}
int Pop_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->front->next->data;
if(Q->front->next==Q->rear){
Q->front->next=NULL;
Q->rear=Q->front;
}else{
Q->front->next=Q->front->next->next;
}
return 1;
}
int Get_Queue(PQueue Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->front->next->data;
return 1;
}
int Print_Queue(PQueue Q){
PNode P=Q->front->next;
while(P){
printf("%d ",P->data);
P=P->next;
}
printf("\n");
}
int main(){
Queue Q;
Init_Queue(&Q);
int e;
while(scanf("%d",&e)==1){
if(e==0){
Pop_Queue(&Q,&e);
}else{
Push_Queue(&Q,e);
}
}
if(Empty_Queue(&Q)==1){
printf("empty\n");
}else{
Print_Queue(&Q);
}
return 0;
}2.6.2 运行结果
三、总结
1.顺序循环队列入队和出队都要考虑“假溢出”的问题
2.链队列出队时要考虑是否是最后一个有效结点，避免尾结点的丢失
3.相比之下，链队列不用考虑“假溢出问题”，在实际应用中操作起来跟方便
