C++中的queue

在编程过程中，当需要实现广度优先搜索时，可以不用自己手动实现一个队列，而是用queue作为代替，以提高程序的准确性。要使用queue，必须包含头文件#include还有命名空间”using namespace std;”。STL的容器中还有两种容器和队列有关，分别是双端队列(deque)和优先队列(priority_queue)，前者是首位皆可以插入和删除的队列，后者是使用堆实现的默认将当前队列最大元素置于队首的容器。

1、queue的定义:queue<typename> name;例如:

queue<int> name;//typename可以是任意基本数据类型或容器

2、queue容器内元素的访问

由于队列queue是一种先进先出的限制性数据结构,因此在STL中只能通过front()来访问队首元素,或者通过back()来访问队尾元素。

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
int main(){
    queue<int> q;
    for(int i=1;i<=5;i++){
        q.push(i);//push(i)将i压入队列
    }
    cout<<q.front()<<" "<<q.back();
    return 0;
}

3、queue常用的函数

(1)push(x):将x进行入队，时间复杂度为O(1)。
(2)pop():令队首元素出队，时间复杂度为O(1)。使用pop()函数之前必须用empty()判断队列是否为空。
(3)front():获得队首元素，时间复杂度为O(1)。使用front()函数之前必须用empty()判断队列是否为空。
(4)back():获得队尾元素，时间复杂度为O(1)。
(5)empty():检测queue是否为空，时间复杂度为O(1)。
(6)size():返回queue内的元素个数，时间复杂度为O(1)。
(7)STL中没有实现队列的清空，如果需要实现队列的清空，可以用一个while循环反复pop出元素直到队列为空：
    while(!q.empty){
        q.pop();
    }