我们先来看个问题：
【问题描述】
实现循环队列的基本操作。（循环队列最大长度不超过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.相比之下，链队列不用考虑“假溢出问题”，在实际应用中操作起来跟方便