C语言-数据结构-循环队列(静态队列)

偏执的太偏执、 2022-05-17 00:42 307阅读 0赞

## 静态队列(循环队列) ##

问题: 假设队列一共有7个元素位置 0 1 2 3 4 5 6  
1. 参数: front永远指向底层第一个元素 rear(永远指向的是下一个元素位置)  
2. 入队问题: 判断是都rear是否到头,如果到头了该怎么指向?既r此时已经指向6了  
答: r = (r + 1) % 数组长度  
3. 出队问题:判断出队到头了,front如何走? 此时front已经等于6了,  
答: f = (f + 1) % 数组长度  
4. 如何判断队列为空?  
答: 不要忽略一点: 队列在空的情况下,front可能在任意位置;不能用front等于0来判断  
所以用rear = front  
5. 如何判断为满?  
答: 判断方法有两种:一种是另外建立一个变量,用来保存当前的数组已存数据数量,但是每次存取数据还要刷新该变量,所以一般不用, 另一种方法是在rear接近front中间空出一个位置,用于作为满的标志; 当rear+1等于front,后者追上了前者,则可以判断为满了  
答: ( (rear + 1) % 数组长度 ) == front  
6. 如何打印队列?  
答: 将front赋值给i, 通过i进行打印,但是在循环的时候记得是  
. while( i != Q->rear )而不是rear -1;  
. 然后i = (i+1)%数组长度

算法精髓: 数组指针到头了之后,指向头的指针应该指回到 i=0 中  
i=(i+1)%数组长度

/* 2018/8/3 */
    
    #include "stdio.h"
    #include "stdlib.h"
    #include "malloc.h"
    #include "stdbool.h"
    
    #define MAX_SIZE 10
    #define enter printf("\n") 
    #define Enter printf("\n") 
    
    typedef struct Queue{
        int data[MAX_SIZE];
        int front,rear;
    } Queue, *PQueue;
    
    /* 函数声明区 */
    PQueue CreateQueue(void);  //新建队列 
    bool QueueEmpty(PQueue);  //判空返1 
    bool QueueFull(PQueue Q);  //判满返1 
    int InQueue(PQueue Q,int val);  //val 入队 
    int DeQueue(PQueue Q,int *val);  //出队到val 
    int DisplayQueue(PQueue Q);  //打印队列 
    
    int main()
    {
        PQueue Q ;
        int val; 
        int i;
        //初始化 
        Q = CreateQueue();
    
        //入队 
        for(i=0; i<13; i++)
        {
            InQueue(Q,i);
        } 
        DisplayQueue(Q);
    
        //出队 
        for( i=0; i<4; i++ )
        {
            DeQueue(Q,&val);
            printf("%d ",val); 
        } 
        DisplayQueue(Q);
    
        printf("\nHello World\n");
        return;
    } 
    
    /* 创建队列. 返回队列首地址 */ 
    PQueue CreateQueue(void)
    {
        PQueue Q;
        Q = (PQueue)malloc(sizeof(Queue));
        Q->front = Q->rear = 0;
        return Q; 
    }
    
    /* 判断队列是否为空,空返回1 */ 
    bool QueueEmpty(PQueue Q)
    {
        return (Q->front == Q->rear) ? true:false;
    } 
    
    /* 判断队列是否满 满返回1*/
    bool QueueFull(PQueue Q)
    {
       //因为一直有一个是空着的数组元素,所以当rear+1如果等于front的时候满 
        return ( (Q->rear+1) % MAX_SIZE == Q->front ) ? true:false;
    } 
    
    /* 入队 */ 
    int InQueue(PQueue Q,int val)
    {
        if ( QueueFull(Q) ) 
        {
            printf("队列以满,请处理多余数据后在请求入队\n");return;
        } 
    
        Q->data[Q->rear] = val;
        Q->rear = ( Q->rear + 1 ) % MAX_SIZE;   
        return;
    } 
    
    /* 出队 */
    int DeQueue(PQueue Q,int *val)
    {
        if ( QueueEmpty(Q) ) 
        {
            printf("队列为空,请添加数据后在请求出队\n");return;
        }   
    
        *val = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAX_SIZE;
        return; 
    } 
    
    /* 从front开始遍历显示队列 */
    int DisplayQueue(PQueue Q)
    {
        if ( QueueEmpty(Q) ) 
        {
            printf("队列为空,请添加数据后在请求打印\n");return;
        } 
    
        int i = Q->front; 
        Enter;  
        while( i != Q->rear)
        {
            printf("%d ",Q->data[i]);
            i = (i+1) % MAX_SIZE;
        } 
        enter;
        return;
    }