数组实现循环队列

2022-10-30 09:59:34

队列的特点数据先进先出;

需要一个指向对头,一个指向队尾的标志,这里使用的数组,那就用数组的下标

定义一个指向顺序队列的结构:

#define   max   1024

typedef struct seqqueue{

  int  data[max]; //存放数据的顺序对列,数组

  int  fornt; //指向对头,数组下标,指向出对数据的下标,此时对头指向一个空数据区域

  int  rear;  //指向队尾,数组下标,表示入队数据的下表标

} seqqueue;

一个空的顺序队列在尾部插入一个数据

 一个拥有8个数据空间的顺序队列插入7个数据,此时要想在插入一个成员,对列头和队列尾就又指向同一个位置;

不方便判断队列是满还是空,插入7个数据队列已经满了,满足公式 :rear+1 = front,这只是一个循环,伴随着入队

出对,对头和对尾的位置是一直变化的,且不止一次;

 多次入队出对后,如下图情况所示:此时在入队数据,数组下标会越界;

   (rear+1) % max  此时数组下标又开始从0 开始,完成一个循环

让一个数组实现队列循环,需要让数组下标对数组的长度取余运算,这样不会让数组下标越界

(1) 开始时头和尾都指向同一个地方表示一个空的队列,rear % max  =  front  %  max

(2)队列满(rear+1)% max  =  front  %  max

 seqqueue.c文件:

#include"seqqueue.h"//创建空顺序队列
seqQueue *create_queue(void)
{
    seqQueue*qe = NULL;
    qe= (seqQueue*)malloc(sizeof(seqQueue));if(qe == NULL)
    {printf("create_seqqueue malloc is null \n");return NULL;}

    qe->head = qe->tail = MAX-1;return qe;
}//尾部插入队列int in_queue(seqQueue *qe, u16 value)
{if(qe == NULL)
    {printf("in queue is null\n");return -1;}if(is_full_queue(qe) ==1 )
    {printf("in queue is full\n");return -1;}

    qe->tail = (qe->tail+1) % MAX;//数组下标加1,对MAX 取余的目的是实现数组下标的循环
    qe->data[qe->tail] = value;return1;
}//判断对列满?int is_full_queue(seqQueue *qe)
{if(qe == NULL)
    {printf("is full queue is null\n");return -1;}return ((qe->tail+1)%MAX == (qe->head%MAX) ?1 :0);
}//判队列空?int is_empty_queue(seqQueue *qe)
{if(qe == NULL)
    {printf("is empty queue is null\n");return -1;}return ( qe->head%MAX == qe->tail%MAX ?1 :0 );    
}//显示栈内容,从队列头部开始显示void show_queue(seqQueue *qe)
{if(qe == NULL)
    {printf("show queue is null\n");return ;}if(is_empty_queue(qe)==1)
    {printf("show queue is empty \n");return ;}

    u16 h= qe->head;while( h != qe->tail)
    {//为什么先 h++ 因为head前的一个元素无效
        h++;
        h= h%MAX;
        printf("%d\n",qe->data[h]);
    }
}//头部出队列int out_queue(seqQueue *qe)//出对{if(qe == NULL)
    {printf("out queue is null\n");return -1;}if(is_empty_queue(qe)==1)
    {printf("out queue is empty \n");return -1;}
    
    qe->head++;
    qe->head = (qe->head)%MAX;
    printf("out queue data = %d\n",qe->data[qe->head]);//此处只是通过打印显示,可以通过传递形参地址形式实现return1;
}

seqqueue.h文件:

#ifndef __SEQQUEUE_H#define __SEQQUEUE_H

#include<stdio.h>
#include<stdlib.h>#define MAX 10 //实际只能用 9 个空间存放数据

typedefint u16;//插入数据,尾部入对,头部出对
typedefstruct seqqueue{
    u16 data[MAX];
    u16 head;//队列头,对应当前数据下标
    u16 tail;//队列尾,对应当前数据下标}seqQueue;

seqQueue*create_queue(void);int in_queue(seqQueue *qe, u16 value);//入对int is_full_queue(seqQueue *qe);//判满int is_empty_queue(seqQueue *qe);//判空void show_queue(seqQueue *qe);//显示栈内容int out_queue(seqQueue *qe);//出对#endif

main.c测试文件

#include"seqqueue.h"int main(int argc,constchar *argv[])
{
    seqQueue*s=NULL;
    s=create_queue();

    in_queue(s,1);
    in_queue(s,2);
    in_queue(s,3);
    in_queue(s,4);
    in_queue(s,5);
    in_queue(s,6);
    in_queue(s,7);
    in_queue(s,8);
    in_queue(s,9);
    in_queue(s,0);

    show_queue(s);

    printf("out queue kaishi \n");
    out_queue(s);

    out_queue(s);return0;
}

测试

转载于:https://www.cnblogs.com/electronic/p/10896410.html

  • 作者:weixin_34250434
  • 原文链接:https://blog.csdn.net/weixin_34250434/article/details/93958402
    更新时间:2022-10-30 09:59:34