实现队列的程序代码主要涉及以下内容:数据结构、队列的操作、C++语法等。下面我们一步步来进行讲解。
数据结构
队列可以看成是一种特殊的线性表,它具有先进先出(FIFO)的特点,即先进队列的元素将先输出,后进队列的元素将后输出。
队列通常包含以下几个基本操作:入队、出队、判空和求队列长度等。入队就是将新元素插入到队列的末尾,出队就是将队头元素删除并返回,判空就是检查队列是否为空,求队列长度就是统计当前队列中元素的数量。
在C++中,可以使用STL库提供的queue模板类来实现队列。queue模板类已经封装好了队列的基本操作,因此我们只需要了解如何使用queue模板类就能够实现队列。
队列的操作
首先需要在程序中引入queue头文件:
#include <queue>
然后定义一个队列:
queue<int> q;
上述代码定义了一个名为q的队列,元素的类型为int。
接下来介绍几个队列的常用操作:
入队
使用push函数可以将新元素插入到队列的末尾:
int num = 3;
q.push(num);
上述代码将数字3插入到了队列的末尾。
出队
使用front函数可以获取队头元素,使用pop函数可以将队头元素删除:
int front_element = q.front(); // 获取队头元素
q.pop(); // 删除队头元素
上述代码获取了队头元素并将其删除。
判空
使用empty函数可以判断队列是否为空:
if (q.empty()) {
cout << "队列为空!" << endl;
}
上述代码判断了队列是否为空。
求队列长度
使用size函数可以获取队列中元素的数量:
int queue_size = q.size(); // 获取队列中元素的数量
上述代码获取了队列中元素的数量。
除了以上几个操作,queue模板类还提供了其他常用的操作,如清空队列、遍历队列等。
示例说明
下面通过两个示例来说明如何使用C++实现队列的程序代码。
示例一:基本的队列操作
下面的代码演示了在队列中插入元素、删除元素、判断队列是否为空以及获取队列长度:
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
// 往队列中插入元素
q.push(2);
q.push(3);
q.push(5);
q.push(7);
q.push(11);
// 输出队列中的元素
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
// 判断队列是否为空
if (q.empty()) {
cout << "队列已经为空!" << endl;
}
// 获取队列中元素的个数
int num_elem = q.size();
cout << "队列中有" << num_elem << "个元素。" << endl;
return 0;
}
运行结果:
2 3 5 7 11
队列已经为空!
队列中有0个元素。
示例二:使用队列实现广度优先搜索
下面的代码演示了如何使用队列实现广度优先搜索算法:
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void bfs(vector<int> graph[], int start_node);
int main() {
// 图中的边
vector<int> graph[6];
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[2].push_back(5);
graph[3].push_back(5);
graph[4].push_back(6);
graph[5].push_back(6);
// 广度优先搜索
bfs(graph, 1);
return 0;
}
void bfs(vector<int> graph[], int start_node) {
bool visited[6] = {false};
queue<int> q;
// 将起始节点加入队列
q.push(start_node);
visited[start_node] = true;
while (!q.empty()) {
int current_node = q.front();
cout << current_node << " ";
q.pop();
for (int i = 0; i < graph[current_node].size(); i++) {
int neighbor_node = graph[current_node][i];
if (!visited[neighbor_node]) {
q.push(neighbor_node);
visited[neighbor_node] = true;
}
}
}
cout << endl;
}
运行结果:
1 2 3 4 5 6
上述代码实现了如何使用队列实现广度优先搜索算法。其中,vector表示无向图,bfs函数中实现了广度优先搜索的算法。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:用C++实现队列的程序代码 - Python技术站