数据结构之队列

定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

循环队列

为充分利用向量空间，克服”假溢出”现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

数据结构

1
2
3
4
5
6
struct buffer
{
  uint8_t in; // 写入位置
  uint8_t out; // 读出位置
  uint8_t my_buff[BUFF_MAX_SIZE]; // 数据域
};

队列判满

1
2
3
4
5
6
bool is_buffer_full(struct buffer *buf)
{
  if(((buf->in+1) % BUFF_MAX_SIZE) == buf->out)
    return true;  // 已满
  return false;
}

队列判空

1
2
3
4
5
6
bool is_buffer_empty(struct buffer *buf)
{
  if(buf->out == buf->in)
    return true;  // 已空
  return false;
}

写入一字节数据

1
2
3
4
5
6
7
8
bool write_buffer(struct buffer *buf, uint8_t *data)
{
  if(is_buffer_full(buf))
    return false;  // 写入失败
  buf->my_buff[buf->in] = *data;
  buf->in = (++buf->in) % BUFF_MAX_SIZE;
  return true;  // 写入成功
}

读取一字节数据

1
2
3
4
5
6
7
8
bool read_buffer(struct buffer *buf, uint8_t *data)
{
  if(is_buffer_empty(buf))
    return false;  // 读取失败
  *data = buf->my_buff[buf->out];
  buf->out = (++buf->out) % BUFF_MAX_SIZE;
  return true;  // 读取成功
}

获取队列数据个数

1
2
3
4
uint8_t get_buffer_len(struct buffer *buf)
{
  return (buf->in - buf->out + BUFF_MAX_SIZE) % BUFF_MAX_SIZE;
}

读取多个数据

1
2
3
4
5
6
7
8
9
10
11
uint8_t read_several_buffer(struct buffer *buf,uint8_t *read_arry,uint8_t len)
{
  uint8_t current_len = get_buffer_len(buf);
  if(len>current_len)
    return false;  // 读取失败
  for(uint8_t i=0;i<len;i++)
  {
    read_buffer(buf,&read_arry[i]);
  }
  return true;  // 读取成功
}

清空队列

1
2
3
4
5
6
7
8
void clear_buffer()
{
  uint8_t junk;
  while(is_buffer_empty(&uart_buff)==false)
  {
    read_buffer(&uart_buff,&junk);
  }
}