队列

一种可以实现“先进先出”的存储结构。

分类：

• 链式队列：用链表实现；
• 静态队列：用数组实现，通常都是循环队列。

循环队列：

1. 静态队列为什么是循环队列？
   避免内存浪费。

2. 循环队列需要几个参数来确定？
   2个参数：front 与 rear。

3. 循环队列各个参数含义。
   不同场合有不同含义：
   1、队列初始化：front 与 rear 的值都是 0。
   2、队列非空：font 代表队列第一个元素，rear 代表队列最后一个有效元素的下一个元素。
   3、队列空：front` 与 rear 值相等，但不一定是 0 。

4. 循环队列入队伪算法讲解。
   1、将值存入 rear 所代表的位置。
   2、r 指向下一位。错误写法 rear = rear+1，正确写法：rear =( rear+1)%(数组长度)。

5. 循环队列出队伪算法讲解。
   同入队，front = (front+1)%数组长度

6. 如何判断循环队列是否为空。
   rear 的值与 front 的值相同时，队列为空。

7. 如何判断循环队列是否已满。
   front 可能比 rear 大，也可能比 rear 小，也可能相等。
   两种方式判断：
   1、多增加一个标识参数，标识数组长度。
   2、少用一个元素（通常使用第二种方式）。例如队列长度为6，可以使用 6 个元素，但让其只使用 5 个元素。

if((r+1)%数组长度 == f){
  已满
}else{
  不满
}

队列实现

#include <stdio.h>
#include <malloc.h>

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 out_quere(QUEUE *, int *pVal);

int main(void)
{
    QUEUE Q;
    int val;

    init(&Q);
    en_queue(&Q, 1);
    en_queue(&Q, 2);
    en_queue(&Q, 3);
    en_queue(&Q, 4);
    en_queue(&Q, 5);
    en_queue(&Q, 6);

    traverse_queue(&Q);

    if (out_quere(&Q, &val))
    {
        printf("出队成功,出队元素是 %d\n", val);
    }
    else
    {
        printf("出队失败!\n");
    }

    return 0;
}

// 初始化
void init(QUEUE *pQ)
{
    //pBase 指向了 24 个字节的数组.
    pQ->pBase = (int *)malloc(sizeof(int) * 6);
    pQ->front = 0;
    pQ->rear = 0;
}

// 判断队列是否已满
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 traverse_queue(QUEUE *pQ)
{
    int i = pQ->front;
    while (i != pQ->rear)
    {
        printf("%d ", pQ->pBase[i]);
        i = (i + 1) % 6
    }
    return;
}

// 判断队列是否为空

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

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

队列应用

所有和时间有关的操作都与队列的影子。