《算法笔记》学习笔记
queue 常见用法详解
queue翻译为队列，在STL中主要则是实现了一个先进先出的容器。
1. queue 的定义
//要使用queue，应先添加头文件#include <queue>，并在头文件下面加上"using namespace std;"，即可使用。
//定义写法
queue< typename > name;
//typename 可以是任意基本数据类型或容器
2. queue容器内元素的访问
//由于队列(queue)本身就是一种先进先出的限制性数据结构，因此在STL中只能通过
//front()来访问队首元素，或是通过back()来访问队尾元素
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for(int i = 1; i <= 5; i++) {
q.push(i); //push(i)用以将i压入队列，因此依次入队 1 2 3 4 5
}
printf("%d %d\n", q.front(), q.back()); //输出结果是1 5
return 0;
}
3.queue实用函数实例解析
(1) push()
//push(x)将x进行入队，时间复杂度为O(1),实例见"queue"容器内元素的访问。
(2) front(), back()
//front()和back()可以分别获得队首元素和队尾元素，时间复杂度为O(1),实例见"queue"容器内元素的访问。
//使用front()前，必须用empty()判断队列是否为空
(3) pop()
//pop()令队首元素出队，时间复杂度为O(1)
//使用pop()前，必须用empty()判断队列是否为空
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for(int i = 1; i <= 5; i++) {
q.push(i); //依次入队1 2 3 4 5
}
for(int i = 1; i <= 3; i++) {
q.pop(); //出队首元素三次(即依次出队1 2 3)
}
printf("%d\n", q.front()));
return 0;
}
(4) empty()
//empty()检测queue是否为空，返回true则空，返回false则非空。时间复杂度为O(1)
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
if(q.empty() == true) { //一开始队列内没有元素,所以是空
printf("Empty\n");
} else {
printf("Not Empty\n");
}
q.push(1);
if(q.empty() == true) { //在入队"1"后，队列非空
printf("Empty\n");
} else {
printf("Not Empty\n");
}
return 0;
}
(5) size()
//size()返回queue内元素的个数，时间复杂度为O(1)
#include <stdio.h>
#include <queue>
using namespace std;
int main() {
queue<int> q;
for(int i = 1; i <= 5; i++) {
q.push(i); //push(i)用以将i压入队列
}
printf("%d\n", q.size()); //队列中有5个元素
return 0;
}
4. queue的常见用途
- 需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用queue作为替代。