线性队列

在单片机程序中，有时设计一个好的数据结构，会使程序的流程更加清晰，这里的线性队列有别与链队，
关于链队，kernel里有一个 超级经典的 双向循环链表，所以就不说链试队列。链队一般都是动态非配空间的，
在不同嵌入式系统中malloc()与free()的执行效率，每次执行的时间开销，以及产生的碎片都有可能不同，
这点本人是有切身体会的，所以固定内存的线性队列有时也是必要的。
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#ifndef  __ARRAY_LIST_H_
#define  __ARRAY_LIST_H_

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "listqueue.h"

#define ARRAYLIST_MAXLEN  (1024*1024)  // 1M
#define FIXED_OUTLEN      (32)  //固定数出去


//typedef   char ElemType;

typedef struct {  
    ElemType DATA[ARRAYLIST_MAXLEN]; 
    unsigned int  rear_point;  //尾 出
unsigned int  front_point; //头 进
unsigned char mode;        //记录 头尾状态的  0 头不在尾后   1 头在尾后
unsigned int data_count;
}ArrayList,*ArrayList_Prt;  


extern ArrayList  send_array_list;
extern ElemType goutdata[FIXED_OUTLEN];

void InitArray(ArrayList_Prt  q);
void EntArray(ArrayList_Prt  q,ElemType *str,unsigned int len);
void EntArray_A(ArrayList_Prt  q,ElemType e);
void EntArray_B(ArrayList_Prt  q,ElemType e);
ElemType * DelArray(ArrayList_Prt  q);
ElemType * DelArray_A(ArrayList_Prt  q);
unsigned int GetArrayListLength(ArrayList_Prt  q);
unsigned int GetArrayListLength_A(ArrayList_Prt  q);
unsigned int GetArrayListLength_G(ArrayList_Prt  q,unsigned char pattern);
void Print_ArrayList(ArrayList_Prt  q);

#endif

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "array_list.h"

ElemType goutdata[FIXED_OUTLEN];
ArrayList  send_array_list;

void InitArray(ArrayList_Prt  q)
{
q->rear_point = 0;
q->front_point = 0;
q->mode = 0;
}


void EntArray(ArrayList_Prt  q,ElemType *str,unsigned int len)
{
unsigned int i = 0;


for(i=0;i<len;i++){
q->DATA[q->front_point] = str[i];

if(++(q->front_point) >= ARRAYLIST_MAXLEN)  //当前这个front_point 有 有效数据
q->front_point = 0;
}

}


void EntArray_A(ArrayList_Prt  q,ElemType e) //让元素e进队
{
if((q->front_point + 1) % ARRAYLIST_MAXLEN == q->rear_point) //队列已满
{
q->mode = 2;
return;
}

q->DATA[q->front_point] = e; //元素e进队
q->front_point = (q->front_point + 1) % ARRAYLIST_MAXLEN; //游标rear上前进一位,如果已达最后,就移到前面
}


void EntArray_B(ArrayList_Prt  q,ElemType e) //让元素e进队
{

q->DATA[q->front_point] = e; //元素e进队
q->front_point = (q->front_point + 1) % ARRAYLIST_MAXLEN; //游标rear上前进一位,如果已达最后,就移到前面
}




ElemType * DelArray(ArrayList_Prt  q)
{
unsigned int i = 0,j=0,k=0;
ElemType *record_array;


if(GetArrayListLength(q)<FIXED_OUTLEN){ 
return NULL;
}
record_array = goutdata;

if(q->mode == 0){  //头在前
for(i=0;i<FIXED_OUTLEN;i++){
record_array[i] = q->DATA[(q->rear_point)];  
  if(++(q->rear_point) >= ARRAYLIST_MAXLEN) 
q->rear_point = 0;
}


}else if(q->mode == 1){  //分两段来拿数据
i = q->rear_point;
j = 0;
k = ARRAYLIST_MAXLEN - q->rear_point;
while(i < ARRAYLIST_MAXLEN){  // 
record_array[j] = q->DATA[(q->rear_point)];  
  if(++(q->rear_point) >= ARRAYLIST_MAXLEN) 
q->rear_point = 0;
i++;
j++;
}

for(i=0;i<FIXED_OUTLEN-k;i++){
record_array[j] = q->DATA[(q->rear_point)];  
if(++(q->rear_point) >= ARRAYLIST_MAXLEN) 
q->rear_point = 0;
}

}

return goutdata;

}


/*
按固定块出队，出队的大小可由FIXED_OUTLEN定义
*/
ElemType * DelArray_A(ArrayList_Prt  q)
{
unsigned int i = 0;
ElemType *record_array;


if(GetArrayListLength_A(q)<FIXED_OUTLEN){ 
return NULL;
}
record_array = goutdata;

for(i=0;i<FIXED_OUTLEN;i++){
record_array[i] = q->DATA[(q->rear_point)];  
q->rear_point = (q->rear_point+1)%ARRAYLIST_MAXLEN;
}


return goutdata;


}








unsigned int GetArrayListLength(ArrayList_Prt  q)
{
unsigned int list_len = 0;
if(q->front_point >= q->rear_point){   
list_len = (q->front_point) - (q->rear_point) + 1;
q->mode = 0;
}else{
   list_len = ARRAYLIST_MAXLEN -(q->rear_point - q->front_point) + 1;
q->mode = 1;
}
if(list_len)
return list_len;
} 




unsigned int GetArrayListLength_A(ArrayList_Prt  q) //返回队列的长度
{
return (q->front_point - q->rear_point + ARRAYLIST_MAXLEN) % ARRAYLIST_MAXLEN;
}




//返回队列的长度                       pattern 0:有效长度    1:剩余长度
unsigned int GetArrayListLength_G(ArrayList_Prt  q,unsigned char pattern) 
{
if(pattern == 0 )
return (q->front_point - q->rear_point + ARRAYLIST_MAXLEN) % ARRAYLIST_MAXLEN;
else if(pattern == 1)
return ARRAYLIST_MAXLEN -(q->front_point - q->rear_point + ARRAYLIST_MAXLEN) % ARRAYLIST_MAXLEN;
}














void Print_ArrayList(ArrayList_Prt  q) //打印队列
{
unsigned int i = 0;

if(q->rear_point == q->front_point)
return;
else if(q->front_point < q->rear_point) //头在后
{
for( i = q->rear_point;i < ARRAYLIST_MAXLEN;++i)
printf("%c ",q->DATA[i]);
for( i = 0;i < q->front_point;++i)
printf("%c ",q->DATA[i]);
printf("<\n");
}
else{   //头在前
for( i = q->rear_point;i < q->front_point;++i)
printf("%c ",q->DATA[i]);
printf(">\n");
}
}