【我的漫漫跨考路】数据结构·队列的链表实现

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  4
//注：定义队列结构体及其指针
typedef struct Queue
{
    char Data;
    struct Queue *next;

} Queue, *PtrQ;
//注：定义队首队尾的指针以及队列的大小指数
typedef struct {
    PtrQ front;
    PtrQ rear;
    int size;
} *Pointer;

//注：初始化队列函数，申请内存建立一个空表头，成为入口和链表的接口
//注：此处一次性的把六个存储空间全部整合摆好，然后形成了后面的图解中的内存分布形式，一个表头，五个队列内存块
PtrQ InitQueue()
{
    Queue *ptrQ;
    ptrQ=(Queue *)malloc(sizeof(Queue));
    int len=MAXSIZE;
    PtrQ head=ptrQ;
    while(len--)
    {
        //注：采用的是尾插法的链表生成模式
        PtrQ p=(Queue *)malloc(sizeof(Queue));
        p->next=head->next;
        head->next=p;
        head=p;
    }
    head->next=ptrQ->next;
    //注：将初始化后的链表队列传回
    return ptrQ;
}


//注：插入数值函数,先预判需要插入内存是否已经满了
void Putin(PtrQ ptrQ,Pointer queue,char item)
{
    if (queue->size==MAXSIZE)
    {
        printf("\n队列已经满了！！~~\n");
    }
    else
    {
        //注：如果队列未满，分为两种情况，第一次入值和后面的入值
        if (queue->rear==queue->front&&queue->size==0)
        {
            PtrQ L=ptrQ->next;
            //注：此时如果是第一次插入数值，那么头指针也要跟着跑一下！
            printf("\n队列空间刚刚空空如也！~终于等到你！~\n");
            queue->front=L;
            queue->rear=L;
        }
        else
        {
            //注：后面的入值就不需要考虑那么多，因为是循环的链表，所以不存在先后关系，只要向前走已经可以从头到尾，
            PtrQ L=queue->rear;
            queue->rear=L->next;
        }
        queue->rear->Data=item;
        queue->size++;
        printf("\n成功插入！数值是:|\t%c\t|,当前队列内有%d个数！！\n",item,queue->size);
    }

}

//注：抛出数值函数,先预判是否还有数值可以抛出，抛出后头指针向前走1位
char Putout(PtrQ ptrQ,Pointer queue)
{
    if (queue->size==0)
    {
        printf("\n我大清！亡了！！！\n" );
    }
    else
    {
        //注：抛出函数的内容很简单，头指针向后走一位，size-- 然后抛出数值即可
        char out;
        PtrQ L=queue->front;
        out=L->Data;
        queue->front=L->next;
        queue->size--;
        printf("\n抛出后当前只有%d个数\t",queue->size);
        printf("被抛出来的是：| \t%c\t|\n ",out);
        return 0;
    }
    return 0;
}


//注：遍历函数，简单易懂，因为是循环体，所以不存在夏先先后，从头到尾跑一遍，一定是整个队列的输出，只要用size控制输出长度即可
void ShowQueue(PtrQ ptrq,Pointer queue)
{

    PtrQ L=queue->front;
    int X=queue->size;
    while(X--)
    {
        char out;
        out=L->Data;
        L=L->next;
        printf("\n现在整个队列中的情况是：|\t%c  \t |\n",out);
    }
    printf("\n******遍历完成！******\n\n");
}



int main()
{
    //注：初始化整个链表
    Pointer queue;
    PtrQ ptrQ;
    ptrQ=InitQueue();
    queue->front=ptrQ;
    queue->rear=ptrQ;
    queue->size=0;
    //注：为了测试所有函数的性能，先压入四个值，然后全部抛出，再请求抛出，会回复：大清亡了！
    Putin(ptrQ, queue, 'a');
    Putin(ptrQ, queue, 'c');
    Putin(ptrQ, queue, 'd');
    Putin(ptrQ, queue, 'Z');
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    //注：然后再次压入数值，在抛出
    Putin(ptrQ, queue, 'G');
    Putin(ptrQ, queue, 'H');
    Putout(ptrQ, queue);
    Putout(ptrQ, queue);
    Putin(ptrQ, queue, 'D');
    //注：最后遍历
    ShowQueue(ptrQ,queue);
    return 0;
}

队列空间刚刚空空如也！~终于等到你！~

成功插入！数值是:|    a   |,当前队列内有1个数！！

成功插入！数值是:|    c   |,当前队列内有2个数！！

成功插入！数值是:|    d   |,当前队列内有3个数！！

成功插入！数值是:|    Z   |,当前队列内有4个数！！

抛出后当前只有3个数    被抛出来的是：|    a   |

抛出后当前只有2个数    被抛出来的是：|    c   |

抛出后当前只有1个数    被抛出来的是：|    d   |

抛出后当前只有0个数    被抛出来的是：|    Z   |

我大清！亡了！！！

成功插入！数值是:|    G   |,当前队列内有1个数！！

成功插入！数值是:|    H   |,当前队列内有2个数！！

抛出后当前只有1个数    被抛出来的是：|    G   |

抛出后当前只有0个数    被抛出来的是：|    H   |

成功插入！数值是:|    D   |,当前队列内有1个数！！

现在整个队列中的情况是：|    D    |

******遍历完成！******

Program ended with exit code: 0