[C++随笔录] stack && queue模拟实现-Toy模板网

这篇具有很好参考价值的文章主要介绍了[C++随笔录] stack && queue模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

stack的实现

🗨️stack的容器适配器应该选什么比较好呢?

首先, stack的特点是 头部入, 尾部出 ⇒ 尾插和尾删操作比较频繁
我们前面学过的容器有 vector 和 list,
vector 和 list的尾插和尾删的时间复杂度是 O(1), 还是适合做容器适配器的.

stack的基本结构

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

private:
	Continer _con; // 维护这个容器对象就可以了
};

用这个容器对象来进行模拟实现stack

按照我们之前的想法, 容器适配器要么是 vector, 要么是 list.
这两者都是 自定义类型 ⇒ 自定义类型会调用它的默认构造 ⇒ 我们都不用写构造函数的

push

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

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

size

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

empty

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

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的实现

🗨️queue的容器适配器能不能用 vector? 能不能使用list?

首先, queue的特点是 队尾入, 对头出 ⇒ 尾插, 头删操作比较频繁
其次, 我们来考量vector 和 list的尾插和头删效率如何?
vector的尾插是O(1), 头删是O(n )且没有pop_front函数
list的尾插是O(1), 头删也是O(1) 且有pop_front函数
⇒ 所以, 我们queue的容器适配器, list 比 vector更适合

queue的基本结构

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

	private:
		Continer _con; // 维护容器对象
	};

push

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

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

front

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

back

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

empty

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

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

[C++随笔录] stack && queue模拟实现,C++,c++,开发语言,stl,数据结构,算法
源码中， stack 和 queue的默认容器适配器给的是 deque.

我们来看一下deque的接口函数
[C++随笔录] stack && queue模拟实现,C++,c++,开发语言,stl,数据结构,算法
我们惊奇的发现: deque不仅可以支持随机访问 [], 还支持 头插, 头删, 尾插, 尾删. 这不妥妥地是 vector 和 list 的结合体嘛.