c语言描述-链式队列与循环队列

队列的特点

• 先进先出，即只能从队尾插入元素，从队头删除元素

队列的链式存储结构

#include<stdio.h>
#include <stdlib.h>
#include<malloc.h>
typedef struct QNode
{
    int date;
    struct QNode *next;
}QNode ,*QueuePtr;

typedef  struct
{
    int size; //记录队列长度
    QueuePtr front; //头指针
    QueuePtr rear;  //尾指针
}LinkQueue;
//初始化
void InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear=(QNode *)malloc(sizeof(QNode));
    if(!Q->front)
      exit(0);
    Q->rear->next=NULL;
    Q->size=0;
}
//在队尾插入元素
void InsertQueue(LinkQueue *Q,int e)
{
    QNode *p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(p==NULL)
      exit(0);
    p->date=e;
    Q->rear->next=p;
    Q->rear=p;
    Q->rear->next=NULL;
    Q->size++;
}
//删除队头元素
void Pop_Queue(LinkQueue *Q)
{
    Q->front=Q->front->next;
    free(Q->front);
    Q->size--;
}
//向队列输入数据
void Push_Queue(LinkQueue *Q)
{
    int e;
    QNode *p=NULL;
    printf("请输入数据：\n");
    for(int i=0;;i++)  //
    {
        scanf("%d",&e);
        if(Q->size==0)  //当插入第一个元素时
        {
            Q->front->date=e;
            Q->rear=Q->front;  //头尾指针都指向第一个结点
            Q->size++;
        }
        else
        {
            p=(QueuePtr)malloc(sizeof(QNode));
            if(!p)
              exit(0);
            p->date=e;
            Q->rear->next=p;
            Q->rear=p;
            Q->rear->next=NULL;
            Q->size++;
        }
        if(getchar()=='\n')
            break;
    }
}
//打印队列元素
void ShowQueue(LinkQueue *Q)
{
    printf("队列内的元素为：\n");
    int e;
    QNode *p;
    p=Q->front;
    for(int i=0;i<Q->size;i++)
    {
        e=p->date;
        printf("%d ",e);
        p=p->next;
    }
    printf("\n");
}

int main()
{
    LinkQueue Q,*p;
    p=&Q;
    Push_Queue(p);
    ShowQueue(p);
    InsertQueue(p, 7);
    ShowQueue(p);
    Pop_Queue(p);
    ShowQueue(p);
}
/* 运行结果
请输入数据：
1 2 3 4 5 6
队列内的元素为：
1 2 3 4 5 6
队列内的元素为：
1 2 3 4 5 6 7
队列内的元素为：
2 3 4 5 6 7
Program ended with exit code: 0
*/

队列的顺序存储结构---循环队列

为什么要实现循环队列（图片来自严蔚敏的数据结构）：

上图是队列的普通顺序存储，队列存入数据后，每删除一个元素，front指针都会上移，则front上一个指向的空间就会被浪费，由此引入循环队列；

循环队列的实现原理：

上图即为循环队列的示意图；由图片可知，当front等于rear时，队列可能为空，也可能满，解决办法有两种办法，一是定义一个整型数据记录元素个数；另一种办法是牺牲一个存储空间，当（rear+1）%MIXSIEZ==front时为满；下面讨论第二种方法；

实现过程：

• 插入与删除时，指针均是在循环链表中顺时针移动；
• 插入一个元素时，rear=（rear+1）%MIXSIZE，即向后移动一位；
• 删除一个元素时，front=（front+1）%MIXSIZE，即向后移动一位；
• 判断队列为满：（rear+1）%MIXSIEZ==front

解释：之所以用（rear+1）%MIXSIEZ==front而不用（rear+1）==front来判断队列是否为满，是因为，队列在进行一系列插入与删除操作后rear可能会小于front，如上图，5过了之后又回到0，用取模的方法可以解决这个问题，front=（front+1）%MIXSIZE与rear=（rear+1）%MIXSIZE也是同理；

代码实现：

#include<stdio.h>
#include <stdlib.h>
#include<malloc.h>
#define MIXSIZE 100   //最大存储空间

typedef struct QNode
{
    int size;
    int front;
    int rear;
    int *base;

}QNode;

//初始化
void InitQueue(QNode *Q)
{
    Q->base=(int *)malloc(MIXSIZE*sizeof(int));
    Q->front=Q->rear=0;
    Q->size=MIXSIZE;
}
//插入
void InsertQueue(QNode *Q,int e)
{
   if((Q->rear+1)%MIXSIZE==Q->front)
        printf("队列已满\n");
    Q->base[Q->rear]=e;
    Q->rear=(Q->rear+1)%MIXSIZE;
}
//删除
void Pop_Queue(QNode *Q)
{
    int e;
    e=Q->base[Q->front++];
}
//输入元素
void Push_Queue(QNode *Q)
{
    int e;
    printf("请输入元素：\n");
    for(int i=0;;i++)
    {
        scanf("%d",&e);
        Q->base[Q->rear]=e;
        Q->rear=(Q->rear+1)%MIXSIZE;
        if(getchar()=='\n')  //按回车键结束输入
            break;
    }

}
//打印所以元素
void ShowQueue(QNode *Q)
{
    int e;
    int t=Q->front;
    while(t!=Q->rear)
    {
        e=Q->base[t];
        printf("%d ",e);
        t=(t+1)%MIXSIZE;
    }
    printf("\n");
}

int main()
{
    QNode Q,*p;
    p=&Q;
    InitQueue(p);
    Push_Queue(p);
    ShowQueue(p);
    InsertQueue(p,8);
    ShowQueue(p);
    Pop_Queue(p);
    ShowQueue(p);
}
/* 运行结果
请输入元素：
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 8
2 3 4 5 8
Program ended with exit code: 0
*/