B站-5.线性结构应用之队列

静态队列——循环队列

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
/*
线性结构的常见应用之：队列
定义：
    一种可以实现“先进先出”的存储结构
分类：
    链式队列：链表
    静态队列：数组(此处进行实现)
        静态队列都必须是循环队列
        循环队列：
            1.静态队列为什么必须是循环队列
                分配内存空间
            2.循环队列需要几个参数
                两个参数，不同场合有不同的含义
                front与rear
            3.各个参数的含义
                1).队列初始化
                        front与rear的值都为0
                2).队列非空
                        front代表队列的第一个元素
                        rear代表队列的最后一个有效元素的下一个元素
                3).队列空
                        front与rear的值相等，但不一定为0
            4.循环队列入队伪算法
                1.将值放入r所代表的位置
                2.r=(r+1)%数组长度
            5.循环队列出队伪算法
                1.f=(f+1)%数组长度
            6.如何判断循环队列是否为空
                1.如果f == r 则该队列为空
            7.如何判断循环队列已满
                两种方式：
                1.多增加一个标识参数
                2.少用一个元素，r f紧挨着
                    if((r+1)%数组长度 == f)
                        已满
                    else
                        未满
算法:
    入队
    出队
队列的具体应用：
    所有和时间有关的操作
*/
typedef struct Queue
{
    int *pBase;
    int front;
    int rear;
} QUEUE;

void init(QUEUE *);//初始化
bool en_queue(QUEUE *,int val);//入队
void traverse_queue(QUEUE *);//遍历
bool full_queue(QUEUE *);//判断是否满
bool emput_queue(QUEUE *pQ);//判断是否为空
bool out_queue(QUEUE *,int *pVal);//出队 保存出队的元素

int main()
{
    int val;
    QUEUE Q;
    init(&Q);
    en_queue(&Q,1);
    en_queue(&Q,2);
    en_queue(&Q,3);
    traverse_queue(&Q);
    printf("\n");
    if(out_queue(&Q,&val))
    {
        printf("出队成功，出队的元素是：%d\n",val);
    }
    else
    {
        printf("出队失败!\n");
    }
    traverse_queue(&Q);
    return 0;
}

bool emput_queue(QUEUE *pQ)
{
    if(pQ->front==pQ->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool out_queue(QUEUE *pQ,int *pVal)
{
    if(emput_queue(pQ))
    {
        return false;
    }
    else
    {
        *pVal = pQ->pBase[pQ->front];
        pQ->front = (pQ->front+1)%6;
        return true;
    }
}

void traverse_queue(QUEUE *pQ)
{
    int i = pQ->front;
    while(i!=pQ->rear)
    {
        printf("%d ",pQ->pBase[i]);
        i=(i+1)%6;
    }
}

bool full_queue(QUEUE *pQ)
{
    if((pQ->rear+1)%6==pQ->front)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool en_queue(QUEUE *pQ,int val)
{
    if(full_queue(pQ))
    {
        return false;
    }
    else
    {
        pQ->pBase[pQ->rear] = val;
        pQ->rear = (pQ->rear+1)%6;
        return true;
    }
}

void init(QUEUE *pQ)
{
    pQ->pBase = (int *)malloc(sizeof(int)*6);//创建数组长度为6的数组，并获取数组的首地址
    pQ->front = 0;
    pQ->rear = 0;
}

```

链式队列——链队列

```
#include <stdio.h>
#include <stdlib.h>
typedef struct QNode //结点结构
{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct //队列的链表结构
{
    //队头、尾指针
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

int main(void)
{
    LinkQueue Q;
    int i,e;
    InitQueue(&Q);
    for(i=0;i<5;i++){
        EnQueue(&Q,i);
    }
    Display(&Q);
    printf("\n");
    i=DeQueue(&Q,&e);
    printf("%d %d",i,e);

}

//入队  插入元素e为Q的新的队尾元素
int EnQueue(LinkQueue *Q,int e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s){
        return 0;
    }
    s->data = e;
    s->next = NULL;

    Q->rear->next = s;//把拥有元素e新结点s赋值给原队尾结点的后继
    Q->rear = s;//把当前的s设置为队尾结点，rear指向s
    return 1;

}

//出队 若队列不空，删除Q的队头元素，用e返回其值，并返回1,否则返回0
int DeQueue(LinkQueue *Q,int *e){
    QueuePtr p;
    if(Q->front==Q->rear){
        return 0;
    }
    p=Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear = p){
        Q->rear = Q->front;
    }
    free(p);
    return 1;
}

//建立一个空队列
void InitQueue(LinkQueue *Q)
{
    Q->front=Q->rear = (QNode *)malloc(sizeof(QNode));
    Q->rear->next = NULL;
}

//遍历
void Display(LinkQueue *Q){
    QNode *p;
    p = Q->front->next;
    while(p!=NULL)
    {
         printf("%d ", p->data);
         p = p->next;
    }
}
```