数据结构复习考试（6）

发表于   |  

C++中STL标准库中队列以及最大优先队列的使用

##0x00介绍
queue类是提供了一个队列功能的容器适配器。具体而言,它是一个FIFO(先入先出)的数据结构 在头文件<queue>中定义。

##0x01队列
常用方法:

bool empty() const;
size_type size() const;

void pop();
void push (const value_type& val);

value_type& front();/const value_type& front() const;
value_type& back();/const value_type& back() const;

##0x02最大优先队列
常用方法：

bool empty() const;
size_type size() const;

const value_type& top() const;
void pop();
void push (const value_type& val);

最大优先队列的声明：
priority_queue pq;
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系
优先队列默认的是数据大的优先级高，即降序，队列头部元素最大

若需要自定义优先级，可以重载小于号：

1
2
3
4
5
6
7
8
9
struct node {
    int priority;
    int value;
    
    friend bool operator < (node n1, node n2){
       return n1.priority < n2.priority;    较大值优先
       //return n1.priority > n2.priority;  较小值优先
    }
};

或者

1
2
//对于基本类型，要使队列头部元素最小，可以使用一下声明
priority_queue<int, vector<int>, greater<int> > q;

或者

1
2
3
4
5
6
7
8
struct cmp{
    bool operator() (Node a, Node b){
        if(a.x == b.x) 
            return a.y> b.y; 
        return a.x> b.x;
    }
};
priority_queue<Node, vector<Node>, cmp> pq;

##0x03应用
首先注意，priority_queue放置元素时，不会判断元素是否重复。（因为在模板的第二个参数时顺序容器，不能保证元素的唯一性）

  • The kth great number（求依次加入队列的数中第k大的数）
  • Fence Repair