stack堆栈容器、queue队列容器和priority_queue优先队列容器(常用的方法对比与总结)

时间:2022-06-27 11:17:43

stack堆栈是一个后进先出的线性表,插入和删除元素都在表的一端进行。

  stack堆栈的使用方法:

  采用push()方法将元素入栈;

  采用pop()方法将元素出栈;

  采用top()方法访问栈顶元素;

  采用empty()方法判断堆栈是否为空;

  采用size()方法返回堆栈中有几个元素。

queue队列容器是一个先进先出的线性存储表,元素的出入只能在队尾,元素的删除只能在队首。

  queue队列容器的使用方法:

  入队时使用push()方法;

  出队时使用pop()方法;

  读取队首元素时front()方法;

  读取队尾元素时back()方法;

  判断是否为空时empty()方法;

  获取队列当前的元素数目size()方法。

可以使用队列写一写广搜的题。

priority——queue优先队列容器和队列容器一样,只能从队尾插入元素,从队首删除元素。但是不同的是每一个进入队列的元素都会被安排在合适的地方,以至于出队的时候出队的元素总是最优的。故而名曰优先队列。

  priority_queue优先队列的使用方法:

  入队push(),出队pop(),读取队首元素时区分与队列容器的front()而是top(),另外还有判断队列是否为空的empty()和读取队列元素的数量size()等方法。

  重定义比较规则的方法,第一种如果元素的类型是结构体,则直接在结构体中重载“<”操作符;对应的联系是HDU 1254 Rescue。

 struct Node {
int s, t;//步数和时间
bool operator < (const Node &a) const {//返回值类型,函数名,参数列表,const限定符
return a.t < t;//按t从小到大排,反之为>即可
}
};

  如果不是结构体可以重载"()"操作符。另外注意自定义优先级的比较函数时,注意在定义优先队列时声明在<>内,否则是不会按照你定义的优先级出队的。另外声明的时候也有一点区别,需要说明内部结构,不过一般将非结构体排序,用sort也行,能掌握更好。

 struct qcmp {
bool operator () (const int &a, const int &b) {
return a > b;//按照从小到大排,反之<即可,和结构体中的相反
}
};
priority_queue<int, vector<int>, qcmp> pq;