【我的漫漫跨考路】数据结构之队列的线性实现

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  5
//注：定义队列结构体及其指针
typedef struct Queue
{
    int Data[MAXSIZE];
    int  front;
    int  rear;

} Queue, *PtrQ;


//注：初始化队列函数，传入一个表头，之后申请内存，使之成为静态变量

PtrQ InitQueue(PtrQ ptrq)
{
    Queue *ptrQ;
    ptrQ=(Queue *)malloc(MAXSIZE*sizeof(Queue));
    //注：初始尾指针，头指针指向-1，每次只要成为空队列就重新置-1，确保空队列有区别于其他的情况
    ptrQ->front=-1;
    ptrQ->rear=-1;
    //注：将初始化后的线性表队列传回
    return ptrQ;
}



//注：插入数值函数,先预判需要插入的地方是否合法
void Putin(PtrQ ptrQ,int item)
{
    if ( (ptrQ->rear + 1)%MAXSIZE == ptrQ->front )
    {        /* 空间已满，不能插入*/
        printf("队列空间已满，不能插入\n\n");

    }
    else
    {
        if ( ptrQ->rear==ptrQ->front&&ptrQ->front==-1 )
        {
            /*检查插入的时候是否为第一次插入*/
            printf("\n人家刚刚还是空队列呢,现在被你插入了~~\n");
        }
        //注：插入后，要对队列中的尾指针做改变，向前进一位，
        ptrQ->Data[++ptrQ->rear]=item;
        //注：此时如果是第一次插入数值，那么头指针也要跟着跑一下！
        if (ptrQ->front==-1) ptrQ->front=0;
        // 注：如果尾指针已经到了最后一位，那么再次插入数值就要回到0位
        if (ptrQ->rear==MAXSIZE)  ptrQ->rear=0;
        printf("成功插入！尾巴是:%d\t脑袋是:%d\n\n",ptrQ->rear,ptrQ->front);
    }
}


//注：抛出数值函数,先预判是否合法，抛出后头指针向前走1位
int Putout(PtrQ ptrQ)
{
    int out;
    if ( ptrQ->front ==-1 )
    {
        /*检查插入位置的合法性*/
        printf("\n当前还是空队列呢，没东西了!\n\n");
        return 0;
    }
    else if(ptrQ->front==ptrQ->rear)
    { //注：如果只剩下一个数值，那么抛出之后就成为空列表，就要回归-1位，方便调用
        out=ptrQ->Data[ptrQ->front];
        printf("\n我空了，弹尽粮绝 最后的子弹: %d\t\n",out);
        ptrQ->front =-1;
        ptrQ->rear =-1;
        printf("成功抛出！尾巴是:%d\t脑袋是:%d\n\n",ptrQ->rear,ptrQ->front);
        return out;
    }
    //注：如果是正常情况，也就是说抛出前还有超过一个元素，可以分为头指针小于尾指针和大于尾指针两种情况
       //注：另外还有就是如果头指针已经指到最后一个位置，那么抛出后头指针置0
    else if (ptrQ->front==MAXSIZE-1)
        //注：
    {
        out=ptrQ->Data[ptrQ->front++];
        ptrQ->front=0;
        printf("\n被抛出来：\t%d \n",out);
        printf("成功抛出！尾巴是:%d\t脑袋是:%d\n\n",ptrQ->rear,ptrQ->front);
        return out;
    }
    //头指针不指向最后一个位置，那么直接输出，头指针加1就好了
    else
    {
        out=ptrQ->Data[ptrQ->front];
        ptrQ->front++;
        printf("\n被抛出来：\t%d \n",out);
        printf("成功抛出！尾巴是:%d\t脑袋是:%d\n\n",ptrQ->rear,ptrQ->front);
        return out;
    }
}



//注：遍历函数，简单易懂，不过分为三种情况 1.空队列  2.头指针小于尾指针  3.头指针大于尾指针
void ShowQueue(PtrQ ptrq)
{
    printf("\n******遍历的量是：******\n");
    //注：空队列
    if ( ptrq->front ==-1 )
    {
        /*检查插入位置的合法性*/
        printf("\n当前还是空队列呢，没东西给你遍历了!\n\n");
         exit(-1);
    }
    //非空队列
    int i=ptrq->front,j=ptrq->rear;
   //注：头指针在尾指针之前，也就是说直接自增头指针知道等于尾指针即可
    if (i<=j)
    {
        for (;i<=j; i++)
        {
            printf("%d\t??加油啊！??\n",ptrq->Data[i]);
        }
    }
    //注：头指针在尾指针后面，那么就需要头指针有个回0的过程，回0之后等同于上面的小于的情况
    else
    {
        while(i!=MAXSIZE)
        {
            printf("%d\n",ptrq->Data[i]);
            i++;
        }
        i=0;
        for (;i<=j; i++)
        {
            printf("%d\n ??加油啊！??\n",ptrq->Data[i]);
        }
    }
    printf("******遍历完成！******\n\n");
}


int main()
{
    PtrQ ptrq;
    ptrq=InitQueue(ptrq);
    Putin(ptrq,5);
    Putin(ptrq,3);
    ShowQueue(ptrq);
    Putin(ptrq,38);
    Putin(ptrq,66);
    Putin(ptrq,69);
    Putin(ptrq,88);
    ShowQueue(ptrq);
    Putout(ptrq);
    printf("\n ------------------\n| \tfuck off \t |\n ------------------\n" );
    ShowQueue(ptrq);
    Putout(ptrq);
    ShowQueue(ptrq);
    Putout(ptrq);
    Putout(ptrq);
    Putout(ptrq);
    Putout(ptrq);
    ShowQueue(ptrq);
    return 0;
}

人家刚刚还是空队列呢,现在被你插入了~~
成功插入！尾巴是:0    脑袋是:0

成功插入！尾巴是:1    脑袋是:0


******遍历的量是：******
5     加油啊！?
3     加油啊！?
******遍历完成！******

成功插入！尾巴是:2    脑袋是:0

成功插入！尾巴是:3    脑袋是:0

成功插入！尾巴是:4    脑袋是:0

队列空间已满，不能插入


******遍历的量是：******
5     加油啊！?
3     加油啊！?
38     加油啊！?
66     加油啊！?
69     加油啊！?
******遍历完成！******


被抛出来：    5 
成功抛出！尾巴是:4    脑袋是:1


 ------------------
|     fuck off     |
 ------------------

******遍历的量是：******
3     加油啊！?
38     加油啊！?
66     加油啊！?
69     加油啊！?
******遍历完成！******


被抛出来：    3 
成功抛出！尾巴是:4    脑袋是:2


******遍历的量是：******
38     加油啊！?
66     加油啊！?
69     加油啊！?
******遍历完成！******


被抛出来：    38 
成功抛出！尾巴是:4    脑袋是:3


被抛出来：    66 
成功抛出！尾巴是:4    脑袋是:4


我空了，弹尽粮绝 最后的子弹: 69    
成功抛出！尾巴是:-1    脑袋是:-1


当前还是空队列呢，没东西了!

Program ended with exit code: 0