第七十四讲 队列(3)

这一讲我们来探索队列,这是真正的队列,queue和priority_queue,在我们已经学会vector,list,deque和stack后再来看queue和priority_queue,他是这么的简单,简单得我们只需要给出的实现大家就会恍然明白——原来不过如此啊,好吧,我们先来看看queue的实现:
———————————
template<typename T,typename C=XXX<T>>
class queue{
public:

typedef typaname C::value_type value_type;



typedef typename C::size_type size_type;



typedef C container_type;

explicit queue(const C&

a = C()):c(a){ }

bool empty() const{

return c.empty();


}

size_type size() const{

return c.size();


}

value_type&

front()
{

return c.front();


}

const value_type&

front() const{

return c.front();


}

vaule&

back(const value_type&

x){

return c.back();


}

const value_type&

back() const{

return c.back();


}

void push(){

c.push_back();


}

void pop(){

c.pop_front();


}
protected:

C c;


};


———————————

同样,上面的XXX指的是容器,具有支持push_back()和pop_front()的容器,所以,他其实也就是某些容器的简单界面,但是由于我们的vector不支持pop_front,所以XXX就不可能会是vector了,但可以是list,也可以是deque,当然,默认情况下就是deque。queue的用途同样很多,windows的消息机制使用的就是queue,不过确切点说,应该priority_queue,如果是queue的话,那么可以这么来模拟消息循环:
———————————
struct Message{
///
};


void Server(queue<Message>&

q){

while(!q.empty()){

Message&

msg = q.front();


p.pop();


}
}
————————————-

使用太简单,所以大家可以自己尝试,下面我们再来看看priority_queue;
————————————-
template<typename T,typename C=XXX<T>,typename Cmp=Less<typename C::value_type>>
class priority_queue{
public:

typedef typaname C::value_type value_type;



typedef typename C::size_type size_type;



typedef C container_type;

explicit priority_queue(const Cmp&

ls=Cmp(),const C&

a = C()):c(a),cmp(ls){

make_heap(c.begin(),c.end(),cmp);


}

template<typename In>

priority_queue(In first,In last,const Cmp&

=Cmp(),const C&

=C());



bool empty() const{

return c.empty();


}

size_type size(){

return c.size();


}

const value_type&

top() const{

return c.front();


}

void push(const value_type&

);


void pop();


protected:

C c;



Cmp cmp;


};


——————————-

默认情况下,cmp使用的"

<"

操作符,所以top返回的总是最大的元素。
———————————
ps.push(5);


ps.push(1);


ps.push(8);


ps.push(9);


ps.push(2);


while (!ps.empty()){

cout <<ps.top() <<"

"

;


ps.pop();



}
———————————-
上面代码将会输出如下结果:
————————–
9 8 5 2 1
————————–

ok,队列算是说完了,有不懂的可以直接提问哈
=========================
回复D直接查看目录


原文始发于微信公众号(

C/C++的编程教室

):第七十四讲 队列(3)

|

发表评论