[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; // 维护这个容器对象就可以了
};
1
2
3
4
5
6
7

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

---

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

---

1. push

void push(const T& val)
{
	_con.push_back(val);
}
1
2
3
4

2. pop

void pop()
{
	_con.pop_back();
}
1
2
3
4

3. size

const T& top() const
{
	return _con.back();
}
1
2
3
4

4. empty

bool empty() const
{
	return _con.size() == 0;
}
1
2
3
4

5. top

const T& top() const
{
	return _con.back();
}
1
2
3
4

---

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;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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; // 维护容器对象
	};
1
2
3
4
5
6
7

---

1. push

void push(const T& val = T())
{
	_con.push_back(val);
}
1
2
3
4

2. pop

void pop()
{
	_con.pop_front();
}
1
2
3
4

3. front

const T& front() const
{
	return _con.front();
}
1
2
3
4

4. back

const T& back() const
{
	return _con.back();
}
1
2
3
4

5. empty

bool empty() const
{
	return _con.size() == 0;
}
1
2
3
4

6. size

size_t size() const
{
	return _con.size();
}
1
2
3
4

---

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;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---

deque

源码中， stack 和 queue的默认容器适配器给的是 deque.

我们来看一下deque的接口函数

我们惊奇的发现: deque不仅可以支持随机访问 [], 还支持 头插, 头删, 尾插, 尾删. 这不妥妥地是 vector 和 list 的结合体嘛.

🗨️那deque这么厉害, 我们之前为啥没有听过呢?

• 由于这个容器不值得我们去深度学习, 我这里就偷点懒, 盗用航哥的图了!
  

---

禅宗说了‘人人都有佛性’后就枯坐，什么都不管了。说了‘佛向心头做’后就真的在心头做，不去实践。而我说了‘在心上用功’后，必须去实践。