一. 队列

1.1 基本概念

队列，也是一种操作受限的线性表，只允许在表的一端进行插入，在表的另一端进行删除

向队列中插入元素称为入队，删除元素称为出队

队列和我们日常生活中的排队是一致的，最早排队的也是最早离队的，其操作的特性是先进先出

1. 队头，允许删除的一端
2. 队尾，允许插入的一端
3. 空队列，不含任何元素的空表

1.2 基本操作

1. 初始化队列，构造一个空队列

initQueue

2. 判断队列是否为空，为空返回 true，否则返回 false

empty

3. 入队，若队列未满，将 value 加入，使之成为新的队尾

inQueue

4. 出队，若队列非空，删除队头元素

outQueue

5. 读队头元素，若队列非空，则将队头元素赋值给 value

getFront

6. 销毁队列

destoryQueue

1.3 队列的链式存储结构

队列的链式存储，实际上是一个同时带有队头指针和队尾指针的单链表。

为了操作的方便，通常在链式队列前加上一个头结点，此时队头指针指向头结点，队尾指针指向队尾结点

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front;
    LinkNode *rear;
}Queue;

int initQueue(Queue *queue){
    if(queue == NULL || queue->front != NULL)
        return -1;
    queue->front = (LinkNode *)malloc(sizeof(LinkNode));
    queue->front->next = NULL;
    queue->rear = queue->front;
    return 0;
}

int destoryQueue(Queue *queue){
    if(queue == NULL || queue->front == NULL)
        return -1;
    LinkNode *next_node = NULL;
    while(queue->front != NULL){
        next_node = queue->front->next;
        free(queue->front);
        queue->front = next_node;
    }
    return 0;
}

bool empty(Queue *queue){
    if(queue->front == queue->rear)
        return true;
    return false;
}

int inQueue(Queue *queue, int val){
    if(queue == NULL || queue->front == NULL)
        return -1;
    LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
    node->data = val;
    node->next = NULL;
    queue->rear->next = node;
    queue->rear = node;
    return 0;
}

int getFront(Queue *queue, int *value){
    if(queue == NULL || queue->front == NULL || queue->front == queue->rear)
        return -1;
    *value = queue->front->next->data;
    return 0;
}

int outQueue(Queue *queue){
    if(queue == NULL || queue->front == NULL || queue->front == queue->rear)
        return -1;
    LinkNode *del_node = queue->front->next;
    queue->front->next = del_node->next;
    if(queue->rear == del_node)
        queue->rear = queue->front;
    free(del_node);
    return 0;
}

作业

1. 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值

示例

输入：nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

输出：[3, 3, 5, 5, 6, 7]

2. 查阅资料，实现队列的顺序存储结构