C++中的queue与priority_queue

queue

queue的介绍

  队列是一种容器适配器，专门用于上下文先进先出的操作中。队列的特性是先进先出，从容器的一端插入，另一端提取元素。
  队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
  底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：empty（检测队列是否为空）、size（返回队列中有效元素的个数）、front（返回队头元素的引用）、back（返回队尾元素的引用）、push_back（在队列尾部插入元素）、pop_front（在队列头部删除元素）。
  标准容器类deque和list满足了这些要求。默认请情况下，如果没有为queue实例化指定底层容器类，则默认使用标准容器deque。

queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，为空就返回true，否则就返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val插入队列
pop()	将队头元素弹出队列

int main()
{deque<int> mydeck(3, 100);list<int> mylist(2, 200);queue<int> first;queue<int> second(mydeck);queue<int, list<int>> third;queue<int, list<int>> fourth(mylist);return 0;
}

int main()
{queue<int> myqueue;int sum(0);cout << myqueue.empty() << endl;for (int i = 1; i <= 10; i++)myqueue.push(i);cout << myqueue.empty() << endl;while (!myqueue.empty()){sum += myqueue.front();myqueue.pop();}cout << "total:" << sum << endl;return 0;
}

int main()
{queue<int> myints;cout << "0.size:" << myints.size() << endl;for (int i = 0; i < 5; i++)myints.push(i);cout << "1.size:" << myints.size() << endl;myints.pop();cout << "2.size:" << myints.size() << endl;return 0;
}

int main()
{queue<int> myqueue;myqueue.push(10);myqueue.push(20);myqueue.front() -= myqueue.back();cout << "myqueue.front():" << myqueue.front() << endl;myqueue.back() += myqueue.front();cout << "myqueue.back():" << myqueue.back() << endl;return 0;
}

  在C++11中，stack的成员函数也新增了emplace和swap。

priority_queue

priority_queue介绍

  优先队列是一种容器适配器，根绝严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。可以当做堆来理解，实际上和堆基本一致。在堆中可以随时插入元素，并且智能检索最大的堆元素（优先队列中位于顶部的元素）。
  优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类。priority_queue提供一组特定的成员函数来访问其元素。元素从特定容器的尾部被抛出，其称为有限队列的顶部。
  底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过迭代器访问，并支持以下操作：empty（检测容器是否为空）、size（返回容器中有效元素的个数）、front（返回容器中第一个元素的引用）、push_back（在容器尾部插入元素）、pop_back（删除容器尾部的元素）。需要注意的是，这些操作是priority_queue必须具备的，并非是只能有这些操作。
  标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
  需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
  优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的地方，都可以考虑使用priority_queue。默认情况下priority_queue是大堆。

priority_queue使用

函数声明	接口说明
priority_queue()/priority_queue(first, last)	构造一个优先级队列
empty()	检测优先级队列是否为空，为空就返回true，否则就返回false
size()	返回优先队列中有效元素的个数
top()	返回优先级队列中最大（最小元素），即堆顶元素
push()	在优先级队列中插入元素
pop()	删除优先级队列中的最大（最小）元素，即堆顶元素

class mycomparison
{bool reverse;
public:mycomparison(const bool& revparam = false){reverse = revparam;}bool operator() (const int& lhs, const int& rhs) const{if (reverse)return (lhs > rhs);elsereturn (lhs < rhs);}
};int main()
{int myints[] = { 10, 60, 50, 20 };priority_queue<int> first;priority_queue<int> second(myints, myints + 4);priority_queue<int, vector<int>, greater<int>> third(myints, myints + 4);typedef priority_queue<int, vector<int>, mycomparison> mypq_type;mypq_type fourth;mypq_type fifth(mycomparison(true));return 0;
}

int main()
{priority_queue<int> mypq;int sum(0);for (int i = 0; i < 10; i++)mypq.push(i);cout << "mypq size:" << mypq.size() << endl;cout << "mypq top:" << mypq.top() << endl;while (!mypq.empty()){sum += mypq.top();mypq.pop();}cout << "total:" << sum << endl;return 0;
}