C++ stack queue 的模拟实现

1.为什么选择 deque 作为 stack 和 queue 的默认容器呢？

stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可 以作为 stack 的底层容器，比如 vector 和 list 都可以；

queue 是先进先出的特殊线性数据结构，只要具有 push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是 STL 中对 stack 和 queue 默认选择deque 作为其底层容器，主要是因为：

1. stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque 比 vector 效率高(扩容时不需要搬移大量数据)；deque 中的元素增长时，deque 不仅效率高，而且内存使用率高。 结合了deque 的优点，而完美的避开了其缺陷。

➡️deque 的使用:c++ deque 的使用-CSDN博客

2. 模拟实现 stack

前面提到，stack 的实现是有一个默认的容器：deque 的，因此在 stack 模板参数列表中就一定有一个模板参数，接收 stack 的底层使用哪一个容器来实现的！因此我们就可以定义出 stack 的基本结构啦！😄

namespace Tchey
{
	template>
	class stack
	{
	public:

	private:
		Container _con;
	};
}
1
2
3
4
5
6
7
8
9
10
11

2.1 默认构造函数

默认构造函数可以不用写哈，我们的 stack 类有一个自定义类型的成员，会调用自定义类型成员的默认构造函数。

2.2 void push(const T& val)

这个接口的实现，我们只需要调用 Container 对应的接口就行了！

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

2.3 void pop()

删除栈顶的元素。

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

2.4 T& top()

查看栈顶的元素。

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

2.5 bool empty()

判断栈是否为空。

bool empty()
{
	return _con.empty();
}
1
2
3
4

2.6 size_t size()

获取栈中元素的个数。

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

3. 模拟实现 queue

模拟实现 queue 的方法跟模拟实现栈是一毛一样的哈！😸

namespace Tchey
{
	template>
	class queue
	{
	public:
		// 队尾入数据
		void push(const T& val)
		{
			_con.push_back(val);
		}
		// 队头出数据
		void pop()
		{
			_con.pop_front();
		}
		// 获取队头数据
		T& front()
		{
			return _con.front();
		}
		// 获取队尾数据
		T& back()
		{
			return _con.back();
		}
		// 判断队列是否为空
		bool empty()
		{
			return _con.empty();
		}
		// 获取队列中元素的个数
		size_t size()
		{
			return _con.size();
		}


	private:
		Container _con;

	};
}
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
33
34
35
36
37
38
39
40
41
42
43