Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to use the C language queue, the article is very detailed, has a certain reference value, interested friends must read it!

1. The principle of queues

The queue principle is actually like a pipe. If we keep stuffing ping-pong balls into the pipe, each ping-pong ball will be arranged in a formation in the pipe. The ping-pong ball that goes in first will come out first. this is the first-in-first-out rule of the queue.

When the ball goes in from the left, the action is to enter the queue, and then the ball is lined up in the pipeline, which is called the queue cache. To put it bluntly, it is an array, so the five balls saved here is equivalent to buff [5]. In this way, the No. 1 ball that comes out on the right is the earliest ball to enter, and the action that comes out is called out, so it follows the rule of first-in, first-out.

two。 The role of the queue

The main function of the queue is to cache data. For example, the serial port receives data. We generally define an array to store the data. But if the serial port data frequency is very fast, the data stored in this array may not be finished. The next set of serial port data comes again, then the data in the array will be overwritten by the new data, resulting in the loss of the old data. Like this, it can be processed through the queue. Every byte of data received is first entered in the column, and then the application parses it synchronously. According to the first-in-first-out rule of the queue, the old data will not be "queued" by the new data.

Based on this technology of caching data, it can be flexibly applied to various scenarios, such as:

1. Message delivery of operating system

2. Big data's treatment

3. Design idea of queue Program

In fact, there are many ways to implement the queue, but the working principle is the same, we want to write code, we must first be very clear about how the queue works.

1. Queue caching

2. List

3. Out of line

A queue basically has the above three necessary operations, then the queue cache is easy to understand, to put it bluntly, it is to define an array directly, and the size of the array is the size of the queue cache. Queuing means storing one or more data in the queue cache array sequentially, and also dequeuing to extract the data from the queue cache.

I understand the principle of queuing and dequeuing, so how should I use the program to achieve it?

4. Join the list

According to the above, listing is the operation of storing data in an array, which is usually buff [0] = 1; this is the operation. However, in the queue, we need to consider how many data currently exist in the queue. If there is data, we cannot start listing with the subscript [0], so we need to consider two issues when we enter the queue:

1. The location of the array subscript that can be stored in the queue cache, which we generally call the end of the queue.

2. Is the queue full? what if the queue cache is full and new data is added to the queue? Here, we usually deal with the data that is the first to be listed in chronological order.

Discard and replace with new data.

Let's put aside the second question for the time being and look at the first one first. According to the arrays and pointers we have learned earlier, through the characteristics of pointers, we are using a pointer to represent the end of the queue, and then the end-of-line pointer points to the first address of the queue cache array, and when we list 1 data, our tail pointer is + 1, so that we can know the address that can be stored in the current queue cache?

5. Out of line

After the data is listed, it has to be taken out naturally, so when we take it, we should not take it randomly, but start from the address of the data that was first listed, so the array subscript out of the column is called the head of the line. Similarly, we can use pointer variables to represent the head of the line.

Let's take a look at the following diagram is a dequeued process. Ours is a full queue. There are a total of five pieces of data. Then the queue head pointer points to the first address of the queue cache, and then the first one is data 1. After dequeue, the queue head pointer adds 1 to the address of data 2. After data 2 is dequeued, the queue head pointer adds 1 to point to the address of data 3, and so on. In this way, the principle of first-in, first-out can be realized.

6. Master queue programming

So after we know the principle, we can use the program to implement it, because in a product, there will be many queues representing different data, for example, I have a queue for messages, and I also have a queue for the underlying serial port to receive. So let's write some operations of the queue, such as queuing, dequeuing operations separately as function interfaces, to facilitate calls from different areas of the program.

# include # include "Queue.h" Queue4 KeyMsg;int main (int argc, char * argv []) {unsigned char a; QueueEmpty (KeyMsg); / * initialize * / printf ("site:%d\ r\ n", sizeof (KeyMsg.Buff)); printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail) Printf ("& buff [0] = 0x%x, & buff [1] = 0x%x, & buff [2] = 0x%x, & buff [3] = 0x%x\ r\ n", & KeyMsg.Buff [0], & KeyMsg.Buff [1], & KeyMsg.Buff [2], & KeyMsg.Buff [3]); printf ("\ r\ n"); a = 1; QueueDataIn (KeyMsg,&a,1) / * which queue to use, which data to store, and how many data to store * / printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail) Printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n"); a = 2; QueueDataIn (KeyMsg,&a,1) Printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail); printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n") A = 3; QueueDataIn (KeyMsg,&a,1); printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail) Printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n"); a = 4; QueueDataIn (KeyMsg,&a,1) Printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail); printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n") A = 5; QueueDataIn (KeyMsg,&a,1); printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail) Printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n") Printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail); QueueDataOut (KeyMsg,&a); / * which queue to use and which data to fetch * / printf ("aversion% d\ r\ n", a) Printf ("& KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%x\ r\ n", & KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail); printf ("buff [0] = 0x%x, buff [1] = 0x%x, buff [2] = 0x%x, buff [3] = 0x%x\ r\ n", KeyMsg.Buff [0], KeyMsg.Buff [1], KeyMsg.Buff [2], KeyMsg.Buff [3]); printf ("\ r\ n") Return 0;}

Queue.c code

Void S_QueueEmpty (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff) {* Head = pBuff; * Tail = pBuff;} void S_QueueDataIn (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff,unsigned char Len,unsigned char * pData,unsigned char DataLen) {unsigned char num; / / close interrupt for (num=0; num

< DataLen; num++,pData++) { **Tail = *pData; //这里把数据入列 (*Tail)++; //队尾指针加1 if(*Tail == pBuff+Len) { *Tail = pBuff; } if(*Tail == *Head) { if(++(*Head) == pBuff+Len) { *Head = pBuff; } } } //打开中断 }unsigned char S_QueueDataOut(unsigned char **Head,unsigned char **Tail,unsigned char *pBuff,unsigned char Len,unsigned char *pData){ unsigned char status; //关闭中断 status = 0; if(*Head != *Tail) { *pData = **Head; status = 1; if(++(*Head) == pBuff+Len) { *Head = pBuff; } } //恢复中断 return status;}unsigned short S_QueueDataLen(unsigned char **Head,unsigned char **Tail,unsigned char *pBuff,unsigned char Len){ if(*Tail >

* Head) {return * Tail-*Head;} if (* Tail < * Head) {return * Tail+Len-*Head;}}

Queue.h code

# ifndef _ QUEUE_H_#define _ QUEUE_H_extern void S_QueueEmpty (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff); extern void S_QueueDataIn (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff,unsigned char Len,unsigned char * pData,unsigned char DataLen); extern unsigned char S_QueueDataOut (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff,unsigned char Len,unsigned char * pData) Extern unsigned short S_QueueDataLen (unsigned char * * Head,unsigned char * * Tail,unsigned char * pBuff,unsigned char Len) # define QueueEmpty (x) S_QueueEmpty ((unsigned char * *) & (x) .head, (unsigned char * *) & (x) .tail, (unsigned char *) (x) .Buff) # define QueueDataIn ((unsigned char * *) & (x) .Buff) S_QueueDataIn ((unsigned char * *) & (x) .Head, (unsigned char * *) & (x) .tail, (unsigned char *) & (x) .Buff, sizeof ((x) .Buff), yMague z) # define QueueDataOut (x) Y) S_QueueDataOut ((unsigned char * *) & (x) .head, (unsigned char * *) & (x) .tail, (unsigned char *) & (x) .Buff, sizeof ((x) .Buff), y) # define QueueDataLen (x) S_QueueDataLen ((unsigned char * *) & (x) .Head, (unsigned char * *) & (x) .tail, (unsigned char *) & (x) .Buff, sizeof ((x) .Buff) typedef struct {unsigned char * buff) / / unsigned char * Tail; / / queue tail pointer for dequeue, unsigned char Buff for queue entry [4]; / queue cache} Queue4;typedef struct {unsigned char * Head; / / queue head pointer, unsigned char * Tail; / / queue tail pointer for queue entry, unsigned char Buff for queue entry; / / queue cache} Queue128 Typedef struct {unsigned char * Head; / / queue header pointer, used for unsigned char * Tail; / / queue tail pointer, used for unsigned char Buff for queue entry; / / queue cache} Queue512;#endif7. Application of queues

Application of serial port:

If the product has two functions, one function requires the light to flash once a second, and the other requires the light to flash twice per second. If the function changes quickly, the function needs to be normal and the light flickers normally, then the queue is needed.

The above is all the contents of the article "how to use the C language queue". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.