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
*/

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

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

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

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

循环队列的实现原理:

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

上图即为循环队列的示意图;由图片可知,当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
*/
上一篇:链式队列


下一篇:cf1076d 贪心最短路