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

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

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;
}
}

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