【数据结构】 链队列的基本操作 （C语言版）

目录

一、链队列

1、链栈的定义：

2、链栈的优缺点：

二、链队列的基本操作算法（C语言）    

1、宏定义

  2、创建结构体

3、链栈的初始化 

4、链队列的入队 

5、链队列的出队

6、取链队列的对头元素

7、链队列的销毁

8、链队列的清空

9、判断链队列是否为空

10、求队列长度

 11、遍历队列元素

三、链队列的基本操作完整代码（C语言）

  四、运行结果

一、链队列

1、链栈的定义：

链队列是一种线性数据结构，采用链表来实现队列的操作。链队列具有队头指针和队尾指针，用于指示队列元素所在的位置。链队列只允许在队尾插入元素，在队头删除元素，符合先进先出（First In First Out，FIFO）的原则。

2、链栈的优缺点：

链队列的优点：

  1. 动态分配空间：链队列使用链表实现，可动态分配和释放空间。因此，不需要预先分配大量存储空间，可以根据实际需求进行空间分配。
  2. 无需移动元素：相比普通队列，链队列在删除元素时无需移动大量元素，只需修改指针即可。这使得链队列在处理大规模数据时具有更高的效率。
  3. 适合处理用户排队等待的情况：链队列适用于处理用户排队等待的情况，例如银行排队、网络请求等。通过链队列，可以快速地插入新用户和删除已处理的用户。

链队列的缺点：

  1. 需要额外的存储空间：为了实现链表结构，链队列需要额外的存储空间来维护指针和节点。这会增加存储空间的消耗。
  2. 插入和删除操作可能引起内存分配和释放：在链队列中插入和删除元素时，可能需要动态分配和释放内存。这会增加操作的时间复杂度，并可能引起内存碎片化问题。
  3. 无法充分利用连续空间的优势：链表结构使得链队列无法像数组一样充分利用连续空间的优势，这会影响空间利用率和访问速度。

二、链队列的基本操作算法（C语言）    

1、宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemtype;
typedef int Status;
  2、创建结构体
//创建结构体
typedef struct QNode {
    QElemtype data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;
3、链栈的初始化 
//链队列的初始化
Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q.front) {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}
4、链队列的入队 
//链队列的入队 
Status EnQueue(LinkQueue &Q, QElemtype e) {
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}
5、链队列的出队
//链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    delete p;
    return OK;

}
6、取链队列的对头元素
//取链列的对头元素 
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;

}
7、链队列的销毁
//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        delete (Q.front);
        Q.front = Q.rear;
    }
//    printf("销毁成功！");
    return OK;
}
8、链队列的清空
//清空
Status ClearQueue(LinkQueue &Q) {
    Q.rear = Q.front->next;
    while (Q.front->next) {
        Q.rear = Q.rear->next;
        delete (Q.front->next);
        Q.front->next = Q.rear;
    }
    Q.rear = Q.front;
//    printf("清空成功！");
    return OK;
}
9、判断链队列是否为空
//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
//        printf("队列为空！\n");
        return true;
    } else {
        return false;
    }
//    printf("该队列不为空！");
}
10、求队列长度
//求队列长度
Status QueueLength(LinkQueue Q) {
    int i = 0;
    while (Q.front != Q.rear) {
        i++;
        Q.front = Q.front->next;
    }
//    printf("该队列长度为：%d", i);
    return i;
}
 11、遍历队列元素
//遍历队列
Status QueueTraverse(LinkQueue Q) {
    QNode *p;
    if (Q.front == Q.rear) {
        return ERROR;
    }
    p = Q.front->next;//存储头元素
    printf("从队头依次读出该队列中的元素值为: ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

三、链队列的基本操作完整代码（C语言）

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

#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemtype;
typedef int Status;

//创建结构体
typedef struct QNode {
    QElemtype data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;

//链队列的初始化
Status InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q.front) {
        exit(OVERFLOW);
    }
    Q.front->next = NULL;
    return OK;
}

//链队列的入队 
Status EnQueue(LinkQueue &Q, QElemtype e) {
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p) {
        exit(OVERFLOW);
    }
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}

//链队列的出队
Status DeQueue(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    delete p;
    return OK;

}

//取链列的对头元素 
Status GetQueueHead(LinkQueue &Q, QElemtype &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.front->next->data;
    return OK;

}


//队列的销毁
Status DestoryQueue(LinkQueue &Q) {
    while (Q.front) {
        Q.rear = Q.front->next;
        delete (Q.front);
        Q.front = Q.rear;
    }
//    printf("销毁成功！");
    return OK;
}

//清空
Status ClearQueue(LinkQueue &Q) {
    Q.rear = Q.front->next;
    while (Q.front->next) {
        Q.rear = Q.rear->next;
        delete (Q.front->next);
        Q.front->next = Q.rear;
    }
    Q.rear = Q.front;
//    printf("清空成功！");
    return OK;
}


//判断是否为空
Status QueueEmpty(LinkQueue &Q) {
    if (Q.front == Q.rear) {
//        printf("队列为空！\n");
        return true;
    } else {
        return false;
    }
//    printf("该队列不为空！");
}

//求队列长度
Status QueueLength(LinkQueue Q) {
    int i = 0;
    while (Q.front != Q.rear) {
        i++;
        Q.front = Q.front->next;
    }
//    printf("该队列长度为：%d", i);
    return i;
}


//遍历队列
Status QueueTraverse(LinkQueue Q) {
    QNode *p;
    if (Q.front == Q.rear) {
        return ERROR;
    }
    p = Q.front->next;//存储头元素
    printf("从队头依次读出该队列中的元素值为: ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}


//功能菜单列表
void show_help() {
    printf("******* 功能菜单列表 *******\n");
    printf("1----入队------------------\n");
    printf("2----求链队列长度----------\n");
    printf("3----出队------------------\n");
    printf("4----取队头元素-------------\n");
    printf("5----清空循环队列-----------\n");
    printf("6----销毁循环队列-----------\n");
    printf("7----判断循环队列是否为空-----\n");
    printf("8----批量插入元素------------\n");
    printf("9----显示队列元素------------\n");
    printf("10----退出------------------\n\n");
}


//主函数
int main() {
    LinkQueue LQ;
    Status reIn = InitQueue(LQ);
    if (reIn == OK) {
        printf("链队列初始时成功  \n");
    } else {
        printf("链队列初始时失败 \n");
    }

    while (1) {

        //功能菜单列表
        show_help();

        int flag;
        printf("请输入所需的功能编号：\n");
        scanf("%d", &flag);

        switch (flag) {
            case 1: {//入队
                Status EnQueueindex;
                printf("请输入插入元素(请在英文状态下输入例如:1): \n");
                scanf("%d", &EnQueueindex);
                Status rEnQueue = EnQueue(LQ, EnQueueindex);
                if (rEnQueue == OK) {
                    printf("向链队列入队%d成功！\n", EnQueueindex);
                } else {
                    printf("向链队列入队失败！\n");
                }
            }
                break;
            case 2: {//求链队列的长度
                int length = QueueLength(LQ);
                printf("链队列的长度为:%d。 \n\n", length);
            }
                break;
            case 3: {//出队
                QElemtype DeElem;
                Status DeEn = DeQueue(LQ, DeElem);
                if (DeEn == OK) {
                    printf("从链队列中出队成功，出队的元素为 %d! \n", DeElem);
                } else {
                    printf("从链队列中出队失败！\n");
                }
            }
                break;
            case 4: {//求队头元素
                QElemtype getEl;
                Status reGet = GetQueueHead(LQ, getEl);
                if (reGet == OK) {
                    printf("从链队列中取对头元素成功，队头元素为:%d! \n", getEl);
                } else {
                    printf("从链队列中取对头元素成功 \n");
                }
            }
                break;
            case 5: { //清空
                Status rClearStack = ClearQueue(LQ);
                if (rClearStack == OK) {
                    printf("链队列清空成功！\n");
                } else {
                    printf("链队列清空失败！\n");
                }
            }
                break;
            case 6: {//销毁
                Status rDestroyStack = DestoryQueue(LQ);
                if (rDestroyStack == OK) {
                    printf("链队列销毁成功！\n");
                } else {
                    printf("链队列销毁失败！\n");
                }
            }
                break;
            case 7: {///判空
                Status ClearStatus = QueueEmpty(LQ);
                if (ClearStatus == true) {
                    printf("链队列为空！\n\n");
                } else {
                    printf("链队列不为空！\n\n");
                }
            }
                break;
            case 8: {//批量插入
                int on;
                printf("请输入想要插入的元素个数：\n");
                scanf("%d", &on);
                QElemtype array[on];
                for (int i = 1; i <= on; i++) {
                    printf("向链队列第%d个位置插入元素为:", i);
                    scanf("%d", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status InsertStatus = EnQueue(LQ, array[i]);
                    if (InsertStatus == OK) {
                        printf("向链队列第%d个位置插入元素%d成功！\n", i, array[i]);
                    } else {
                        printf("向链队列第%d个位置插入元素%d失败！\n", i, array[i]);
                    }
                }
            }
                break;
            case 9: {//输出链表元素
                QueueTraverse(LQ);
//                printf("\n");
            }
                break;
            case 10: {//退出程序
                return 0;
            }
                break;
            default: {
                printf("输入错误，无此功能，请检查输入:\n\n");
            }
        }
    }


    return 1;
}

  四、运行结果

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/345910.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Minio 判断对象是否存在

Minio 判断对象是否存在

引 Minio数据模型 中描述了 MinIO 中什么是桶&#xff0c;什么是对象&#xff0c;也给出了操作桶和操作对象的API。 在 MinIO 中&#xff0c; 对象 中间前缀 对象名称 。如何判定对象是否存在呢&#xff1f; 分析 在 MinIO 中并没有提供判断对象是否存在的操作&#xff…
阅读更多...
leetcode:排序链表(递归)

leetcode:排序链表(递归)

题目&#xff1a; 给定链表的头结点 head &#xff0c;请将其按 升序 排列并返回 排序后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [4,2,1,3] 输出&#xff1a;[1,2,3,4]示例 2&#xff1a; 输入&#xff1a;head [-1,5,3,4,0] 输出&#xff1a;[-1,0,3,4,5]示例…
阅读更多...
【原创】linux为什么不是实时操作系统

【原创】linux为什么不是实时操作系统

文章目录 一、什么是实时操作系统&#xff08;RTOS&#xff09;&#xff1f;二、linux为什么不是实时操作系统&#xff1f;中断响应时间中断处理时间任务调度时间1、No Forced Preemption(Server)2、Voluntary Kernel Preemption(Desktop)3、Preemptible Kernel(Low-Latency De…
阅读更多...
yarn集群HDFS datanode无法启动问题排查

yarn集群HDFS datanode无法启动问题排查

一、问题场景 hdfs无法访问&#xff0c;通过jps命令查看进程&#xff0c;发现namenode启动成功&#xff0c;但是所有datanode都没有启动&#xff0c;重启集群&#xff08;start-dfs.sh&#xff09;后仍然一样 二、原因分析 先看下启动的日志有无报错。打开Hadoop的日志目录 …
阅读更多...
Java实现考研专业课程管理系统 JAVA+Vue+SpringBoot+MySQL

Java实现考研专业课程管理系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 考研高校模块2.3 高校教师管理模块2.4 考研专业模块2.5 考研政策模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 考研高校表3.2.2 高校教师表3.2.3 考研专业表3.2.4 考研政策表 四、系统展示五、核…
阅读更多...
系统登录的时候的密码如何做到以加密的形式进行登录【java.security包下的api】工具类。

系统登录的时候的密码如何做到以加密的形式进行登录【java.security包下的api】工具类。

/** description: 将普通的publicKey转化得到一个RSAPublicKey* author: zkw* date: 2024/1/24 16:17* param: publicKey 普通的publicKey* return: RSAPublicKey 得到一个新的RSAPublicKey**/public static RSAPublicKey getPublicKey(String publicKey) throws NoSuchAlgorit…
阅读更多...
【进阶之路】如何提升 Java 编程内力？

【进阶之路】如何提升 Java 编程内力？

如何提升 Java 编程内力&#xff1f; 可能很多初学者在学完 SpringBoot 之后&#xff0c;做了 1-2 个项目之后&#xff0c;不知道该去学习什么了&#xff0c;其实这时候需要去学习的东西还有很多&#xff0c;接下来我会列举一下主要需要从哪些方面来对 Java 编程深入学习&#…
阅读更多...
C++补充篇- C++11 及其它特性

C++补充篇- C++11 及其它特性

目录 explicit 关键字 左值和右值的概念 函数返回值当引用 C11 新增容器 - array C的类型转换 static_cast reinterpret_cast dynamic_cast const_cast C智能指针 auto_ptr 使用详解 (C98) unique_ptr 使用详解 (C11) auto_ptr的弊端 unique_ptr严谨auto_ptr的弊端 unique_…
阅读更多...
网安培训第二期——sql注入+中间件+工具

网安培训第二期——sql注入+中间件+工具

文章目录 宽字节注入插入注入二次注入PDO模式(动态靶机&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;&#xff01;)sql注入读取文件sql注入导出文件linux命令 10.12笔记sqlmapsqlmap参数 10.13笔记sqlmap 文件读写前后缀常用tamper及适用场景 10.…
阅读更多...
SpringMVC-RESTFul

SpringMVC-RESTFul

文章目录 RESTFul一、基础概念二、增删改查1.查询全部用户信息 &#xff08;GET&#xff09;2.根据id查询用户信息3.添加用户&#xff08;POST&#xff09;4.修改用户 &#xff08;PUT&#xff09;5.删除用户 &#xff08;DELETE&#xff09; RESTFul 一、基础概念 二、增删改…
阅读更多...
Qt Designer教程

Qt Designer教程

文章目录 创建一个 ui 文件选择控件Qt Designer基本控件介绍1、Layouts1.1、Layouts 布局1.2、参数配置 2、Spacers2.1、 Spacers 弹簧介绍2.2、 参数设置 3、Buttons 按键3.1、 Buttons 按键分类 4、Item Views&#xff08;Model-Based&#xff09; 项目视图(基于模型)4.1、 B…
阅读更多...
高质量简历模板网站，免费、免费、免费

高质量简历模板网站，免费、免费、免费

你们在制作简历时&#xff0c;是不是基本只关注两件事&#xff1a;简历模板&#xff0c;还有基本信息的填写。 当你再次坐下来更新你的简历时&#xff0c;可能会发现自己不自觉地选择了那个“看起来最好看的模板”&#xff0c;填写基本信息&#xff0c;却没有深入思考如何使简历…
阅读更多...
shell脚本基础之条件语句详解

shell脚本基础之条件语句详解

目录 一、条件语句 1、测试 1.1 测试判断 ​1.2 比较整数数值 1.3 字符串比较 1.4 双中括号的用法 1.5 () 与 {} 的用法及区别 2、if语句 2.1 单分支if语句 2.2 双分支if语句 2.3 多分支if语句 2.4 shell脚本的if语句案例 案例一 案例二 案例三 案例四 案例五…
阅读更多...
c++day1作业

c++day1作业

思维导图 提示并输入一个字符串&#xff0c;统计该字符中大写、小写字母个数、数字个数、空格个数以及其他字符个数 要求使用C风格字符串完成 #include <iostream> #include <iomanip> using namespace std; int main() {string a;cout<<"输入一个字符…
阅读更多...
vue3-深入组件-组件注册和props更多细节

vue3-深入组件-组件注册和props更多细节

组件注册 定义好的组件需要注册才能被使用。 注册方式有两种 全局注册 局部注册 全局注册 .component() 方法&#xff0c;让组件在当前 Vue 应用中全局可用。 在 main.ts 中 import ./assets/main.cssimport { createApp } from vue import { createPinia } from pinia i…
阅读更多...
一带一路暨金砖国家技能发展国际联盟大数据和人工智能专业委员会名单

一带一路暨金砖国家技能发展国际联盟大数据和人工智能专业委员会名单

四川城市职业学院和陈老师在序号&#xff1a;158&#xff0c;300 一带一路暨金砖国家技能发展国际联盟大数据和人工智能专业委员会名单 各相关单位&#xff1a; 一带一路暨金砖国家技能发展国际联盟大数据和人工智能专业委员会于2023年11月12日正式成立。经各单位申请、大数据…
阅读更多...
kafka-顺序消息实现

kafka-顺序消息实现

kafka-顺序消息实现 场景 在购物付款的时候&#xff0c;订单会有不同的订单状态&#xff0c;对应不同的状态事件&#xff0c;比如&#xff1a;待支付&#xff0c;支付成功&#xff0c;支付失败等等&#xff0c;我们会将这些消息推送给消息队列 &#xff0c;后续的服务会根据订…
阅读更多...
数据的存储结构

数据的存储结构

1.类别 顺序存储、链式存储、散列存储、索引存储 2.顺序存储与链式存储的区别 顺序存储链式存储优点 可以实现随机存取每个元素占用最少的空间 充分利用所有存储单元&#xff0c;不会出现碎片现象。缺点 只能使用整块的存储单元&#xff0c;会产出较多的碎片。 需要额外的存…
阅读更多...
12.for 条件循环语句 （3）

12.for 条件循环语句 （3）

for 循环语句 允许脚本一次性读取多个信息&#xff0c;然后逐一对信息进行操作处理。当要处理的数据有范围时&#xff0c;使用for循环语句。 使用 for 循环语句从列表文件中读取多个用户名&#xff0c;然后为其逐一创建用户账户并设 置密码。首先创建用户名称的列表文件users.…
阅读更多...
Linux浅学笔记02

Linux浅学笔记02

目录 grep-wc-管道符 echo-tail-重定向符 vi编辑器 grep-wc-管道符 grep命令(过滤文件内容) //更准确的来说&#xff0c;是筛选包括“所需字符”的一句内容或多句内容。 语法&#xff1a;grep [-n] 关键字 文件路径 //-n&#xff1a;可选&#xff0c;表示在结果中匹配的行…
阅读更多...
最新文章

Copyright @ 2022~2023