【CODING TALK】你会怎么实现队列

辛昕

【CODING TALK】你会怎么实现队列 [复制链接]

 

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

链接已隐藏，如需查看请登录或者注册

贴上来


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

头文件定义

1. struct QueueRecord;
   
2. typedef struct QueueRecord *Queue;
   
3. typedef struct QueueRecord  QueueStruct;
   
4. 
   
5. typedef unsigned char  Element;
   
6. typedef short QRange;
   
7. 
   
8. struct QueueRecord
   
9. {
   
10.      QRange capacity;
    
11.      QRange front;
    
12.      QRange rear;
    
13.      QRange size;
    
14.      Element *array;
    
15. };
    
16. 
    
17. void Queue_MakeEmpty(Queue Q);
    
18. void Queue_Create(Queue Q,Element *Array,QRange MaxElement);
    
19. int isQueueFull(Queue Q);
    
20. void Enqueue(Queue Q,Element X);
    
21. int isQueueEmpty(Queue Q);
    
22. Element Dequeue(Queue Q);
    
23. 
    
24. 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. 
   
9. void Queue_MakeEmpty(Queue Q)
   
10. {
    
11.     Q->front = 1;
    
12.     Q->rear = 0;
    
13.         Q->size = 0;
    
14. }
    
15. 
    
16. void Queue_Create(Queue Q,Element *Array,QRange MaxElement)
    
17. {
    
18.         Q->capacity = MaxElement;
    
19.         Q->array = Array;
    
20.         Queue_MakeEmpty(Q);
    
21. }
    
22. 
    
23. int isQueueFull(Queue Q)
    
24. {
    
25.     return (Q->size == Q->capacity);
    
26. }
    
27. 
    
28. int isQueueEmpty(Queue Q)
    
29. {
    
30.     return (Q->size == 0);
    
31. }        
    
32. 
    
33. void Enqueue(Queue Q,Element X)
    
34. {   
    
35.     if(isQueueFull(Q))
    
36.         return;
    
37.    
    
38.     Q->rear = NextPosition(Q->rear,Q->capacity);
    
39.     Q->array[Q->rear] = X;
    
40.     Q->size++;
    
41. }
    
42. 
    
43. // 队列空时，返回值未定义；
    
44. Element Dequeue(Queue Q)
    
45. {
    
46.       Element x;
    
47.       
    
48.       if(isQueueEmpty(Q))
    
49.           return 0xff;
    
50.       
    
51.       x = Q->array[Q->front];
    
52.       Q->front = NextPosition(Q->front,Q->capacity);
    
53.       Q->size--;
    
54.       
    
55.       return x;
    
56. }

复制代码

辛昕

没骗你吧。
加上头文件，还有我强迫症的缩进和空格，整个实现不足100行。

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

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

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

辛昕

但事实上，它还真的并不是真正意义上的通用。

为啥呢？
我给你看我的文件夹截图

这个 U8_libQueue.h 为毛头文件名字这么别扭呢？
其实，别扭就别扭在 Element这个地方。

具体来说是这一句

1. typedef unsigned char  Element;
   
2. typedef short QRange;

复制代码

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

通用到什么程度呢？

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

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

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

辛昕

所以，真正意义上的通用，只有做成 不需要也无法修改的 .a/.lib文件，直接调用。

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

辛昕

事实上，我大半夜不好好睡觉，已经想出了三四种不同形式的实现方式。

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

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

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

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

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

零一春风数声

开发累哟！

辛昕

零一春风数声 发表于 2019-3-5 15:16
开发累哟！

哭啥呢。

bigbat

本身数据结构的实现就有两种内存结构，第一是：数组，二是：链表。在单片机这种环境下，我推荐数组。数组是可控的结构，不易出错。
当然，也可以使用硬件结构的队列。

辛昕

bigbat 发表于 2019-3-18 08:21
本身数据结构的实现就有两种内存结构，第一是：数组，二是：链表。在单片机这种环境下，我推荐数组。数组是 ...

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

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

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

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

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

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

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

bigbat

我这话说的很严密“本身数据结构的实现就有两种内存结构，第一是：数组，二是：链表。”我说的数据结构就是指的ADT(抽象数据结构)。而且，我说的是内存结构！
不知道你了解了没有。ADT的词条释义来自于“维基百科”，不是骗子网站哦！

bigbat

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

bigbat

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

...

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

bigbat

辛昕 发表于 2019-3-12 02:12
哭啥呢。

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

GuyGraphics

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

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

成风

1. 要存放不同类型的数据，得抽象。

C语言中，char、int、float、struct等数据类型对应的数据，从内存的角度来看，它们只有两个属性，一是开始地址，二是长度。所以，把char、int、float、struct等数据类型对应的数据，抽象为包含开始地址和长度的一段内存就行了。

把

void Enqueue(Queue Q,Element X)

修改为

void Enqueue(Queue Q, void* pData, unsigned int DataLen)

问题迎刃而解。

 

2. 要完全通用，还有一个问题要解决，就是线程安全。涉及到线程安全，其实相当于涉及到跨OS的问题。因为不同OS的锁接口的名字和参数很可能不一样。

 

辛昕

成风 发表于 2020-4-25 22:31 1. 要存放不同类型的数据，得抽象。 C语言中，char、int、float、struct等数据类型对应的数据，从内存的 ...

第一个问题

相比于 改成地址——关于数据类型的描述，我十分认可，是一个老到的描述。

但是与其如此，我还是倾向于 Linux 那种游标式的路子

 

第二个问题。

还没考虑过。但是，就FreeRTOS这类RTOS来说，它提供了带线程保护版本的API，我的思路，也是如此。

不会在ABT这个位置处理，而会在 类似于 系统调用 的 系统API这个位置处理。

成风

辛昕 发表于 2020-5-6 21:15 第一个问题 相比于 改成地址——关于数据类型的描述，我十分认可，是一个老到的描述。 ...

第二个问题。

       既然要队列通用，而且是编译成a档、lib档这种程度的通用，那就不能和某个OS的API耦合。否则其它OS可能无法使用，在不带OS的裸机上也用不了。

       要解决第二个问题，其实也不难，使用装饰模式这种设计模式就行了。队列结构体QueueRecord增加加锁、解锁函数指针，队列使用者在调用Queue_Create时把具体OS的加锁解锁API传进来（裸机传NULL），然后在Enqueue接口判断函数指针是否为NULL，不为NULL则调用就行了。

        加锁、解锁函数指针抽象得好的话，队列则可做到完美的通用。

辛昕

成风 发表于 2020-5-17 16:38 第二个问题。        既然要队列通用，而且是编译成a档、lib档这种程度的通用， ...

嗯，基本就是这个意思。