队列

队列是一种在队尾部插入，在队头部删除的先入先出（FIFO）数据结构。在队尾部插入称为入队，在队头部删除称为出队。

 

struct queue 
{
  task_t *head;
  task_t *tail;
};

 

队列最重要的两个操作就是入队和出队操作。

 

上面是一个最简单的队列结构，不过这样太“arbitrary”了。

 

struct queue 
{
  task_t *head;
  task_t *tail;

  unsigned int count; // the number of elements in queue.
};

指定队列容量

struct queue 
{
  // the size of queue, also known as "capacity"
  unsigned int size;

  task_t *head;
  task_t *tail;

  unsigned int count; // the number of elements in queue.
};

 

 

 

 

 

队列是一个典型的生产者消费者问题。生产者向队列生产数据，消费者从队列消费数据。如果队列满了，生产者必须进入等待，或者进入睡眠，先睡一下，等待消费者消费数据以空出队列空间。如果队列空了，消费者也必须进入等待，或者也进入睡眠，等到生产者向队列生产数据才能继续消费。

 

struct queue 
{
  // the size of queue, also known as "capacity"
  unsigned int size;
	
  task_t *head;
  task_t *tail;
  
  unsigned int count; // the number of elements in queue.

  pthread_mutex_t mutex;
  pthread_cond_t cond;
};

 

 

优先级队列

优先级队列也叫二叉堆。

写道

堆
https://www.iteye.com/blog/lobin-2325641