生活中的一些排队行为，基本上都是队列的形式。这篇博客涉及的概念有 队列，循环队列，优先队列，双端队列。

很多编程语言已经内置了队列结构，在实际项目中可以直接使用。这篇文章里的代码实现，主要用做原理理解。

p001601_1

拿超市买单为例，买完东西，一般会找一个结账台排队，等待结账。如果前面已经有人在排队，那你肯定是排在当前队伍的最后面，如果再来人，肯定是排在你的后面，依次往后排。每当有一个顾客买完单，那后面的顾客就会往前走，直到整个买单队伍没有人排队。这就是队列结构。是不是很简单~

队列

队列，是一种先进先出的结构(First in first out)，也就是在队尾进行插入操作，在队头进行删除操作。队列可以用链表来实现，也可以用数组来实现，要根据实际需求来决定。

队列的操作有入列、出列、判断是否为空、判断是否已满等操作。下面将用C#来实现列表结构，看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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;
    }
}

循环队列

循环队列，是将队列的空间，想象成首尾相接的圆环形式。这样可以充分利用队列空间，并且防止伪溢出的发生。循环队列，使用索引对容量取模计算出当前要插入元素的索引。

p001602_Circular-queue-1

循环队列有两个索引，一个指向队头，一个队尾，当队头索引等于队尾所引时，队列为空。而判断队满，有两种方式，一种是加一个变量，用于记录元素数量。一种是空一个位置，使用一个简单计算来判断是队列是否已满。这里我们使用第二种方式。看下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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

循环队列里最主要的计算就是取模计算，只要理清了这个，就很容易理解了，可以自己建立一个小容量队列，然后在纸上跟着代码演算一遍，很容易理解。

循环队列可以充分利用分配的内存，减少内存分配次数，提高程序性能。

优先队列

如果买冰激凌时，允许插队，那这就是一个优先队列。

优先队列和普通的队列基本一样，只是在插入元素时会根据优先级，将元素插入到正确的位置，而不是直接放到队尾。例如在任务系统中使用优先队列，就可以保证优先级更高的任务排在前面，优先出列被处理。

优先队列往往用堆来实现。这个后面才会学到，所以这里暂时不做优先队列的代码实现，现在只要知道有这样一个东西就行。

双端队列

双端队列从结构上已经和普通的队列不太一样了，它有两个头，左边和右边。可以从左边入列，从左边出列，也可以从右边入列，从右边出列。我们可以用双向链表实现这样一个结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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;
    }
}

双端队列大概就是这样，不要着急，好好体会一下，很简单。