备案控制台
开发者社区 云计算 文章 正文

【DS】队列@栈和队列

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

@TOC
上次实现队列，是在三个月之前，拖到现在才写文章非常惭愧，但细节忘得差不多了反倒利于我思考嘞，写的过程也犯了几个傻错误，它们都变成小注意写在文章中了。

正文开始

1. 队列的概念和结构

1.1 队列的概念

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

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

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

<img src=" title="">

1.2 队列结构

队列也可以数组和链表的结构实现。但数组结构明显不适合，出队列，即头删要挪动数据，效率会低。

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

为了避免每次找尾的麻烦，我们定义一个尾指针，一头一尾构成队列的结构体。

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

2. 队列的实现

头文件附在后面大家自己写嗷，单链表增删查改都会了，这个就是一样的，除了尾指针的加入带来了一点小变动，也没关系，小注意都写好嘞~

2.1 初始化和销毁

2.1.1 初始化

<img src=" title="">
开始时，队列为空，因此我们这样初始化这个结构体 ——
<img src=" title="">

我要的改变head，tail是结构体中的内容，不需要传二级指针，要改变结构体，就传结构体指针就行。

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

2.1.2 销毁

遍历销毁即可。

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

2.2 求队列中有效元素个数、队列是否为空

2.2.1 求队列中有效元素个数

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

2.2.2 队列是否为空

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

2.3 入队和出队

要考虑的和单链表的尾插和头删基本一致。

2.3.1 入队

尾插考虑空链表时的插入。

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

2.3.2 出队

注意！删完了，此时head为空，tail要更改，否则是野指针。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kl3mQswC-1644214522589)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220207135835481.png)]

如果不过更改看似好像没什么问题，毕竟正常人谁会销毁了队列还去访问它呢，但我就是抽风我去取队尾元素，原本被销毁后空间归还系统应该拿不到，可tail未被更改，就还是能拿得到。

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq)); 
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

2.4 取队头队尾元素

注意断言空链表。

2.4.1 取队头数据

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

2.4.2 取队尾数据

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

附

Queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//求队列中有效元素个数
int QueueSize(Queue* pq);
//判断队列是否为空？
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq));
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

test.c

  • [ ] 遍历队列要保证队列的性质，先进先出。
  • [ ] 想取下一个，那就pop掉这个再取下一个，别忘记pop。
#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void testQueue1()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePop(&q);
    QueuePop(&q);
    /*QueuePop(&q);
    QueuePop(&q);*/

    printf("front:%d\n", QueueFront(&q));
    printf("rear:%d\n", QueueBack(&q));
    printf("size:%d\n", QueueSize(&q));

    QueueDestroy(&q);
}

void testQueue2()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);

    // 遍历栈，要保证先进先出的性质
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);//想取下一个，那就pop掉这个再取下一个
    }
    QueueDestroy(&q);
}

int main()
{
    //testQueue1();
    testQueue2();
    return 0;
}
关键词：
栈数据结构
队列数据结构
队列栈数据结构
ds栈数据结构
ds队列数据结构
@浮光掠影
目录
相关文章
倔强的石头_
|
5天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
13 0
倔强的石头_
|
5天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
14 1
誓则盟约
|
3天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
誓则盟约
11 0
jjczqyjxgdegi
|
3天前
|
存储 人工智能 程序员
技术心得记录：堆(heap)与栈(stack)的区别
技术心得记录：堆(heap)与栈(stack)的区别
jjczqyjxgdegi
5 0
枫叶丹4
|
5天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
5 0
lge101058
|
6天前
|
存储 测试技术
【数据结构】操作受限的线性表，栈的具体实现
【数据结构】操作受限的线性表，栈的具体实现
lge101058
17 5
24k纯甄
|
6天前
|
算法
【C/数据结构和算法】：栈和队列
【C/数据结构和算法】：栈和队列
24k纯甄
15 1
HEX9CF
|
10天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解（递归+记忆化搜索）
**NOIP2003普及组栈问题**：给定操作数序列1到n，仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3，输出5。当队列空时返回1，栈空则只能入栈，栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
HEX9CF
9 1
未名编程
|
13天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
未名编程
10 1
倔强的石头_
|
5天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈：原理、步骤与应用
【数据结构与算法】使用数组实现栈：原理、步骤与应用
倔强的石头_
10 0

热门文章

最新文章

  • 1
    【C语言/数据结构】二叉树（层序遍历|判断完全二叉树|性质）
  • 2
    【C 言专栏】C 语言中的数据结构应用
  • 3
    【数据结构】~顺序表
  • 4
    [数据结构]-红黑树
  • 5
    【数据结构】树和二叉树堆（基本概念介绍）
  • 6
    Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
  • 7
    [数据结构]-map和set
  • 8
    【数据结构】二叉树-堆（top-k问题，堆排序，时间复杂度）
  • 9
    高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]
  • 10
    猿创征文｜栈和队列OJ刷题
  • 1
    【算法与数据结构】深入解析二叉树（二）之堆结构实现
    31
  • 2
    ABAP 源代码如何创建嵌套的内表，即内表列数据结构又是内表
    36
  • 3
    Redis数据类型详解：选择合适的数据结构优化你的应用
    81
  • 4
    【算法与数据结构】二叉树（前中后）序遍历2
    26
  • 5
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    43
  • 6
    【数据结构】排序算法
    35
  • 7
    【数据结构】C语言实现链队列(附完整运行代码)
    56
  • 8
    深入理解InnoDB索引数据结构和算法
    75
  • 9
    【数据结构】深入浅出理解链表中二级指针的应用
    45
  • 10
    【数据结构】线性表的链式存储结构
    29

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）