【数据结构】——拿捏栈和队列2

2022-05-11 92

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】——拿捏栈和队列2

二、队列

队列的概念和结构

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

队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

【数据结构】——拿捏栈和队列_C语言_10

【数据结构】——拿捏栈和队列_数据结构_11

入队列：进行插入操作的一端称为队尾

【数据结构】——拿捏栈和队列_栈和队列_12

出队列：进行删除操作的一端称为队头

【数据结构】——拿捏栈和队列_栈和队列_13

队列的实现思路

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

而链表我们采用双向链接结构，一个指针来维护头节点，一个指针维护尾部节点

【数据结构】——拿捏栈和队列_接口实现_14

定义的结构体类型如下：

typedef int QDataType;

//创建一个结点型结构体
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QueueNode;

//创建一个队列
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

队列的内存布局图

【数据结构】——拿捏栈和队列_接口实现_15

队列接口实现

1.初始化和销毁

初始化：初始化只需将两个指针置为NULL。

销毁：同链表一样，保存下一个结点地址，释放当前结点，直到指针为NULL。

【数据结构】——拿捏栈和队列_接口实现_16

//初始化队列
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = NULL;//有了头指针就不用二级指针来维护了
    pq->tail = NULL;
}

//队列销毁
void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur != NULL)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = NULL;
    pq->tail = NULL;
}

2.入队

入队和单链表的尾插一样，只是这里更简单，这里不需要找尾。

注意：

队列为空。
队列不为空。

//入队函数
void QueuePush(Queue* pq, QDatatype x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (!pq->head)
        pq->head = pq->tail = newnode;
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

3.出`队

和单链表头删一样，保存第二个结点地址释放，队头位置。

注意：队列不能为空。

//出数据，类似链表的头删
void QueuePop(Queue* pq)
{
    assert(pq);
    //要保证队列不能为空
    assert(pq->head != NULL);
    QueueNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;

    //防止野指针出现，当队列为空时要把tail指针置为空
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

4.取队头数据

返回队头元素即可。

5.取队尾数据

返回队尾元素即可。

6.获取队列元素个数

//获取队列元素个数
int QueueSize(Queue* pq)
{
    assert(pq);
    int count = 0;
    QueueNode* cur = pq->head;
    while (cur != NULL)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

7.判断队列是否为空

直接判断头指针是否为空，就可判断队列是否为空。

【数据结构】——拿捏栈和队列_数据结构_17

【数据结构】——拿捏栈和队列2

二、队列

队列的概念和结构

队列的实现思路

队列的内存布局图

队列接口实现

1.初始化和销毁

2.入队

3.出`队

4.取队头数据

5.取队尾数据

6.获取队列元素个数

7.判断队列是否为空

热门文章

最新文章

相关课程

相关电子书

【数据结构】——拿捏 栈和队列2

二、队列

队列的概念和结构

队列的实现思路

队列的内存布局图

队列接口实现

1.初始化和销毁

2.入队

3.出`队

4.取队头数据

5.取队尾数据

6.获取队列元素个数

7.判断队列是否为空

热门文章

最新文章

相关课程

相关电子书

【数据结构】——拿捏栈和队列2