生活中的一些排队行为，基本上都是队列的形式。这篇博客涉及的概念有 队列，循环队列，优先队列，双端队列。
很多编程语言已经内置了队列结构，在实际项目中可以直接使用。这篇文章里的代码实现，主要用做原理理解。
拿超市买单为例，买完东西，一般会找一个结账台排队，等待结账。如果前面已经有人在排队，那你肯定是排在当前队伍的最后面，如果再来人，肯定是排在你的后面，依次往后排。每当有一个顾客买完单，那后面的顾客就会往前走，直到整个买单队伍没有人排队。这就是队列结构。是不是很简单~
队列
队列，是一种先进先出的结构(First in first out)，也就是在队尾进行插入操作，在队头进行删除操作。队列可以用链表来实现，也可以用数组来实现，要根据实际需求来决定。
队列的操作有入列、出列、判断是否为空、判断是否已满等操作。下面将用C#来实现列表结构，看代码
public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
}
}
public class LinkedListQueue
{
public Node head;
public Node tail;
// 插入一个元素
public void Enqueue(int data)
{
Node newNode = new Node(data);
if (head == null)
{
head = newNode;
tail = newNode;
}
else
{
tail.next = newNode;
tail = newNode;
}
}
// 删除一个元素
public int Dequeue()
{
if (IsEmpty())
{
Debug.LogError("Is Empty");
return -1;
}
Node node = head;
head = head.next;
return node.data;
}
// 判断是否为空
public bool IsEmpty()
{
return head == null;
}
}
循环队列
循环队列，是将队列的空间，想象成首尾相接的圆环形式。这样可以充分利用队列空间，并且防止伪溢出的发生。循环队列，使用索引对容量取模计算出当前要插入元素的索引。
循环队列有两个索引，一个指向队头，一个队尾，当队头索引等于队尾所引时，队列为空。而判断队满，有两种方式，一种是加一个变量，用于记录元素数量。一种是空一个位置，使用一个简单计算来判断是队列是否已满。这里我们使用第二种方式。看下面的代码。
public class CircularQueue
{
private int[] array = null;
private int capacity = 0;
public int head = 0;
public int tail = 0;
// 在New一个循环队列时，指定队列的容量
public CircularQueue(int capacity)
{
this.capacity = capacity;
this.array = new int[capacity];
}
// 判断队列是否为空
public bool IsEmpty()
{
return head == tail;
}
// 判断队列是否已满
public bool IsFull()
{
return (tail + 1) % capacity == head;
}
// 入列一个元素
public void Enqueue(int data)
{
if (IsFull())
{
Debug.LogError("Queue is Full!");
return;
}
array[tail] = data;
tail = (tail + 1) % capacity;
Debug.Log("Enqueue: " + data);
}
// 出列一个元素
public int Dequeue()
{
if (IsEmpty())
{
Debug.LogError("Queue Is Empty");
return -1;
}
int data = array[head];
head = (head + 1) % capacity;
return data;
}
}
为了使判断队列为空和队列已满不冲突，所以我们将队列空了一个位置，所以要记得整个队列的实际容量为 capacity - 1
循环队列里最主要的计算就是取模计算，只要理清了这个，就很容易理解了，可以自己建立一个小容量队列，然后在纸上跟着代码演算一遍，很容易理解。
循环队列可以充分利用分配的内存，减少内存分配次数，提高程序性能。
优先队列
如果买冰激凌时，允许插队，那这就是一个优先队列。
优先队列和普通的队列基本一样，只是在插入元素时会根据优先级，将元素插入到正确的位置，而不是直接放到队尾。例如在任务系统中使用优先队列，就可以保证优先级更高的任务排在前面，优先出列被处理。
优先队列往往用堆来实现。这个后面才会学到，所以这里暂时不做优先队列的代码实现，现在只要知道有这样一个东西就行。
双端队列
双端队列从结构上已经和普通的队列不太一样了，它有两个头，左边和右边。可以从左边入列，从左边出列，也可以从右边入列，从右边出列。我们可以用双向链表实现这样一个结构。
public class DoubleEndedQueue
{
public Node left = null;
public Node right = null;
// 判断队列是否为空
public bool IsEmpty()
{
return (left == null || right == null);
}
// 从左边入列一个元素
public void EnqueueLeft(int data)
{
Node newNode = new Node(data);
if(left == null)
{
left = newNode;
right = newNode;
}
else
{
newNode.next = left;
left.prev = newNode;
left = newNode;
}
}
// 从左边出列一个元素
public int DequeueLeft()
{
if (IsEmpty())
{
return -1;
}
Node node = left;
if(left.next != null)
{
left.next.prev = null;
}
left = left.next;
return node.data;
}
// 从右边入列一个元素
public void EnqueueRight(int data)
{
Node newNode = new Node(data);
if(right == null)
{
left = newNode;
right = newNode;
}
else
{
newNode.prev = right;
right.next = newNode;
right = newNode;
}
}
// 从右边出列一个元素
public int DequeueRight()
{
if (IsEmpty())
{
return -1;
}
Node node = right;
if(right.prev != null)
{
right.prev.next = null;
}
right = right.prev;
return node.data;
}
}
双端队列大概就是这样，不要着急，好好体会一下，很简单。