【C++修行之道】STL（初识list、stack）

一、list

1.1list的定义和结构

以下是一个示例，展示如何使用list容器:

1.2list的常用函数

1.3list代码示例

二、stack

2.1stack的定义和结构

stack的常用定义

2.2常用函数

2.3stack代码示例

一、list

1.1list的定义和结构

list的使用频率不高，在做题时极少遇到需要使用list的情景。
ist是一种双向链表容器，它是标准模板库(STL)提供的一种序列容器。
list容器以节点(node)的形式存储元素，并使用指针将这些节点链接在一起，形成一个链表结构。
list容器的定义和结构如下：

template <class T, class Allocator = std::allocator<T>>class list;

list容器模板接受两个参数：

T:指定容器中存储的元素类。
Allocator (可选):指定用于分配内存的分配器类型，默认为std::allocator<T>。

list容器的特点包括:

双向性:每个节点都包含指向前一个节点和后一个节点的指针，因此可以在常数时间内在链表中的任意位置进行插入、删除和访问操作。
动态大小: 链表的大小可以根居需要动态扩展或收缩，不需要预先指定容器的大小
不连续存储:链表中的节点可以在内存中的任意位置分布，不要求连续存储因此插入和删除操作不会导致元素的移动。
list与其他标准序列容器（array，vector和deque）相比，list通常可以在容器内的任何位置插入、提取和移动元素。
list与其他标准序列容器（array，vector和deque）相比，list和forward_list（单链表实现）的主要缺点是他们不能通过位置直接访问元素；例如，要访问列表中的第五个元素，必须从已知位置（开始或结束）迭代到该位置，需要线性时间开销。
存储密度低，list要使用一些额外的内容空间（next，prev）来保持与每个元素相关联（前后续的线性）的链接信息，从而导致存储小元素类型（如char，short，int等）的列表的存储密度低。

list容器提供了一系列成员函数和迭代器来操作和访问链表中的元素，包括插入、删除、访问、反转等操作。可以使用迭代器来遍历链表中的元素。

以下是一个示例，展示如何使用list容器:

#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> myList;

	//在链表尾部插入元素
	myList.push_back(1);
	myList.push_back(2);
	myList.push_back(3);

	//在链表头不插入元素
	myList.push_front(0);

	//遍历链表并输出元素
	for (int num : myList) {
		cout << num << " ";
	}
	cout << endl;

	return 0;
}

在上述示例中，我们首先创建了一个list容器myList，然后使用push_back()和push_front()函数分别在链表尾部和头部插入元素。最后，使用范围基于范围的for循环遍历链表并输出元素。
需要注意的是，由于list是双向链表，因此插入和删除操作的时间复杂度是常量时间O(1)，但访问和查找操作的时间复杂度是线性时间O(n)，其中n是链表的大小。因此，如果需要频繁进行随机访问操作，可能更适合使用支持随机访问的容器，如vector或deque。

随机访问：begin()+idex，得到迭代器

1.2list的常用函数

list容器提供了多个常用的成员函数来操作和访问链表中的元素以下是一些常用的list函数的解释:

push _back():将元素插入到链表的末尾。
push front():将元素插入到链表的开头。
pop back():移除链表末尾的元素。
pop_front():移除链表开头的元素。
size():返回链表中元素的个数。
empty():检查链表是否为空。
clear():清空链表中的所有元素。
front():返回链表中第一个元素的引用。
back():返回链表中最后一个元素的引用。
begin(): 返回指向链表第一个元素的迭代器。
end(): 返回指向链表末尾的下一个位置的迭代器。
insert():在指定位置之前插入一个或多个元素。
.erase():从链表中移除指定位置的一个或多个元素。

1.3list代码示例

在代码中，我们向myList的尾部添加了5个元素，从1到5。

int main()
{
	//创建一个List<int>对案myList
	list<int> myList;
	//向myList尾部添加元素
	for (int i = 1; i <= 5; ++i)
	{
		myList.push_back(i);
	}

然后，我们使用范围for循环遍历myList并输出其中的元素。输出结果为：1 2 3 4 5 。

// 从头到尾输出myList中的元素
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';

使用reverse函数将myList中的元素反转，并输出反转后的结果。输出为：5 4 3 2 1 。

//将myList中的元素反转
	reverse(myList.begin(), myList.end());
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';

再使用myList.begin()获取链表的第一个迭代器，然后使用++操作符将其移动到第二个元素的位置。接着，我们使用insert函数在这个位置插入元素0。输出结果为：5 0 4 3 2 1 。

//在第一个元素的后一个位置加上元素0
	myList.insert(++myList.begin(), 0);

删除链表中的一部分元素。++++myList.begin()将迭代器移动到链表的第三个元素，而--myList.end()将迭代器移动到链表的倒数第二个元素之前的位置。因此，这行代码将删除从第三个元素到倒数第二个元素之间的所有元素。

for (const auto& i : myList)cout << i << ' ';
	cout << '\n';

	myList.erase(++++myList.begin(), -- myList.end());

	//输出myList的大小
	cout << "链表大小为: " << myList.size() << '\n';

	//从头到尾输出myList中的元素
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';

int main()
{
	//创建一个List<int>对案myList
	list<int> myList;
	//向myList尾部添加元素
	for (int i = 1; i <= 5; ++i)
	{
		myList.push_back(i);
	}
	// 从头到尾输出myList中的元素
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';
	//将myList中的元素反转
	reverse(myList.begin(), myList.end());
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';
	//在第一个元素的后一个位置加上元素0
	myList.insert(++myList.begin(), 0);

	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';

	myList.erase(++++myList.begin(), -- myList.end());

	//输出myList的大小
	cout << "链表大小为: " << myList.size() << '\n';

	//从头到尾输出myList中的元素
	for (const auto& i : myList)cout << i << ' ';
	cout << '\n';
}

二、stack

2.1stack的定义和结构

在C++中，stack是一个标准库容器，它提供了后进先出（LIFO, Last In First Out）的数据结构。stack容器只允许在序列的同一端（称为栈顶）进行插入和删除操作。stack没有迭代器，因此你不能像遍历其他容器（如vector或list）那样遍历stack。相反，你只能查看栈顶元素、向栈中添加元素或从栈中移除元素。

stack提供了一组函数来操作和访问元素，但它的功能相对较简单。stack的定义和结构如下 (仅作了解即可)：

template <class T, class Container = deque<T>>
class stack;

T:表示存储在stack中的元素的类型

Container: 表示底层容器的类型，默认为deque。也可以使用其他容器类型，如vector或list、stack的内部实现使用了底层容器来存储元素，并且只能通过特定的函数来访问和操作元素。

stack的常用定义

//stack的定义 
stack<int>s1; //定义一个储存数据类型为int的stack容器s1 
stack<double>s2; //定义一个储存数据类型为double的stack容器s2
stack<string>s3; //定义一个储存数据类型为string的stack容器s3
stack<结构体类型>s4; //定义一个储存数据类型为结构体类型的stack容器s4
stack<int> s5[N]; //定义一个储存数据类型为int的stack容器数组,N为大小 
stack<int> s6[N]; //定义一个储存数据类型为int的stack容器数组,N为大小

2.2常用函数

stack不能遍历

函数	描述	时间复杂度
push(x)	在栈顶插入元素 x	0(1)
pop	弹出栈顶元素	0(1)
top	返回栈顶元素	0(1)
empty	检查栈是否为空	0(1)
size	返回栈中元素的个数	0(1)

小tips: 如果将一个数组的元素依次放入栈，再依次取出，则可以将数组翻转。

2.3stack代码示例

#include<iostream>
#include<stack>

using namespace std;

int main()
{
	stack<int>myStack;

	//向栈中插入元素
	myStack.push(10);
	myStack.push(20);
	myStack.push(30);
	myStack.push(40);

	//获取栈顶元素
	cout << "栈顶元素" << myStack.top() << endl;

	//弹出栈顶元素
	myStack.pop();

	//再次获取栈顶元素
	cout << "弹出一个元素后的栈顶元素" << myStack.top() << endl;

	//检查栈是否为空
	if (myStack.empty()) {
		cout << "栈为空" << endl;
	}
	else {
		cout << "栈不为空" << endl;
	}

	//获取栈的大小
	cout << "栈的大小" << myStack.size() << endl;

	return 0;
}