基础数据结构与算法5：队列

队列：
1.只能从表的一端存数据另一端取数据且遵循FIFO(先进先出)原则的线性存储结构
2.在队列的一端只能插入元素：队尾
3.在队列的另一端只能删除元素：队首

队列的实现

• 采用链表的方式实现队列

1.定义结构

• 定义数据类型Datatype
• 定义链表节点
  存储的数据data
  指向下一个节点的地址next
• 定义链表形式的队列
  头指针：队首元素header
  尾指针：队尾元素tailer
  链表节点个数：队列存储的数据个数size

typedef int Datatype;
// 定义节点
typedef struct Node{
    Datatype data;
    struct Node* next;
} Node;
// 定义链表形式队列
typedef struct Queue{
    Node* header;
    Node* tailer;
    size_t size;
} Queue;

2.创建队列

// 函数：创建队列
Queue* Create_queue(){
    Queue* queue = malloc(sizeof(Queue));
    queue->header = NULL;
    queue->tailer = NULL;
    queue->size = 0;
    return queue;
}

3.获取队列中元素个数

// 函数：获取队列元素个数
size_t GetSize_queue(Queue* queue){
    return queue->size;
}

4.访问队首元素

// 函数：获取队首元素地址
Datatype* GetFrontData_queue(Queue* queue){
    if(NULL == queue) return NULL;
    if(0 == GetSize_queue(queue)) return NULL;
    return &(queue->header->data);
}

7.入队

• 尾添加

// 尾添加
bool Enqueue(Queue* queue,Datatype en_data){
    if(NULL == queue) return false;

    // 创建新的队元素(节点)
    Node* new_node = malloc(sizeof(Node));
    new_node->data = en_data;
    new_node->next = NULL;

    if(0 == GetSize_queue(queue)){
        queue->header = new_node;
        // queue->tailer = new_node;
    }else{
        queue->tailer->next = new_node;
    }
    queue->tailer = new_node;
    queue->size++;
    return true;
}

8.出队

• 头删除

// 函数：出队
bool Dequeue(Queue* queue){
    if(NULL == queue) return false;
    if(0 == GetSize_queue(queue)) return false;
    Node* del_node = queue->header;
    queue->header = del_node->next;
    free(del_node);
    del_node = NULL;
    queue->size--;
    if(0 == GetSize_queue(queue)){
        queue->header = NULL;
        queue->tailer = NULL;
    }
    return true;
}

7.销毁队列

// 函数：销毁队列
void Destory_queue(Queue** queue){
    if(NULL == queue) return;
    if(NULL == *queue) return;
    Node* _node = (*queue)->header;

    while(NULL != _node){
        Node* free_node = _node;
        _node = _node->next;
        free(free_node);
        free_node = NULL;
    }
    free(*queue);
    *queue = NULL;
}