C語言佇列和應用詳情

2022-03-06 13:00:26

1.佇列的原理

佇列原理其實就像一個管道，如果我們不斷往管道里面塞乒乓球，每個乒乓球在管道里就會排列一條隊形。先進去的乒乓球就會先出來，這個就是佇列的先進先出的規則。

球從左邊進去，進去的動作就是入列，然後進去的球在管道里排成一個佇列，這個叫佇列快取，說白了就是陣列，那麼這裡存了5個球就相當於是buff[5];這樣的意思，最右邊出來的1號球就是最早進去的球，出來的這個動作叫出列，所以遵循了先進先出的規則。

2.佇列的作用

佇列最主要的作用就是用來快取資料，比方說串列埠接收資料，我們一般定義一個陣列來儲存資料，但是假如串列埠資料頻率很快，可能這個陣列裡儲存的資料還沒處理完，下一組串列埠資料又過來了，那麼這時候陣列裡的資料就會被新資料覆蓋，導致老的資料丟失。像這種就可以通過佇列的方式來處理，每收到一個位元組資料都先入列，然後應用程式同步解析處理，根據佇列先進先出的規則，那麼老的資料就不會被新的資料“插隊”了。

基於這種快取資料的技術，可以靈活應用在各種場景，比如說：

1、作業系統的訊息傳遞
2、巨量資料處理

3.佇列程式設計思路

其實實現佇列的方法有很多種，但是工作原理都是一樣的，我們要編寫程式碼，首先要很清楚佇列的工作原理。

1、佇列快取
2、入列
3、出列
一個佇列基本上要有上面這三個必要的操作，那麼佇列快取就很好理解，說白了就是直接定義一個陣列，陣列大小就是佇列快取的大小。入列就是把1個或者若干個資料按順序存到佇列快取陣列裡，同樣出列把資料從佇列快取裡取出來。

入列和出列的原理懂了，那麼應該怎麼樣用程式來實現呢？

4.入列

根據上文的說法，入列就是把資料存進陣列的操作，我們平時存陣列一般都是buff[0]=1;這樣操作。不過在佇列中我們要考慮佇列裡當前存在多少個資料的情況，如果有資料，那麼我們就不能從[0]這個下標開始入列，所以我們在入列時要考慮兩個問題：

1、佇列快取可以儲存的陣列下標位置，這個我們一般稱為隊尾。
2、佇列是否已滿，如果佇列快取滿了又有新的資料入列，該怎麼處理？這裡我們一般處理方式是按照時間順序，把最早入列的資料

丟棄，以新的資料替換。
第二個問題先暫時不管，先看第一個問題。根據前面學過的陣列與指標，通過指標的特性，我們在用1個指標來代表隊尾，然後這個隊尾指標指向佇列快取陣列的首地址，當入列1個資料時，我們的隊尾指標就+1，這樣是不是就能夠知道當前佇列快取的可以儲存的地址了？

5.出列

資料入列以後自然要取出來，那麼我們取的時候也是有原則的，不能亂取，而是從最早入列那個資料的地址開始取，所以這個出列的陣列下標我們稱為隊頭，同樣我們可以使用指標變數來代表這個隊頭。
我們看看下面這個圖是一個出列的流程，我們這個是滿編隊的佇列，總共有1,2，3,4，5個資料，那麼隊頭指標指向佇列快取首地址，接著第一個出列的就是資料1，出列後隊頭指標加1，就指向資料2的地址，那麼資料2出列後，隊頭指標又加1，指向資料3的地址，以此類推，這樣就可以實現先進先出的原則。

6.掌握佇列程式編寫

那麼我們知道原理後就可以用程式來實現它了，因為一個產品中，會有很多佇列代表不同的資料，比如說訊息我有一個佇列，底層串列埠接收我也有一個佇列，所以我們吧佇列的一些操作，比如說入列，出列的操作單獨寫成函數介面，方便程式不同區域的呼叫。

#include <stdio.h>
#include "Queue.h"
Queue4 KeyMsg;

int main(int argc, char *argv[])
{
    unsigned char a; 
    QueueEmpty(KeyMsg);/*初始化*/
    printf("site:%drn",sizeof(KeyMsg.Buff)); 
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("&buff[0]=0x%x, &buff[1]=0x%x, &buff[2]=0x%x, &buff[3]=0x%x rn",&KeyMsg.Buff[0],&KeyMsg.Buff[1],&KeyMsg.Buff[2],&KeyMsg.Buff[3]);
    printf("rn"); 
    
    a = 1;
    QueueDataIn(KeyMsg,&a,1);/*要用哪一個佇列，要存那個資料，要存多少個資料*/
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    a = 2;
    QueueDataIn(KeyMsg,&a,1);
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    a = 3;
    QueueDataIn(KeyMsg,&a,1);
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    a = 4;
    QueueDataIn(KeyMsg,&a,1);
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    a = 5;
    QueueDataIn(KeyMsg,&a,1);
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    QueueDataOut(KeyMsg,&a);/*要用哪一個佇列，要取那個資料*/
    printf("a=%drn",a); 
    printf("&KeyMsg=0x%x, KeyMsg.Buff=0x%x, KeyMsg.Head=0x%x, KeyMsg.Tail=0x%xrn",&KeyMsg,KeyMsg.Buff,KeyMsg.Head,KeyMsg.Tail);
    printf("buff[0]=0x%x, buff[1]=0x%x, buff[2]=0x%x, buff[3]=0x%x rn",KeyMsg.Buff[0],KeyMsg.Buff[1],KeyMsg.Buff[2],KeyMsg.Buff[3]);
    printf("rn"); 
    
    return 0;
}

queue.c程式碼

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;
    //關閉中斷 
    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程式碼

#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(x,y,z) S_QueueDataIn((unsigned char **)&(x).Head,(unsigned char **)&(x).Tail,(unsigned char *)&(x).Buff,sizeof((x).Buff),y,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 *Head;     //隊頭指標，用來出列用的 
    unsigned char *Tail;     //隊尾指標，用來入列用的 
    unsigned char Buff[4];    //佇列快取 
}Queue4;

typedef struct
{
    unsigned char *Head;     //隊頭指標，用來出列用的 
    unsigned char *Tail;     //隊尾指標，用來入列用的 
    unsigned char Buff[128];    //佇列快取 
}Queue128;

typedef struct
{
    unsigned char *Head;     //隊頭指標，用來出列用的 
    unsigned char *Tail;     //隊尾指標，用來入列用的 
    unsigned char Buff[512];    //佇列快取 
}Queue512;
#endif