stack

stack介紹

stack是一種先進後出的資料結構，只有一個出口，類似於棧。stack容器哦允許新增元素，移除元素，取得棧頂元素，但是除了最頂端之後，沒有任何其他辦法可以存取stack的其他元素，換句話說，stack不允許有遍歷的行為。

元素推入棧的操作稱為：push 元素推出棧的操作稱為：pop

概述

• 資料結構：連續的儲存空間，只有一個出口，先進後出的特性
• 迭代器：沒有迭代器
• 常用的API
  • 建構函式
  • 賦值
  • 資料存取
  • 容量大小操作

總結：

• stack是一種容器介面卡，專門用在具有後進先出 (last-in first-out)操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與提取操作。
• stack是作為容器介面卡被實現的，容器介面卡即是對特定類封裝作為其底層的容器，並提供一組特定的成員函數來存取其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。
• stack的底層容器可以是任何標準容器，這些容器需要滿足push_back，pop_back，back和empty幾個介面的操作。
• 標準容器vector、deque、list均符合這些需求，預設情況下，如果沒有為stack指定特定的底層容器，預設情況下使用deque。

stack常用的介面

//建構函式
stack<T> stkT;//stack採用模板類實現，stack物件的預設構造形式
stack(const stack &stk);//拷貝建構函式
//賦值操作
stack&operator=(const stack &stk)//過載等號操作符
//資料存取操作
push(elem);//向棧頂新增元素
pop();//從棧頂移除一個元素
top();//返回棧頂元素
//容量大小操作
empty();//判斷堆疊是否為空
size();//返回堆疊的大小

queue

queue介紹

queue是一種先進後出的資料結構（佇列），它有兩個出口，queue容器允許從一端新增元素，另一端移除元素

概述

• 資料結構：連續的儲存空間，有兩個口，一個是進入資料，一個是出資料，有先進先出的特性
• 迭代器：沒有迭代器
• 常用API
  • 建構函式
  • 存取、插入和刪除
  • 賦值
  • 大小操作

總結：

• 佇列是一種容器介面卡，專門用於在FIFO上下文(先進先出)中操作，其中從容器一端插入元素，另一端提取元素。
• 佇列作為容器介面卡實現，容器介面卡即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來存取其元素。元素從隊尾入佇列，從隊頭出佇列。
• 和stack一樣，它的底層容器可以是任何標準容器，但這些容器必滿足push_back，pop_back，back和empty幾個介面的操作。
• 標準容器類deque和list滿足了這些要求。預設情況下，如果沒有為queue範例化指定容器類，則使用標準容器deque。

queue常用的介面

//建構函式
queue<T> queT;//queue採用模板類實現，queue物件的預設建構函式
queue(const queue &que);//拷貝建構函式
//存取、插入和刪除操作
push(elem);//往隊尾新增元素
pop();//從對頭移除第一個元素
back();//返回最後一個元素
front();//返回第一個元素
//賦值操作
queue&operator=(const queue &que);//過載等號操作符
//容量大小操作
empty();//判斷佇列是否為空
size();//返回佇列的大小

容器介面卡

介面卡： 一種設計模式，該種模式是將一個類的介面轉換成客戶希望的另外一個介面。

可以看出的是，這兩個容器相比我們之間見過的容器多了一個模板引數，也就是容器類的模板引數，他們在STL中並沒有將其劃分在容器的行列，而是將其稱為容器介面卡，它們的底層是其他容器，對其他容器的介面進行了包裝，它們的預設是使用deque（雙端佇列）

deque

vector容器時單向開口的連續記憶體空間，deque則是一種雙向開口的連續線性空間。雙開口的含義是：可以在頭尾兩端進行插入和刪除操作，且時間複雜度為O(1)，與vector比較，頭插效率高，不需要搬移元素；與list比較，空間利用率比較高。

deque底層結構
它並不是一段連續的空間，而是由多個連續的小空間拼接而成，相當於一個動態的二維陣列。

Deque容器是連續的空間，至少邏輯上看來如此，連續現行空間總是令我們聯想到 array和vector，array無法成長，vector雖可成長，卻只能向尾端成長，而且其成長其實 是一個假象，事實上（1）申請更大空間（2）原資料複製新空間（3）釋放原空間三步驟，如果不是vector每次設定新的空間時都留有餘裕，其成長假象所帶來的代價是非常昂貴的。Deque是由一段一段的定量的連續空間構成。一旦有必要在前端或者尾端增加新的空間，便設定一段連續定量的空間，串接在deque的頭端或者尾端。Deque最大的工作就是維護這些分段連續的記憶體空間的整體性的假象並提供隨機存取的介面，避開了重新設定空間，複製，釋放的輪迴，代價就是複雜的迭代器架構。 既然deque是分段連續記憶體空間，那麼就必須有中央控制，維持整體連續的假象資料結構的設計及迭代器的前進後退操作頗為繁瑣。Deque程式碼的實現遠比vector或list都多得多。

Deque採取一塊所謂的map作為主控，這裡所謂的map是一小塊連續的記憶體空間，其中每一個元素（此時成為一個結點）都是一個指標，指向另一段連續的記憶體空間，稱作緩衝區，緩衝區才是deque的儲存空間的主體。

deque的迭代器：

deque的優點：

• 相比於vector，deque可以進行頭插和頭刪，且時間複雜度是O(1)，擴容是也不需要大量挪動資料，因此效率是比vector高的。
• 相比於list，deque底層是連續的空間，空間利用率高,，也支援隨機存取，但沒有vector那麼高。
• 總的來說，deque是一種同時具有vector和list兩個容器的優點的容器，有一種替代二者的作用，但不是完全替代。

deque的缺點：

• 不適合遍歷，因為在遍歷是，deque的迭代器要頻繁地去檢測是否運動到其某段小空間的邊界，所以導致效率低下。
• deque的隨機存取的效率是比vector低很多的，實際中，線性結構大多數先考慮vector和list。

deque可以作為stack和queue底層預設容器的原因：

1. stack和queue並不需要隨機存取，也就是說沒有觸及到deque的缺點，只是對頭和尾進行操作。
2. 在stack增容時，deque的效率比vector高，queue增容時，deque效率不僅高，而且記憶體使用率也高。

stack和queue的模擬實現

template<class T, class Container = deque<T>>
class stack
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_back();
	}
	T top()
	{
		return _con.back();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};


template<class T, class Container = deque<T>>
class queue
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}
	void pop()
	{
		_con.pop_front();
	}
	T& front()
	{
		return _con.front();
	}
	T& back()
	{
		return _con.back();
	}
	size_t size()
	{
		return _con.size();
	}
	bool empty()
	{
		return _con.empty();
	}
private:
	Container _con;
};

priority_queue（優先順序佇列）

template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> 
class priority_queue

priority_queue 範例預設有一個 vector 容器。函數物件型別 less 是一個預設的排序斷言，定義在標頭檔案 function 中，決定了容器中最大的元素會排在佇列前面。fonction 中定義了 greater，用來作為模板的最後一個引數對元素排序，最小元素會排在佇列前面。當然，如果指定模板的最後一個引數，就必須提供另外的兩個模板型別引數。

總結幾點：

• 優先順序佇列也是一種容器介面卡，它的第一個元素總是最大的。
• 類似於堆，且預設是大堆，在堆中可以插入元素，並且只能檢索最大元素。
• 底層容器可以任何標準容器類別範本，也可以是其他特定容器類封裝作為器底層容器類，需要支援push_back，pop_back，front和empty幾個介面的操作。

priority_queue常用的介面

push(const T& obj);//將obj的副本放到容器的適當位置，這通常會包含一個排序操作。
push(T&& obj);//將obj放到容器的適當位置，這通常會包含一個排序操作。
emplace(T constructor a rgs...);//通過呼叫傳入引數的建構函式，在序列的適當位置構造一個T物件。為了維持優先順序，通常需要一個排序操作。
top();//返回優先順序佇列中第一個元素的參照。
pop();//移除第一個元素。
size();//返回佇列中元素的個數。
empty();//如果佇列為空的話，返回true。
swap(priority_queue<T>& other);//和引數的元素進行交換，所包含物件的型別必須相同。

void test_priority_queue()
{
	priority_queue<int, vector<int>> pq;

	pq.push(5);
	pq.push(7);
	pq.push(4);
	pq.push(2);
	pq.push(6);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

priority_queue的模擬實現

priority_queue的框架

其中模板中有三個引數，最後一個引數是仿函數，也就是指明優先順序佇列是按照升序還是降序來存資料的

template<class T, class Container = vector<T>, class Compare = less<T>>// 預設是小於
class priority_queue
{
public:
private:
	Container _con;
	Compare _com;
};

仿函數

仿函數(functor)，就是使一個類的使用看上去像一個函數。其實現就是類中實現一個operator()，這個類就有了類似函數的行為，就是一個仿函數類了。

// 仿函數  就是一個類過載了一個()，operator()，可以像函數一樣使用
template<class T>
struct greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};
template<class T>
struct less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

可以看出，仿函數就是用一個類封裝一個成員函數operator()，使得這個類的物件可以像函數一樣去呼叫。

範例演示：

template<class T>
struct IsEqual
{
	bool operator()(const T& a, const T& b)
	{
		return a == b;
	}
};
void test()
{
	IsEqual<int> ie;
	cout << ie(2, 3) << endl;// 該類範例化出的物件可以具有函數行為
}

堆的向上調整和向下調整的實現

向上調整： 從最後一個數往上調整

void AdjustUp(int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[child] > _con[parent])//<  建小堆  > 建大堆
		{
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

向下調整： 從第一個往下調整

void AdjustDown(int parent)
{
	int child = parent * 2 + 1;
	while (child < (int)size())
	{			
		if (child + 1 < (int)size() && _con[child + 1] > _con[child]) 
		{
			++child;
		}
		if (_con[child] >  _con[parent])// 建小堆
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

這兩個函數用仿函數實現後如下：

void AdjustUp(int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_com(_con[parent], _con[child]))// _con[child] > _con[parent]
		{
			swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(int parent)
{
	int child = parent * 2 + 1;
	while (child < (int)size())
	{			
		if (child + 1 < (int)size() && _com(_con[child], _con[child + 1]))// _con[child + 1] > _con[child]
		{
			++child;
		}
		if (_com(_con[parent], _con[child]))// _con[child] >  _con[parent]
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

priority_queue的插入和刪除

push 先在隊尾插入資料，然後用向上調整演演算法使得堆是大堆或小堆

void push(const T& x)
{
	_con.push_back(x);
	AdjustUp((int)size() - 1);
}

pop 先將堆頂的元素和隊尾的元素交換，再刪去隊尾元素（而不是直接刪去堆頂元素，這樣會破壞堆的結構，然後又要建堆），然後再使用向下調整演演算法使得堆是大堆或小堆

void pop()
{
	assert(!empty());
	swap(_con[0], _con[(int)size() - 1]);
	_con.pop_back();
	AdjustDown(0);
}

priority_queue的存取與大小

//top 返回堆頂元素
T& top()
{
	assert(!empty());
	return _con[0];
}
//size 返回優先順序佇列元素個數
size_t size()
{
	return _con.size();
}
//empty 判斷優先順序佇列是否為空
bool empty()
{
	return size() == 0;
}