队列的概念
1.先进者先出，这就是典型的“队列”结构。
2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。
3.所以，和栈一样，队列也是一种操作受限的线性表。
数组实现（顺序队列）
顺序队列的C#代码实现
以下代码实现了简单的顺序队列，队列初始化以及入队、出队方法。
public sealed class QueueDs<T> { private T[] data; private int n; private int head; private int tail; //有参实例构造器，根据传入整型数据初始化队列的数组 public QueueDs(int size) { n = size; head = 0; tail = 0; data = new T[size]; } //入队方法，尾指针等于数组长度时即队满 public Boolean In(T item) { if (tail == n) return false; data[tail] = item; tail++; return true; } //出队方法，头尾相等说明队空 public T Out() { if (head == tail) return default(T); T temp = data[head]; head++; return temp; } }
假溢出
以上代码中的出队入队会造成假溢出现象，即随着不断的出队，head在增加，head前的数组空间实际是被空着的。
修改入队方法
因此我们需要修改入队的方法，使每次入队时都检查并搬移数据到数组最前头。
public Boolean In(T item) { //如果队列满了 if (tail == n) { //如果是真满了就返回 if (head == 0) { return false; } //假溢出则将head处起始的数据搬移到索引0开始 for(int i = head; i < tail; ++i) { data[i - head] = data[i]; } //更新头尾指针 tail -= head; head = 0; } data[tail] = item; tail++; return true; }
以上代码避免了假溢出的情况。
链表实现（链式队列）
链式队列的C#代码实现
链式队列无需考虑溢出
public sealed class SinglyLinkedQueue<T> { //头尾指针 private Node<T> head; private Node<T> tail; private int count; public int Count { get{return count;} private set{} } //无参构造器初始化指针 public SinglyLinkedQueue() { head = null; tail = null; count=0; } //入队方法 public void In(T item) { var newNode = new Node<T>(item); var p = head; //循环到p为空 while (p!=null) { //p的后继结点为空则说明链表到头 if (p.Next == null) { //添加新节点到尾部，尾指针指向新节点，方法结束返回 p.Next = newNode; tail = newNode; count++; return; } //p的后继结点不为空说明链表没遍历到头，继续遍历 else p = p.Next; } } //出队方法 public T Out() { //如果头指针不为空说明链表不为空 if (head!= null) { //将头指针指向其后继结点 T temp = head.Data; head = head.Next; count--; return temp; } //否则就说明链表为空，返回默认值 return default(T); } }
循环队列（基于数组）
循环队列的C#代码实现
循环队列可以实现不进行数据搬移而解决假溢出现象。
//入队方法 public Boolean In(T item) { //尾指针加一除余数组长度后等于头指针即队满 if ((tail+1)%n == head) return false; data[tail] = item; //如果假溢出的话，新数据进入后就会补充到前面，实现循环 tail=(tail+1)%n; return true; } //出队方法，头尾相等说明队空 public T Out() { if (head == tail) return default(T); T temp = data[head]; //如果头指针出队到数组长度，再出队head就更新到数组前面 head=(head+1)%n; return temp; }
队列的常见的应用
阻塞队列
1）在队列的基础上增加阻塞操作，就成了阻塞队列。
2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；
如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
3）从上面的定义可以看出这就是一个“生产者-消费者模型”。
这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。
当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，
这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。
不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，
比如配置几个消费者，来应对一个生产者。
并发队列
1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
线程池资源枯竭时的处理
在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
思考
1.除了线程池这种池结构会用到队列排队请求，还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？
2.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？