队列

队列也是一种操作受限的线性表数据结构，具有先进者先出的特性。

实现队列

队列主要包含两个操作：入队enqueue(),放一个数据到队列尾部；出队dequeue(),从队列头部取一个元素。
用数组实现的队列-顺序队列，多为有界队列。
队列需要两个指针：1指向队头的head指针；2指向队尾的tail指针。
顺序队列实现优化，出队时不搬移数据，入队时如果没有空闲空间集中触发一次数据的搬移操作。更进一步，循环队列可以避免数据搬移操作。
用链表实现的队列-链式队列，多为无界队列。
入队：tail->next=new_node,tail=tail->next(tail=new_node);
出队：head=head->next.

特殊队列

• 循环队列(基于数组)
  与普通队列的区别关键在于队空和队满的判定条件
  普通队列：队空head==tail,队满tail==n;
  循环队列：队空head==tail,队满(tail+1)%n==head.

  tail指向的位置没有存储数据，循环队列会浪费一个数组的存储空间。为了区分队空和队满。
  普通队列队满的时候tail指向n，而不是n-1，不会浪费空间，数组中所有的位置都有数据。

• 阻塞队列（生产者-消费者模型）
  在队列的基础上增加了阻塞操作：在队列为空的时候，从对头取数据会被阻塞；如果队列已满，插入数组的操作会被阻塞。
• 并发队列
  线程安全的队列
  在入队、出队操作方法上加锁，锁粒度大并发度低。
  基于数组的循环队列，利用CAS原子操作实现高效的并发队列。

应用

资源有限场景中，没有空闲资源时，通过队列来实现请求排队。
线程池、数据库连接池等