stack的實現(xiàn)

???stack的容器適配器應(yīng)該選什么比較好呢?

• 首先, stack的特點是 頭部入, 尾部出 ? 尾插 和 尾刪操作比較頻繁
  我們前面學過的容器有 vector 和 list,
  vector 和 list的尾插 和 尾刪的時間復雜度是 O(1), 還是適合做容器適配器的.

stack的基本結(jié)構(gòu)

template<class T, class Continer = vector<T>> // 默認容器適配器是vector
class stack
{

private:
	Continer _con; // 維護這個容器對象就可以了
};

用這個容器對象來進行模擬實現(xiàn)stack

按照我們之前的想法, 容器適配器要么是 vector, 要么是 list.
這兩者都是 自定義類型 ? 自定義類型會調(diào)用它的默認構(gòu)造 ? 我們都不用寫構(gòu)造函數(shù)的

1. push

void push(const T& val)
{
	_con.push_back(val);
}

2. pop

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

3. size

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

4. empty

bool empty() const
{
	return _con.size() == 0;
}

5. top

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

stack測試用例

void test_stack()
{
	muyu::stack<int> st;

	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << "size->" << st.size() << endl;

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

	st.push(2);
	st.push(3);
	st.push(4);
	st.pop();
	st.pop();
	cout << "size->" << st.size() << endl;

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

}

queue的實現(xiàn)

???queue的容器適配器能不能用 vector? 能不能使用list?

• 首先, queue的特點是 隊尾入, 對頭出 ? 尾插, 頭刪操作比較頻繁
  其次, 我們來考量vector 和 list的尾插 和 頭刪效率如何?
  vector的尾插是O(1), 頭刪是O(n )且 沒有pop_front函數(shù)
  list的尾插是O(1), 頭刪也是O(1) 且 有pop_front函數(shù)
  ? 所以, 我們queue的容器適配器, list 比 vector更適合

queue的基本結(jié)構(gòu)

	template<class T, class Continer = list<T>> // 默認容器適配器是list
	class queue
	{

	private:
		Continer _con; // 維護容器對象
	};

1. push

void push(const T& val = T())
{
	_con.push_back(val);
}

2. pop

void pop()
{
	_con.pop_front();
}

3. front

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

4. back

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

5. empty

bool empty() const
{
	return _con.size() == 0;
}

6. size

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

queue測試用例

void test_queue()
{
	muyu::queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << "front->" << q.front() << endl;
	cout << "back->" << q.back() << endl;
	cout << "size->" << q.size() << endl;
	cout << endl;

	q.pop();
	q.pop();
	cout << "front->" << q.front() << endl;
	cout << "back->" << q.back() << endl;
	cout << "size->" << q.size() << endl;
	cout << endl;

	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl;
	
}

deque

源碼中， stack 和 queue的默認容器適配器給的是 deque.

我們來看一下deque的接口函數(shù)

我們驚奇的發(fā)現(xiàn): deque不僅可以支持隨機訪問 [], 還支持 頭插, 頭刪, 尾插, 尾刪. 這不妥妥地是 vector 和 list 的結(jié)合體嘛.

???那deque這么厲害, 我們之前為啥沒有聽過呢?

• 由于這個容器不值得我們?nèi)ド疃葘W習, 我這里就偷點懶, 盜用航哥的圖了!
  

禪宗說了‘人人都有佛性’后就枯坐，什么都不管了。說了‘佛向心頭做’后就真的在心頭做，不去實踐。而我說了‘在心上用功’后，必須去實踐。文章來源地址http://www.zghlxwxcb.cn/news/detail-739127.html

到了這里，關(guān)于[C++隨筆錄] stack && queue模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！