【专栏】数据结构和算法之美-队列：队列在线程池等有限资源池中的应用

本文主要是介绍【专栏】数据结构和算法之美-队列：队列在线程池等有限资源池中的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学习笔记

如何理解“队列”？

结构特征

操作受限的线性表数据结构
两端开放，一端是数据的入口，另一端是数据的出口

行为特征

先进先出，类似于水管，从一端进水，另一端出水，先进去的水会先流出来

如何实现队列？

基于数组实现：顺序队列

/*Queue implement based on the array*/
/*Queue implement based on the linked list*/
/*Circl Queue implement based on the array*/#include <stdio.h>#define QUEUE_LEN 8
#define TRUE (unsigned short)1
#define FALSE (unsigned short)0typedef unsigned short bool;static int queueArray[QUEUE_LEN];bool inQueue(int data, int *phead, int *ptail)
{bool ret = FALSE;int currentIndex = *ptail;int n = 0;if(*ptail == QUEUE_LEN){/*it is full*/for(; n < ((*ptail) - (*phead)); n++){queueArray[n] = queueArray[(*phead) + n];}*phead = 0;if(n < QUEUE_LEN){queueArray[n] = data;*ptail = n + 1;ret = TRUE;}else{printf("error! queue is full\n");ret = FALSE;}}else{queueArray[currentIndex] = data;*ptail = currentIndex+1;ret = TRUE;}return (ret);}int outQueue(int *phead, int *ptail)
{int ret = 0;int currentIndex = *phead;if(*ptail == *phead){return -1;}else{ret = queueArray[currentIndex];*phead = currentIndex + 1;}return ret;
}void main(void)
{int tail = 0;int head = 0;int data = 1;int n = 0;for (; n < QUEUE_LEN; n++){inQueue(data, &head, &tail);data += 1;}printf("###########test 1: new data cann't enter while the queue is full: %d\n", inQueue(9,&head, &tail));printf("###########test 2: data leave from the queue: %d\n", outQueue(&head, &tail));printf("************head=%d, tail=%d, the latest leaving value is %d\n", head, tail, queueArray[head -1]);printf("***********test 3: new data can enter even though tail reaches the end of the queue\n");inQueue(10, &head, &tail);printf("************tail's position:%d, the latest entering value is %d\n", tail, queueArray[tail - 1]);
}

循环队列

结构特征

首尾相连，成环形
对于用数组实现的非循环队列，队满条件tail == n，队空条件head == tail。而循环队列,队满特征是（tail+1）%n=head;
-

行为特征

新元素添加进来后，如果达到队满条件，tail在环中后移一位，而不是直接加1

特殊特性的队列

阻塞队列特征

队空时，从对头取数据会被阻塞
队满时，插入数据操作会被阻塞
Linux环形缓存
阻塞队列是“生产者-消费者模型”的一种实现策略。
而在多线程情况下，多个线程同时操作队列，如下，有多个线程同时从队头取数据，保证线程安全的队列我们就叫作并发队列，那么如何实现它呢？（看实战篇的Disruptor）

关于线程池会用到队列排队请求？