社区导航

 

搜索
查看: 719|回复: 13

[讨论] 【CODING TALK】你会怎么实现队列

[复制链接]

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

发表于 2019-3-5 02:33 | 显示全部楼层 |阅读模式
本帖最后由 辛昕 于 2019-3-19 00:54 编辑

我已经习惯性忘记开过坑这件事情了 。
不过事实上,我的确按照自己的想法实现了一个 “通用的” 队列。
另外,我还在它的基础上,做了一个 二重队列,我实现它是因为我经常要把串口通信缓冲起来,再配合
一个简单的 字符检测器的 有限状态机 做帧判断。
简单起见,我先把我这个 osc git的项目地址贴上来


必须说,队列(Queue)虽然是一个很有用的基础ADT,但是,就基本功能而言,它的实现却是十分简单的。
比如我自己实现的一个版本。
(我是根据 《C语言算法描述》这本书的相关章节中的定义 实现的)

头文件定义
  1. struct QueueRecord;
  2. typedef struct QueueRecord *Queue;
  3. typedef struct QueueRecord  QueueStruct;

  4. typedef unsigned char  Element;
  5. typedef short QRange;

  6. struct QueueRecord
  7. {
  8.      QRange capacity;
  9.      QRange front;
  10.      QRange rear;
  11.      QRange size;
  12.      Element *array;
  13. };

  14. void Queue_MakeEmpty(Queue Q);
  15. void Queue_Create(Queue Q,Element *Array,QRange MaxElement);
  16. int isQueueFull(Queue Q);
  17. void Enqueue(Queue Q,Element X);
  18. int isQueueEmpty(Queue Q);
  19. Element Dequeue(Queue Q);

  20. QRange NextPosition(QRange pos,QRange Range);
复制代码



源文件实现
  1. QRange NextPosition(QRange Pos,QRange Range)
  2. {
  3.     if( (++Pos) == Range)
  4.           Pos = 0;
  5.    
  6.     return Pos;
  7. }

  8. void Queue_MakeEmpty(Queue Q)
  9. {
  10.     Q->front = 1;
  11.     Q->rear = 0;
  12.         Q->size = 0;
  13. }

  14. void Queue_Create(Queue Q,Element *Array,QRange MaxElement)
  15. {
  16.         Q->capacity = MaxElement;
  17.         Q->array = Array;
  18.         Queue_MakeEmpty(Q);
  19. }

  20. int isQueueFull(Queue Q)
  21. {
  22.     return (Q->size == Q->capacity);
  23. }

  24. int isQueueEmpty(Queue Q)
  25. {
  26.     return (Q->size == 0);
  27. }        

  28. void Enqueue(Queue Q,Element X)
  29. {   
  30.     if(isQueueFull(Q))
  31.         return;
  32.    
  33.     Q->rear = NextPosition(Q->rear,Q->capacity);
  34.     Q->array[Q->rear] = X;
  35.     Q->size++;
  36. }

  37. // 队列空时,返回值未定义;
  38. Element Dequeue(Queue Q)
  39. {
  40.       Element x;
  41.       
  42.       if(isQueueEmpty(Q))
  43.           return 0xff;
  44.       
  45.       x = Q->array[Q->front];
  46.       Q->front = NextPosition(Q->front,Q->capacity);
  47.       Q->size--;
  48.       
  49.       return x;
  50. }
复制代码




来源:EEWorld 编程基础板块,转载请附上链接

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-5 02:35 | 显示全部楼层
没骗你吧。
加上头文件,还有我强迫症的缩进和空格,整个实现不足100行。

其实这个东西本来没什么纠结的。

上面这个实现,我个人使用了很久,也一直很满意。
而且,从我类似强迫症的名字中你可能看出来了,我把这个东西当成一个基础部件在使用。

事实上,只要用宏,或者 typedef 重定义 Element,这个实现的确是 准通用的。

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-5 02:43 | 显示全部楼层
但事实上,它还真的并不是真正意义上的通用。

为啥呢?
我给你看我的文件夹截图
无标题.png
这个 U8_libQueue.h 为毛头文件名字这么别扭呢?
其实,别扭就别扭在 Element这个地方。

具体来说是这一句

  1. typedef unsigned char  Element;
  2. typedef short QRange;
复制代码



并不是所有时候,Element都是char——虽然作为串口之类的通信缓冲,其实百分之九十九。
但因为这个功能过于简单,也过于基础,所以我很希望把它做成通用。

通用到什么程度呢?

在我的认知里,除了最没品的复制之外,有两种层次的通用:
1.代码几乎不用改——比如我的这个实现,只需要稍微修改一下 Element;
2.直接编译成库,使用的时候,不需要也无法修改。

但是第一种实现,其实有个缺陷。
假设以下这种情形。
在你的代码里,有两个地方需要队列。
第一个地方,Element是char,第二个地方,Element是一个之定义的结构体。

你完全可以想象,这个时候,它的不通用性就暴露出来了。

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-5 02:44 | 显示全部楼层
所以,真正意义上的通用,只有做成 不需要也无法修改的 .a/.lib文件,直接调用。

但是,这里,会遇到第一个难题,就是如何处理 Element。
(这里留一个钩子:我踩你第一反应也会想到 void *,和我一样,那,好吧,试试
实现,至少我就发现没我想的那么完美~~)

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-5 02:46 | 显示全部楼层
事实上,我大半夜不好好睡觉,已经想出了三四种不同形式的实现方式。

不过说实话,我觉得,对于这个不足100行就可以实现的简单功能,这样做已经有点高射炮打蚊子了。

已经失去了实际意义,不值得我再浪费干正经事的时间。

不过,我转念一想,如果退一步,把编程技艺,当成一种像琴棋书画一般的爱好,那么,就让我一天写一种实现方式,并简要分析其给接口和使用带来的方便与麻烦~~~

老规矩,这个问题,我会晾它一两天,等待你的回复。

答地好的,斑斑将选取其中最好的3个回复,一人送500芯币。

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

110

TA的帖子

0

TA的资源

宇宙尘埃

发表于 2019-3-5 15:16 | 显示全部楼层
开发累哟!

回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-12 02:12 | 显示全部楼层

哭啥呢。

点评

补充一下我上学学习的数据结构用的是PASCAL语言来描述的。教材是清华大学教授“严老太太”写的。  详情 回复 发表于 2019-3-19 17:59

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

748

TA的帖子

2

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2019-3-18 08:21 | 显示全部楼层
本身数据结构的实现就有两种内存结构,第一是:数组,二是:链表。在单片机这种环境下,我推荐数组。数组是可控的结构,不易出错。
当然,也可以使用硬件结构的队列。

点评

额,我发现你的认知里有几个很严重的混淆 首先,所谓数据结构,其实分很多种,不过我猜测你想说的是 不管是 队列,栈,或者 树这些基础的数据结构的实现,都有两种内存组织方式 一种是数组,一种是链表。 但  详情 回复 发表于 2019-3-19 00:51

回复

使用道具 举报

7870

TA的帖子

54

TA的资源

裸片初长成(中级)

Rank: 11Rank: 11Rank: 11Rank: 11

荣誉会员勋章

 楼主| 发表于 2019-3-19 00:51 | 显示全部楼层
bigbat 发表于 2019-3-18 08:21
本身数据结构的实现就有两种内存结构,第一是:数组,二是:链表。在单片机这种环境下,我推荐数组。数组是 ...

额,我发现你的认知里有几个很严重的混淆
首先,所谓数据结构,其实分很多种,不过我猜测你想说的是

不管是 队列,栈,或者 树这些基础的数据结构的实现,都有两种内存组织方式
一种是数组,一种是链表。

但其实,就某种观点而言。
表,是最基础的一种数据结构之一,另外两种才是队列 和 栈
他们的区别是 进出顺序。

而数组和链表才是表的两种最常见的实现方式。
数组可以说是线性表,链表则不是,因为它的内存不一定是连续的。

我并不觉得,单片机环境下,数组比链表安全。
我想,你大概是把 链表的实现认为是必须有 malloc/free这个堆上内存分配功能。
如果是这样,不带OS的单片机裸机C编程环境的确不安全。

但实际上,链表还有另一种 游标实现方案。
完全不需要堆上分配内存。
也是一种静态数组方案。

如有兴趣, 可以看我之前上传的一本
《数据结构和算法:C语言描述》
作者是 M.K.Allen

点评

我的回复被挡了,我说的数据结构就是指的ADT  详情 回复 发表于 2019-3-19 17:53

八年一梦,洗尽铅华,重头再来


回复

使用道具 举报

748

TA的帖子

2

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2019-3-19 17:35 | 显示全部楼层
我这话说的很严密“本身数据结构的实现就有两种内存结构,第一是:数组,二是:链表。”我说的数据结构就是指的ADT(抽象数据结构)。而且,我说的是内存结构!
不知道你了解了没有。ADT的词条释义来自于“维基百科”,不是骗子网站哦!

回复

使用道具 举报

748

TA的帖子

2

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2019-3-19 17:47 | 显示全部楼层
给你的建议是C语言的数据结构库不是没人做不出来,而是这个没有太大的意义。你看为什么C++有STL,而C语言没有呢?可能你会觉得C可以调用C++的库,就没有必要了是吧!
C和C++就不是一种语言。对于单片机等内存受限的设备,C语言的标准库更是没有必要。
顺便说一下,你做的库能不能在操作系统下用的呢,换个简单的说法是能不能支持“多线索”,有人也称“多线程”。

回复

使用道具 举报

748

TA的帖子

2

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2019-3-19 17:53 | 显示全部楼层
辛昕 发表于 2019-3-19 00:51
额,我发现你的认知里有几个很严重的混淆
首先,所谓数据结构,其实分很多种,不过我猜测你想说的是

...

我的回复被挡了,我说的数据结构就是指的ADT

回复

使用道具 举报

748

TA的帖子

2

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2019-3-19 17:59 | 显示全部楼层

补充一下我上学学习的数据结构用的是PASCAL语言来描述的。教材是清华大学教授“严老太太”写的。

回复

使用道具 举报

40

TA的帖子

0

TA的资源

一粒金砂(中级)

Rank: 2

发表于 2019-9-28 13:57 | 显示全部楼层

我见过一种实现,好像是使用了数组来实现队列,但是当队列要满的时候,把数组的SIZE*2;当元素出队,导致总长只有当前的1/4的时候,把数组的SIZE/2。

小题目也是可以高出不同的精彩点


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

关闭

站长推荐上一条 /6 下一条

  • 论坛活动 E手掌握

    扫码关注
    EEWORLD 官方微信

  • EE福利  唾手可得

    扫码关注
    EE福利 唾手可得

Archiver|手机版|小黑屋|电子工程世界 ( 京ICP证 060456 )

GMT+8, 2019-10-15 06:50 , Processed in 0.389713 second(s), 18 queries , Gzip On, MemCache On.

快速回复 返回顶部 返回列表