C++初阶：容器适配器介绍、stack和queue常用接口详解及模拟实现

介绍完了list类的相关内容后：C++初阶：适合新手的手撕list（模拟实现list）
接下来进入新的篇章，stack和queue的介绍以及模拟：

---

---

1.stack的初步介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下

操作：

• empty：判空操作

• back：获取尾部元素操作

• push_back：尾部插入元素操作

• pop_back：尾部删除元素操作

4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

---

2.stack的使用

#include<iostream>
#include<stack>
using namespace std;

int main()
{
	stack<int> st;//一个空栈
	st.push(1);
	st.push(2);
	st.push(3);//push进去3个
	while (!st.empty())//当st不空进循环
	{
		cout << st.top() << endl;//输出栈顶元素
		st.pop();//栈顶出栈
	}//遍历结束

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

3.queue的初步介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

• empty：检测队列是否为空
• size：返回队列中有效元素的个数
• front：返回队头元素的引用
• back：返回队尾元素的引用
• push_back：在队列尾部入队列
• pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

---

4.queue的使用

#include<iostream>
#include<queue>
using namespace std;

int main()
{
	queue<int> q;//一个空队列
	q.push(1);
	q.push(2);
	q.push(3);//push进去3个
	while (!q.empty())//当q不空进循环
	{
		cout << q.front() << endl;//输出队头元素
		q.pop();//出队
	}//遍历结束
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

5.容器适配器

5.1含义

容器适配器是一种将现有的容器类型适配为不同接口的容器的工具。C++标准库提供了三种主要的容器适配器：栈（stack）、队列（queue）和优先队列（priority_queue）。这些适配器都是基于现有的序列容器（如vector、deque或list）实现的，但提供了不同的接口和行为。

1. 栈（stack）：栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶进行插入和删除操作。在C++中，栈适配器基于deque或vector实现，提供了push、pop、top等操作。
2. 队列（queue）：队列是一种先进先出（FIFO）的数据结构，它允许在队列的前端进行删除操作，在队列的后端进行插入操作。在C++中，队列适配器也基于deque或list实现，提供了push、pop、front、back等操作。
3. 优先队列（priority_queue）：优先队列是一种特殊的队列，它根据元素的优先级进行排序。在C++中，优先队列适配器基于vector实现，提供了push、pop、top等操作。

今天先来模拟栈和队列。优先队列，下次单独细讲

怎么理解“适配为不同接口的容器”：

容器适配器（上述三种）提供的操作接口与底层容器的操作接口不同。虽然容器适配器底层使用了常见的序列容器（如vector、deque或list）来存储数据，但是它们暴露的操作接口与这些底层容器不同。

举个例子，让我们比较一下栈（stack）适配器和vector容器的接口：

1. 栈（stack）适配器的接口：

• push：将元素压入栈顶
• pop：弹出栈顶元素
• top：访问栈顶元素

2. vector容器的接口：

• push_back：在vector的末尾插入元素
• pop_back：删除vector的末尾元素
• back：访问vector的末尾元素

如你所见，尽管栈适配器的底层容器可能是vector，但它提供了与vector不同的操作接口。栈适配器隐藏了vector的细节，只暴露了栈的相关操作，使得我们可以更方便地使用栈这种数据结构。

5.2STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

---

6.模拟stack和queue

文件规划和一览

stack.h:用来实现stack

queue.h:用来实现queue

test.cpp:进行测试

6.1模拟stack（stack.h）

#pragma once

namespace MyStack
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		//构造函数、析构函数之类的会去调用传过来的的类的

		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}

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

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

		bool empty()
		{
			return _con.empty();
		}

	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

6.2模拟queue（queue.h）

#pragma once

namespace MyQueue
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		//构造函数、析构函数之类的会去调用传过来的的类的

		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}

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

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

		bool empty()
		{
			return _con.empty();
		}

	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

---

好啦大家，这次就到这里啦！！下次就带来优先级队列priority_queue的介绍和模拟。感谢大家