先进先出
队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在 队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除 第一个元素。
队列实现
为了实现队列,我们可以使用 动态数组 和 指向队列头部的索引。
如上所述,队列应支持两种操作:入队和出队。入队会向队列追加一个新元素,而出队会删除第一个元素。 所以我们需要一个索引来指出起点。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
class MyQueue {
private:
// store elements
vector<int> data;
// a pointer to indicate the start position
int p_start;
public:
MyQueue() {p_start = 0;}
/** Insert an element into the queue. Return true if the operation is successful. */
bool enQueue(int x) {
data.push_back(x);
return true;
}
/** Delete an element from the queue. Return true if the operation is successful. */
bool deQueue() {
if (isEmpty()) {
return false;
}//出队时注意判断队列是否为空
p_start++;
return true;
};
/** Get the front item from the queue. */
int Front() {
return data[p_start];
};
/** Checks whether the queue is empty or not. */
bool isEmpty() {
return p_start >= data.size();
}
};
int main() {
MyQueue q;
q.enQueue(5);
q.enQueue(3);
if (!q.isEmpty()) {
cout << q.Front() << endl;
}
q.deQueue();
if (!q.isEmpty()) {
cout << q.Front() << endl;
}
q.deQueue();
if (!q.isEmpty()) {
cout << q.Front() << endl;
}
}
C++ STL1
2
3
4
5
6queue<int> q;
q.push(1);
q.front(); //访问队列的队首元素
q.back(); //访问队列的队尾元素
q.size(); //队列的元素个数
q.pop(); //移除队列的队首元素
循环队列
我们可以使用 固定大小的数组 和 两个指针 来指示起始位置和结束位置。 目的是 重用 我们之前提到的被浪费的存储。
- 队首指head针和队尾指针tail重合时,队列为空
- tail+1 = head 时,队列满
队列和广度优先搜索
1. 结点的处理顺序是什么?
在第一轮中,我们处理根结点。在第二轮中,我们处理根结点旁边的结点;在第三轮中,我们处理距根结点两步的结点;等等等等。
与树的层序遍历类似,越是接近根结点的结点将越早地遍历。
如果在第 k 轮中将结点 X 添加到队列中,则根结点与 X 之间的最短路径的长度恰好是 k。也就是说,第一次找到目标结点时,你已经处于最短路径中。
2. 队列的入队和出队顺序是什么?
如上面的动画所示,我们首先将根结点排入队列。然后在每一轮中,我们逐个处理已经在队列中的结点,并将所有邻居添加到队列中。值得注意的是,新添加的节点 不会 立即遍历,而是在下一轮中处理。
结点的处理顺序与它们 添加 到队列的顺序是 完全相同的顺序,即先进先出(FIFO)。这就是我们在 BFS 中使用队列的原因。
伪代码: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/**
* Return the length of the shortest path between root and target node.
*/
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
- 如代码所示,在每一轮中,队列中的结点是 等待处理的结点。
- 在每个更外一层的 while 循环之后,我们 距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。
有两种情况不需要使用哈希集:
- 代码中没有循环,例如,在树遍历中;
- 希望多次将结点添加到队列中。