【C数据结构】队列_Queue

小咪咪 2024-03-16 20:20 114阅读 0赞

**目录**

队列\_Queue

【1】队列的概念及结构

【2】节点队列的实现

【2.1】队列的各个接口

【2.2】队列的初始化

【2.3】队列栈的释放

【2.4】队尾入队列

【2.5】队头出队列

【2.6】获取队列头部元素

【2.7】获取队列尾部元素

【2.8】获取队列中有效元素个数

【2.9】检测队列是否为空

--------------------

## 队列\_Queue ##

## 【1】队列的概念及结构 ##

**队列：**只允许在一端进行插入数据操作，在另一端进行删除数据操作的**特殊线性表，队列具有先进先出 FIFO(First In First Out)**

**入队列：**进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为**队头 。**

**栈符合后进先出（First In First Out ）**

![5d3e66c0064e47b5b9e8841dc83374b2.png][]

## 【2】节点队列的实现 ##

队列也可以**数组和链表**的结构实现，**使用链表的结构实现更优一些**，因为如果使用数组的结构，出队列在数组头上出数据，**效率会比较低。**

![dad11d79a0aa4afcb596997f2e893711.png][]

### 【2.1】队列的各个接口 ###

#pragma once
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <assert.h>
    
    
    // 栈数据结构定义 ///
    /* 栈数据结构 */
    typedef int QDataType;
    typedef struct QListNode {
        QDataType _data;
        struct QListNode *_nextNode;
    }QNode;
    
    typedef struct Queue {
        QNode* _head;
        QNode* _tail;
        size_t _size;
    }Q;
    
    
    // 栈常用接口定义 ///
    /* 队列：初始化 */ 
    void QueueInit(Q* q);
    
    /* 队列：销毁 */
    void QueueDestroy(Q* q);
    
    /* 队列：尾插 */
    void QueuePush(Q* q, QDataType val);
    
    /* 队列：头出 */
    void QueuePop(Q* q);
    
    /* 队列：获取头部数据 */
    QDataType QueueFront(Q* q);
    
    /* 队列：获取尾部数据 */
    QDataType QueueBack(Q* q);
    
    /* 队列：获取队列有效元素个数 */
    size_t QueueSize(Q* q);
    
    /* 队列：检查是否为空栈 */
    bool QueueEmpty(Q* q);

### 【2.2】队列的初始化 ###

/* 队列：初始化 */
    void QueueInit(Q* q) {
        // 断言
        assert(q);
    
        // 初始化
        q->_head = q->_tail = NULL;
        q->_size = 0;
    }

### 【2.3】队列栈的释放 ###

/* 队列：销毁 */
    void QueueDestroy(Q* q) {
        // 断言
        assert(q);
    
        // 遍历释放
        QNode* pCur = q->_head;
        while (pCur != NULL) {
            QNode* pDel = pCur;
            pCur = pCur->_nextNode;
    
            free(pDel); pDel = NULL;
        }
    
        // 初始化
        q->_head = q->_tail = NULL;
        q->_size = 0;
    }

### 【2.4】队尾入队列 ###

*  **入队列动画演示**

![7ce958c4fa974179903b5ba2ddf9d691.png][]

*  **入队会出现两种情况**

![10c47127d12e447db5e07ad0c6240f53.png][]

/* 队列：尾插 */
    void QueuePush(Q* q, QDataType val) {
        // 断言
        assert(q);
    
        // 开辟节点
        QNode* newNode = (QNode*)malloc(sizeof(QNode));
        // 开辟失败
        if (newNode == NULL) {
            perror("malloc fail!");
            exit(-1);
        }
        // 开辟成功
        else
        {
            newNode->_data = val;
            newNode->_nextNode = NULL;
        }
    
        // 插入数据
        // 链表为空
        if (q->_tail == NULL) {
            q->_head = q->_tail = newNode;
        }
        // 链表不为空
        else
        {
            q->_tail->_nextNode = newNode;
            q->_tail = q->_tail->_nextNode;
        }
        // 记录数据个数
        q->_size++;
    }

### 【2.5】队头出队列 ###

![6cec223932114d3d9ad7c94faeb7f54c.png][]

/* 队列：头出 */
    void QueuePop(Q* q) {
        // 断言
        assert(q);
    
        // 链表剩余最后一个节点数据
        if (q->_head->_nextNode == NULL) {
            free(q->_head);  
            q->_head = q->_tail = NULL;
        }
        // 链表有很多数据
        else
        {
            QNode* pDel = q->_head;
            q->_head = q->_head->_nextNode;
            free(pDel); pDel = NULL;
        }
    }

### 【2.6】获取队列头部元素 ###

/* 队列：获取头部数据 */
    QDataType QueueFront(Q* q) {
        // 断言
        assert(q);
        // 检测是否是空
        assert(!QueueEmpty(q));
        return q->_head->_data;
    }

### 【2.7】获取队列尾部元素 ###

/* 队列：获取尾部数据 */
    QDataType QueueBack(Q* q) {
        // 断言
        assert(q);
        // 检测是否是空
        assert(!QueueEmpty(q));
        return q->_tail->_data;
    }

### 【2.8】获取队列中有效元素个数 ###

/* 队列：获取队列有效元素个数 */
    size_t QueueSize(Q* q) {
        // 断言
        assert(q);
        return q->_size;
    }

### 【2.9】检测队列是否为空 ###

/* 队列：检查是否为空栈 */
    bool QueueEmpty(Q* q) {
        // 断言
        assert(q);
        return q->_head == NULL && q->_tail == NULL;
    }

[5d3e66c0064e47b5b9e8841dc83374b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8bc1fb1b8a4241b1bbc2f8e720f386fc.png
[dad11d79a0aa4afcb596997f2e893711.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/a4e77987f56e49109167da6d6ee7b747.png
[7ce958c4fa974179903b5ba2ddf9d691.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8c60f7b20a414c8c961483b5d3ba5891.png
[10c47127d12e447db5e07ad0c6240f53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2cf347cb7c854796b4302fd897e940bc.png
[6cec223932114d3d9ad7c94faeb7f54c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/77db4ddb681e4bce9b0a6fe9b04805cb.png