【CODING TALK】How would you implement a queue?

辛昕

【CODING TALK】How would you implement a queue? [Copy link]

 

I have habitually forgotten that I have opened a pit. But in fact, I did implement a "universal" queue according to my own ideas. In addition, I also made a double queue based on it. I implemented it because I often need to buffer serial communication and then use a simple character detector finite state machine to do frame judgment. For the sake of simplicity, I will first post my

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

. It must be said that although the queue is a very useful basic ADT, its implementation is very simple in terms of basic functions. For example, a version I implemented myself. （I implemented it according to the definitions in the relevant chapters of the book "C Language Algorithm Description") Header file definition

1. struct QueueRecord; typedef struct QueueRecord *Queue; typedef struct QueueRecord QueueStruct; typedef unsigned char Element; typedef short QRange; struct QueueRecord { QRange capacity; QRange front; QRange rear; QRange size; Element *array; }; void Queue_MakeEmpty(Queue Q); void Queue_Create(Queue Q,Element *Array,QRange MaxElement); int isQueueFull(Queue Q); void Enqueue(Queue Q,Element X); int isQueueEmpty(Queue Q); Element Dequeue(Queue Q); QRange NextPosition(QRange pos,QRange Range);

复制代码

Source file implementation

1. QRange NextPosition(QRange Pos,QRange Range) { if( (++Pos) == Range) Pos = 0; return Pos; } void Queue_MakeEmpty(Queue Q) { Q->front = 1; Q->rear = 0; Q->size = 0; } void Queue_Create(Queue Q,Element *Array,QRange MaxElement) { Q->capacity = MaxElement; Q- >array = Array; Queue_MakeEmpty(Q); } int isQueueFull(Queue Q) { return (Q->size == Q->capacity); } int isQueueEmpty(Queue Q) { return (Q->size == 0); } void Enqueue(Queue Q,Element X) { if(isQueueFull(Q)) return; Q->rear = NextPosition( Q->rear,Q->capacity); Q->array[Q->rear] = X; Q->size++; } // When the queue is empty, the return value is undefined; Element Dequeue(Queue Q) { Element x; if(isQueueEmpty(Q)) return 0xff; x = Q->array[Q->front]; Q->front = NextPosition(Q->front,Q->capacity); Q->size--; return x; }

复制代码

辛昕

I kid you not. Including the header file and my obsessive indentation and spacing, the entire implementation is less than 100 lines. In fact, there is nothing to worry about. I have used the above implementation for a long time and I am always satisfied with it. And, as you can probably tell from my obsessive-compulsive name, I use this thing as a basic component. In fact, as long as you use macros or typedef to redefine Element, this implementation is indeed quasi-universal.

辛昕

But in fact, it is not universal in the true sense. Why? Let me show you a screenshot of my folder Why is the name of this U8_libQueue.h header file so awkward? In fact, the awkwardness lies in the Element. Specifically, it is this sentence

1. typedef unsigned char Element; typedef short QRange;

复制代码

Not all the time, Element is char - although as a communication buffer such as a serial port, it is actually 99% of the time. But because this function is too simple and too basic, I really want to make it universal. How universal is it? In my opinion, except for the most tasteless copying, there are two levels of universality: 1. The code hardly needs to be modified - for example, my implementation only needs to slightly modify Element; 2. Directly compile it into a library, and when it is used, it does not need to be modified or cannot be modified. But the first implementation actually has a flaw. Suppose the following situation. In your code, there are two places where queues are needed. In the first place, Element is char, and in the second place, Element is a defined structure. You can easily imagine that at this point, its inapplicability is exposed.

辛昕

Therefore, the only way to make it universal is to make it into a .a/.lib file that does not need to be modified and can be called directly. However, here, the first problem will be how to deal with Element. (Here is a hook: I will step on your first reaction and think of void *, just like me, then, okay, try to implement it, at least I found that it is not as perfect as I thought~~)

辛昕

In fact, I didn't sleep well most of the night and have come up with three or four different forms of implementation. But to be honest, I think that for this simple function that can be implemented in less than 100 lines, this is a bit like using an anti-aircraft gun to kill a mosquito. It has lost its practical significance and is not worth wasting my time on serious things. However, I changed my mind and thought that if I take a step back and regard programming skills as a hobby like music, chess, calligraphy and painting, then let me write one implementation method a day and briefly analyze the convenience and trouble it brings to the interface and use~~~ As usual, I will leave this question alone for a day or two and wait for your reply. If you answer well, Banban will select the best 3 replies and give each of them 500 core coins.

零一春风数声

Development is so tiring!

辛昕

Posted by 零一春风数声 on 2019-3-5 15:16 Development is exhausting!

Why are you crying?

bigbat

The implementation of the data structure itself has two memory structures, the first is: array, the second is: linked list. In the environment of single-chip microcomputer, I recommend array. Array is a controllable structure and is not prone to errors. Of course, you can also use a hardware structure queue.

辛昕

bigbat published on 2019-3-18 08:21 The implementation of the data structure itself has two memory structures, the first is: array, the second is: linked list. In the environment of single-chip microcomputer, I recommend array. Array is...

Well, I found that there are several serious confusions in your cognition. First of all, the so-called data structure is actually divided into many kinds, but I guess what you want to say is that no matter whether it is a queue, stack, or tree, these basic data structures are implemented, there are two memory organization methods, one is array, and the other is linked list. But in fact, from a certain point of view. The table is one of the most basic data structures, and the other two are queues and stacks. The difference between them is the order of entry and exit. Arrays and linked lists are the two most common implementation methods of tables. Arrays can be said to be linear lists, but linked lists are not, because their memory is not necessarily continuous. I don't think that arrays are safer than linked lists in a single-chip microcomputer environment. I think you probably think that the implementation of linked lists must have the malloc/free heap memory allocation function. If so, the bare-metal C programming environment of a single-chip microcomputer without an OS is indeed unsafe. But in fact, there is another cursor implementation for linked lists. There is no need to allocate memory on the heap at all. It is also a static array solution. If you are interested, you can read a book I uploaded before, "Data Structures and Algorithms: C Language Description" The author is MKAllen

bigbat

I said this very strictly. "The implementation of data structure itself has two memory structures, the first is: array, the second is: linked list." The data structure I am talking about is ADT (abstract data structure). And, I am talking about memory structure! I don't know if you understand it. The definition of ADT comes from "Wikipedia", not a scam website!

bigbat

My suggestion to you is that it is not that no one can make a data structure library for C language, but it is not very meaningful. Why does C++ have STL, but C language does not? You may think that since C can call C++ library, it is not necessary, right? C and C++ are not the same language. For devices with limited memory such as microcontrollers, the standard library of C language is even more unnecessary. By the way, can the library you made be used under the operating system? To put it simply, can it support "multi-threading", which some people also call "multi-threading".

bigbat

Xin Xin posted on 2019-3-19 00:51 Well, I found that there are several serious confusions in your cognition. First of all, the so-called data structure is actually divided into many kinds, but I guess what you want to say is...

My reply was blocked. The data structure I mentioned refers to ADT

bigbat

Xin Xin posted on 2019-3-12 02:12 Why are you crying?

I would like to add that the data structure I studied in school was described in PASCAL language. The textbook was written by Professor Yan from Tsinghua University.

GuyGraphics

I have seen an implementation that seems to use an array to implement the queue, but when the queue is about to be full, the array's SIZE*2; when an element is removed from the queue, resulting in the total length being only 1/4 of the current length, the array's SIZE/2 is reduced.

Small topics can also highlight different highlights

成风

1. To store different types of data, abstraction is required.

In C language, the data corresponding to data types such as char, int, float, struct, etc., from the perspective of memory, they have only two attributes, one is the starting address, and the other is the length. Therefore, the data corresponding to data types such as char, int, float, struct, etc. can be abstracted into a section of memory containing the starting address and length.

Bundle

void Enqueue(Queue Q,Element X)

Modified to

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

The problem is solved.

2. To be fully universal, there is another problem to be solved, which is thread safety. Involving thread safety is actually equivalent to involving cross-OS issues, because the names and parameters of the lock interfaces of different OSes may be different.

辛昕

Chengfeng published on 2020-4-25 22:31 1. To store different types of data, you need to abstract. In C language, the data corresponding to data types such as char, int, float, struct, etc., from the memory...

First question

Compared to changing it to address - I fully agree with the description of the data type, it is a mature description.

But instead of that, I prefer the cursor approach of Linux.

The second question.

I haven't thought about it yet. However, for RTOS such as FreeRTOS, it provides an API with thread protection version, which is also my idea.

It will not be processed at the ABT location, but at the system API location similar to the system call.

成风

Xin Xin published on 2020-5-6 21:15 Compared with the first question, the description of the data type is quite mature, which I agree with. ...

The second question.

Since the queue needs to be universal and compiled into a file or lib file, it cannot be coupled with the API of a certain OS. Otherwise, it may not be used on other OSes and it cannot be used on bare metal without OS.

To solve the second problem, it is not difficult. You can use the design pattern of the decorator mode. The queue structure QueueRecord adds lock and unlock function pointers. When calling Queue_Create, the queue user passes in the lock and unlock API of the specific OS (NULL for bare metal), and then determines whether the function pointer is NULL in the Enqueue interface. If it is not NULL, just call it.

If the locking and unlocking function pointers are well abstracted, the queue can be perfectly universal.

辛昕

Chengfeng published on 2020-5-17 16:38 The second question. Since the queue is to be universal, and it is compiled into a file and lib file, ...

Well, that's basically what it means.