STL容器:双端队列deque与优先级队列priority_queue

• 双端队列deque
• • 基于deque的Stack
  • 基于deque的queue
• 优先级队列priority_queue

双端队列deque

deque是一个双端队列，即可以头插和尾插，也可以头删和尾删。它的优点就是结合了vector与list两个的优点，可是实现随机访问和头插头删，在空间不够需要扩容时也不需要像vector那样复杂，只需要在原来空间的基础上加入新的空间即可。

虽然deque具有vector与list的优点，但是由于其复杂的结构，导致其有些操作效率非常低下，譬如排序，直接在deque中排序甚至不如先把数据拷贝到vector中，在vector中排序后在拷贝回deque。

deque的底层空间可以说是连续的，又不是绝对连续的。deque的实现是通过控制多个数组来实现的。内部有一个map表，每一项都是一个只想一段连续物理空间（缓冲区）的指针。数据放在那段连续的空间里。

• 每当需要访问元素时，先通过map找到具体存放在哪一块空间。然后在通过指针进行访问。虽然不是直接通过指针访问，但是比起list来看访问效率也是提高不少。
• 当需要进行头插时，找到map的第一个有效元素，该指针指向的空间若还有空余，则直接插入，没有空间则在动态开辟一块空间，将指针放在map的第一个有效元素之前。然后将元素存放在新开辟的空间的最后一个位置。也不需要移动元素。与list的效率一样高。若map已满，则重新开辟空间并将原来的map拷贝到新的map。

deque的迭代器包括四个部分，指向当前缓冲区的第一个位置first，指向当前缓冲区的最后一个位置last。指向当前元素cur，node保存该缓冲区在map中的位置。first与last作为缓冲区的边界防止越界，node为了可以跳转到下一个或上一个缓冲区。

基于deque的Stack

栈是一个先进后出的数据结构，即只可以在一端进行插入与删除操作。deque双向都可以插入与删除。所以我们将deque再次进行封装操作后就可以实现一个栈。STL标准库的栈就是基于deque实现的。

栈的接口不多。下面是一个模拟实现的栈。

template<class T, class Con = deque<T>>
class stack
{
public:
	stack() {}
	void push(const T& x) {
		_c.push_back(x);
	}

	void pop() {
		_c.pop_back();
	}

	T& top() {
		return _c.back();
	}

	const T& top()const {
		return _c.back();
	}

	size_t size()const {
		return _c.size();
	}

	bool empty()const {
		return _c.empty();
	}

private:
	Con _c;
};
           

把deque的接口封装起来，只暴露一些可以使用的，就形成了一个栈。

基于deque的queue

同理，队列是一个先进先出的数据结构，采用同样的方式，我们可以把deque封装为一个队列。

template<class T, class Con = deque<T>>
class queue
{
public:
	queue() {};

	void push(const T& x) {
		_c.push_back();
	}

	void pop() {
		_c.pop();
	}

	T& back() {
		return _c.back();
	}

	const T& back()const {
		return _c.back();
	}

	T& front() {
		return _c.front();
	}

	const T& front()const {
		return _c.front();
	}

	size_t size()const {
		return _c.size();
	}

	bool empty()const {
		return _c.empty();
	}
private:
	Con _c;
};
           

优先级队列priority_queue

优先级队列就是认为队列中的元素有权值，每当有元素入队时会根据权值为队列元素重新排序，可简单理解为建造堆。

使用优先级队列默认时建造一个大根堆。

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
// test priority queue...
	int ia[9] = {0,1,2,3,4,8,9,3,5};
	priority_queue<int> ipq(ia, ia+9);
	cout << "size=" << ipq.size() << endl; // size=9
	for(int i=0; i<ipq.size(); ++i)
		cout << ipq.top() << ' '; // 9 9 9 9 9 9 9 9 9
	cout << endl;
	while(!ipq.empty()) {
		cout << ipq.top() << ' '; // 9 8 5 4 3 3 2 1 0
		ipq.pop();
	}
	cout << endl;
	return 0;
}
           

要建造小根堆需要指定参数与底层容器。

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	// test priority queue...
	int ia[9] = { 0,1,2,3,4,8,9,3,5 };
	priority_queue<int, vector<int>, greater<int>> ipq(ia, ia + 9);
	cout << "size=" << ipq.size() << endl; // size=9
	for (int i = 0; i < ipq.size(); ++i)
		cout << ipq.top() << ' '; // 0 0 0 0 0 0 0 0 0
	cout << endl;
	while (!ipq.empty()) {
		cout << ipq.top() << ' '; // 0 1 2 3 3 4 5 8 9
		ipq.pop();
	}
	cout << endl;
	return 0;
}