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;
}