开发者社区 开发与运维 文章 正文

队列的实现

2013-10-25 784
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一、顺序队列 [cpp] view plaincopy     typedef  int QElemType;         // c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列)    #define MAXQSIZE 5 // 最大队列长度(对于循环...

一、顺序队列

[cpp] view plain copy
  1.    
  2. typedef  int QElemType;  
  3.    
  4.   // c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列)  
  5.  #define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1)  
  6.  struct SqQueue  
  7.  {  
  8.    QElemType *base; // 初始化的动态分配存储空间  
  9.    int front; // 头指针,若队列不空,指向队列头元素  
  10.    int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置  
  11.  };  
  12.    
  13.  // bo3-4.cpp 顺序队列(非循环,存储结构由c3-3.h定义)的基本操作(9个)  
  14.  Status InitQueue(SqQueue &Q)  
  15.  { // 构造一个空队列Q  
  16.    Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));  
  17.    if(!Q.base) // 存储分配失败  
  18.      exit(OVERFLOW);  
  19.    Q.front=Q.rear=0;  
  20.    return OK;  
  21.  }  
  22.   
  23.  Status DestroyQueue(SqQueue &Q)  
  24.  { // 销毁队列Q,Q不再存在  
  25.    if(Q.base)  
  26.      free(Q.base);  
  27.    Q.base=NULL;  
  28.    Q.front=Q.rear=0;  
  29.    return OK;  
  30.  }  
  31.   
  32.  Status ClearQueue(SqQueue &Q)  
  33.  { // 将Q清为空队列  
  34.    Q.front=Q.rear=0;  
  35.    return OK;  
  36.  }  
  37.   
  38.  Status QueueEmpty(SqQueue Q)  
  39.  { // 若队列Q为空队列,则返回TRUE,否则返回FALSE  
  40.    if(Q.front==Q.rear) // 队列空的标志  
  41.      return TRUE;  
  42.    else  
  43.      return FALSE;  
  44.  }  
  45.   
  46.  int QueueLength(SqQueue Q)  
  47.  { // 返回Q的元素个数,即队列的长度  
  48.    return(Q.rear-Q.front);  
  49.  }  
  50.   
  51.  Status GetHead(SqQueue Q,QElemType &e)  
  52.  { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
  53.    if(Q.front==Q.rear) // 队列空  
  54.      return ERROR;  
  55.    e=*(Q.base+Q.front);  
  56.    return OK;  
  57.  }  
  58.   
  59.  Status EnQueue(SqQueue &Q,QElemType e)  
  60.  { // 插入元素e为Q的新的队尾元素  
  61.    if(Q.rear>=MAXQSIZE)  
  62.    { // 队列满，增加1个存储单元  
  63.      Q.base=(QElemType *)realloc(Q.base,(Q.rear+1)*sizeof(QElemType));  
  64.      if(!Q.base) // 增加单元失败  
  65.        return ERROR;  
  66.    }  
  67.    *(Q.base+Q.rear)=e;  
  68.    Q.rear++;  
  69.    return OK;  
  70.  }  
  71.   
  72.  Status DeQueue(SqQueue &Q,QElemType &e)  
  73.  { // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR  
  74.    if(Q.front==Q.rear) // 队列空  
  75.      return ERROR;  
  76.    e=Q.base[Q.front];  
  77.    Q.front=Q.front+1;  
  78.    return OK;  
  79.  }  
  80.   
  81.  Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))  
  82.  { // 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败  
  83.    int i;  
  84.    i=Q.front;  
  85.    while(i!=Q.rear)  
  86.    {  
  87.      vi(*(Q.base+i));  
  88.      i++;  
  89.    }  
  90.    printf("\n");  
  91.    return OK;  
  92.  }  


二、链队列

[cpp] view plain copy
  1. typedef int QElemType;  
  2.   
  3. // c3-2.h 单链队列－－队列的链式存储结构  
  4. typedef struct QNode  
  5. {  
  6.   QElemType data;  
  7.   QNode *next;  
  8. }*QueuePtr;  
  9.   
  10. struct LinkQueue  
  11. {  
  12.   QueuePtr front,rear; // 队头、队尾指针  
  13. };  
  14.   
  15.   
  16. // bo3-2.cpp 链队列(存储结构由c3-2.h定义)的基本操作(9个)  
  17. Status InitQueue(LinkQueue &Q)  
  18. { // 构造一个空队列Q  
  19.   if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))  
  20.     exit(OVERFLOW);  
  21.   Q.front->next=NULL;  
  22.   return OK;  
  23. }  
  24.   
  25. Status DestroyQueue(LinkQueue &Q)  
  26. { // 销毁队列Q(无论空否均可)  
  27.   while(Q.front)  
  28.   {  
  29.     Q.rear=Q.front->next;  
  30.     free(Q.front);  
  31.     Q.front=Q.rear;  
  32.   }  
  33.   return OK;  
  34. }  
  35.   
  36. Status ClearQueue(LinkQueue &Q)  
  37. { // 将Q清为空队列  
  38.   QueuePtr p,q;  
  39.   Q.rear=Q.front;  
  40.   p=Q.front->next;  
  41.   Q.front->next=NULL;  
  42.   while(p)  
  43.   {  
  44.     q=p;  
  45.     p=p->next;  
  46.     free(q);  
  47.   }  
  48.   return OK;  
  49. }  
  50.   
  51. Status QueueEmpty(LinkQueue Q)  
  52. { // 若Q为空队列,则返回TRUE,否则返回FALSE  
  53.   if(Q.front==Q.rear)  
  54.     return TRUE;  
  55.   else  
  56.     return FALSE;  
  57. }  
  58.   
  59. int QueueLength(LinkQueue Q)  
  60. { // 求队列的长度  
  61.   int i=0;  
  62.   QueuePtr p;  
  63.   p=Q.front;  
  64.   while(Q.rear!=p)  
  65.   {  
  66.     i++;  
  67.     p=p->next;  
  68.   }  
  69.   return i;  
  70. }  
  71.   
  72. Status GetHead(LinkQueue Q,QElemType &e)  
  73. { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
  74.   QueuePtr p;  
  75.   if(Q.front==Q.rear)  
  76.     return ERROR;  
  77.   p=Q.front->next;  
  78.   e=p->data;  
  79.   return OK;  
  80. }  
  81.   
  82. Status EnQueue(LinkQueue &Q,QElemType e)  
  83. { // 插入元素e为Q的新的队尾元素  
  84.   QueuePtr p;  
  85.   if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败  
  86.     exit(OVERFLOW);  
  87.   p->data=e;  
  88.   p->next=NULL;  
  89.   Q.rear->next=p;  
  90.   Q.rear=p;  
  91.   return OK;  
  92. }  
  93.   
  94. Status DeQueue(LinkQueue &Q,QElemType &e)  
  95. { // 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR  
  96.   QueuePtr p;  
  97.   if(Q.front==Q.rear)  
  98.     return ERROR;  
  99.   p=Q.front->next;  
  100.   e=p->data;  
  101.   Q.front->next=p->next;  
  102.   if(Q.rear==p)  
  103.     Q.rear=Q.front;  
  104.   free(p);  
  105.   return OK;  
  106. }  
  107.   
  108. Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType))  
  109. { // 从队头到队尾依次对队列Q中每个元素调用函数vi()。一旦vi失败,则操作失败  
  110.   QueuePtr p;  
  111.   p=Q.front->next;  
  112.   while(p)  
  113.   {  
  114.     vi(p->data);  
  115.     p=p->next;  
  116.   }  
  117.   printf("\n");  
  118.   return OK;  
  119. }  

 

三、循环队列

[cpp] view plain copy
    1. // c3-3.h 队列的顺序存储结构(可用于循环队列和非循环队列)  
    2. #define MAXQSIZE 5 // 最大队列长度(对于循环队列，最大队列长度要减1)  
    3. struct SqQueue  
    4. {  
    5.   QElemType *base; // 初始化的动态分配存储空间  
    6.   int front; // 头指针,若队列不空,指向队列头元素  
    7.   int rear; // 尾指针,若队列不空,指向队列尾元素的下一个位置  
    8. };  
    9.   
    10. // bo3-3.cpp 循环队列(存储结构由c3-3.h定义)的基本操作(9个)  
    11. Status InitQueue(SqQueue &Q)  
    12. { // 构造一个空队列Q  
    13.   Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));  
    14.   if(!Q.base) // 存储分配失败  
    15.     exit(OVERFLOW);  
    16.   Q.front=Q.rear=0;  
    17.   return OK;  
    18. }  
    19.   
    20. Status DestroyQueue(SqQueue &Q)  
    21. { // 销毁队列Q,Q不再存在  
    22.   if(Q.base)  
    23.     free(Q.base);  
    24.   Q.base=NULL;  
    25.   Q.front=Q.rear=0;  
    26.   return OK;  
    27. }  
    28.   
    29. Status ClearQueue(SqQueue &Q)  
    30. { // 将Q清为空队列  
    31.   Q.front=Q.rear=0;  
    32.   return OK;  
    33. }  
    34.   
    35. Status QueueEmpty(SqQueue Q)  
    36. { // 若队列Q为空队列,则返回TRUE,否则返回FALSE  
    37.   if(Q.front==Q.rear) // 队列空的标志  
    38.     return TRUE;  
    39.   else  
    40.     return FALSE;  
    41. }  
    42.   
    43. int QueueLength(SqQueue Q)  
    44. { // 返回Q的元素个数,即队列的长度  
    45.   return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;  
    46. }  
    47.   
    48. Status GetHead(SqQueue Q,QElemType &e)  
    49. { // 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR  
    50.   if(Q.front==Q.rear) // 队列空  
    51.     return ERROR;  
    52.   e=*(Q.base+Q.front);  
    53.   return OK;  
    54. }  
    55.   
    56. Status EnQueue(SqQueue &Q,QElemType e)  
    57. { // 插入元素e为Q的新的队尾元素  
    58.   if((Q.rear+1)%MAXQSIZE==Q.front) // 队列满  
    59.     return ERROR;  
    60.   Q.base[Q.rear]=e;  
    61.   Q.rear=(Q.rear+1)%MAXQSIZE;  
    62.   return OK;  
    63. }  
    64.   
    65. Status DeQueue(SqQueue &Q,QElemType &e)  
    66. { // 若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR  
    67.   if(Q.front==Q.rear) // 队列空  
    68.     return ERROR;  
    69.   e=Q.base[Q.front];  
    70.   Q.front=(Q.front+1)%MAXQSIZE;  
    71.   return OK;  
    72. }  
    73.   
    74. Status QueueTraverse(SqQueue Q,void(*vi)(QElemType))  
    75. { // 从队头到队尾依次对队列Q中每个元素调用函数vi().一旦vi失败,则操作失败  
    76.   int i;  
    77.   i=Q.front;  
    78.   while(i!=Q.rear)  
    79.   {  
    80.     vi(*(Q.base+i));  
    81.     i=(i+1)%MAXQSIZE;  
    82.   }  
    83.   printf("\n");  
    84.   return OK;  
    85. } 

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。

文章标签：
存储
C++
heyonggang0811
目录
相关文章
CamilleKing
|
网络协议 安全 5G
网络与通信原理
【10月更文挑战第14天】网络与通信原理涉及众多方面的知识，从信号处理到网络协议，从有线通信到无线通信，从差错控制到通信安全等。深入理解这些原理对于设计、构建和维护各种通信系统至关重要。随着技术的不断发展，网络与通信原理也在不断演进和完善，为我们的生活和工作带来了更多的便利和创新。
CamilleKing
462 58
dotNative
|
Ubuntu 持续交付 API
如何使用 dotnet pack 打包 .NET 跨平台程序集？
`dotnet pack` 是 .NET Core 的 NuGet 包打包工具，用于将代码打包成 NuGet 包。通过命令 `dotnet pack` 可生成 `.nupkg` 文件。使用 `--include-symbols` 和 `--include-source` 选项可分别创建包含调试符号和源文件的包。默认情况下，`dotnet pack` 会先构建项目，可通过 `--no-build` 跳过构建。此外，还可以使用 `--output` 指定输出目录、`-c` 设置配置等。示例展示了创建类库项目并打包的过程。更多详情及命令选项，请参考官方文档。
dotNative
835 12
技术内容小助手
|
11月前
|
人工智能 运维 API
PAI企业级能力升级：应用系统构建、高效资源管理、AI治理
PAI平台针对企业用户在AI应用中的复杂需求，提供了全面的企业级能力。涵盖权限管理、资源分配、任务调度与资产管理等模块，确保高效利用AI资源。通过API和SDK支持定制化开发，满足不同企业的特殊需求。典型案例中，某顶尖高校基于PAI构建了融合AI与HPC的科研计算平台，实现了作业、运营及运维三大中心的高效管理，成功服务于校内外多个场景。
技术内容小助手
478 0
API小知识
|
搜索推荐 数据挖掘 双11
淘宝运营进阶秘籍：从业余到专业
淘宝运营涉及市场分析、产品定位、店铺装修、营销推广、客户服务、数据分析等多环节。要脱颖而出，需掌握进阶秘籍。本文从精准定位、店铺装修、定价策略、流量获取、客户服务、数据分析及跨平台合作七大方面深入探讨，助商家实现从平凡到卓越的蜕变。通过目标受众分析、优化店铺形象、合理定价、多种促销手段、提升客户体验、利用数据反馈调整策略以及拓展销售渠道，商家可逐步提升运营能力，在竞争激烈的电商环境中取得成功。
API小知识
1529 4
叫个什么名字
|
关系型数据库 MySQL PHP
PHP与MySQL的无缝集成：构建动态网站的艺术####
本文将深入探讨PHP与MySQL如何携手合作，为开发者提供一套强大的工具集，以构建高效、动态且用户友好的网站。不同于传统的摘要概述，本文将以一个生动的案例引入，逐步揭示两者结合的魅力所在，最终展示如何通过简单几步实现数据驱动的Web应用开发。 ####
叫个什么名字
139 6
游客mldfis24krfue
|
监控 Ubuntu Linux
在Linux中，如何使用top和htop命令?
在Linux中，如何使用top和htop命令?
游客mldfis24krfue
426 0
qtuzunbex43fk
|
弹性计算 大数据 测试技术
2024年阿里云服务器新购、续费、升级优惠信息整理汇总
随着云计算技术的深入普及，越来越多的企业和个人选择阿里云作为他们的云服务提供商。然而，续费成本往往成为用户考虑的重要因素。为了帮助用户更经济地续费，阿里云推出了一系列优惠活动和代金券。2024年阿里云服务器优惠活动，轻量2核2G3M服务器61元一年、2核4G4M带宽165元1年，云服务器4核16G10M带宽26元1个月、149元半年，阿里云ECS云服务器2核2G3M新老用户均可99元一年续费不涨价，企业用户2核4G5M带宽199元一年
qtuzunbex43fk
3153 2
小蜗牛耶
|
JavaScript Java 测试技术
基于Java的电竞交互管理系统的设计与实现(源码+lw+部署文档+讲解等)
基于Java的电竞交互管理系统的设计与实现(源码+lw+部署文档+讲解等)
小蜗牛耶
144 0
基于Java的电竞交互管理系统的设计与实现(源码+lw+部署文档+讲解等)
花落已飘
|
存储 C语言
C语言基础教程（fgets和fputs)
C语言基础教程（fgets和fputs)
花落已飘
362 0

热门文章

最新文章

  • 1
    【YOLOv8训练结果评估】YOLOv8如何使用训练好的模型对验证集进行评估及评估参数详解
  • 2
    Android ADB命令大全(通过ADB命令查看wifi密码、MAC地址、设备信息、操作文件、查看文件、日志信息、卸载、启动和安装APK等)
  • 3
    datagrip2022最新版安装破解与激活教程，亲测可用
  • 4
    ETL工具 kettle
  • 5
    漂亮又好用的Redis可视化客户端汇总
  • 6
    MySQL数据库基础：JSON函数各类操作一文详解
  • 7
    JDK5.0新特性系列---8.泛型编程
  • 8
    html常见兼容性问题？
  • 9
    公路（最小生成树）
  • 10
    具备这3种特质 才能称的上是一个好的 Exploit Kit
  • 1
    一个 .NET 开源免费、功能强大的 UI 自动化库
    34
  • 2
    国产芯片生态：从设计到量产，到底难在哪？
    40
  • 3
    ASP.NET Core 依赖注入的三种服务生命周期
    32
  • 4
    灰度不是赌命：我为什么开始用 AI 帮我“决定要不要继续发版”
    54
  • 5
    别再把 K8s 当大号 Docker 了：我用 Kubernetes 跑数据任务踩过的那些坑
    37
  • 6
    阿里云无影云手机快速入门及使用流程（图文教程）
    41
  • 7
    基于 YOLOv8 的智能火灾识别系统设计与实现— 从数据集训练到 PyQt5 可视化部署的完整工程实践
    50
  • 8
    机器学习时间特征处理：循环编码（Cyclical Encoding）与其在预测模型中的应用
    33
  • 9
    《告别无效等待：大规模第三方库项目的快速增量构建指南》
    19
  • 10
    《从视觉到听觉：游戏状态信息的屏幕阅读器适配底层逻辑》
    24

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    基于Python+Vue开发的口腔牙科预约管理系统