STL中常用的容器——stack,queue和list容器_stack容器中元素的进出顺序是先进先出

一，stack容器

1，stack容器概述：
stack 是一种先进后出(First In Last Out,FILO)的数据结构，它只有一个出口，形式 如图所示。stack 容器允许新增元素，移除元素，取得栈顶元素，但是除了最顶端 外，没有任何其他方法可以存取 stack 的其他元素。换言之，stack 不允许有遍历 行为。 有元素推入栈的操作称为:push,将元素推出 stack 的操作称为 pop.
如下：

2.stack迭代器
Stack 所有元素的进出都必须符合”先进后出”的条件，只有 stack 顶端的元素，才 有机会被外界取用。Stack 不提供遍历功能，也不提供迭代器。所以Stack没有迭代器。
3.stack 常用 API
3.1stack 构造函数

stack<T> stkT;//stack 采用模板类实现， stack 对象的默认构造形式： 
stack(const stack &stk);//拷贝构造函数
1
2

3.2stack 赋值操作

stack& operator=(const stack &stk);//重载等号操作符
1

3.3stack 数据存取操作

push(elem);//向栈顶添加元素 
pop();//从栈顶移除第一个元素 
top();//返回栈顶元素
1
2
3

3.4stack 大小操作

empty();//判断堆栈是否为空 
size();//返回堆栈的大小
1
2

二，queue容器

1.queue容器概述：
Queue 是一种先进先出(First In First Out,FIFO)的数据结构，它有两个出口，queue 容器允许从一端新增元素，从另一端移除元素。

2.queue迭代器
Queue 所有元素的进出都必须符合”先进先出”的条件，只有 queue 的顶端元素，才 有机会被外界取用。Queue 不提供遍历功能，也不提供迭代器。

3.queue 常用 API
3.1queue 构造函数

 queue<T> queT;//queue 采用模板类实现，queue 对象的默认构造形式： 
 queue(const queue &que);//拷贝构造函数
1
2

3.2 queue 存取、插入和删除操作

push(elem);//往队尾添加元素 
pop();//从队头移除第一个元素
back();//返回最后一个元素 
front();//返回第一个元素 
1
2
3
4

3.3 queue 赋值操作

queue& operator=(const queue &que);//重载等号操作符
1

3.5.3.4 queue 大小操作

 empty();//判断队列是否为空
  size();//返回队列的大小
1
2

注：上述API使用可参考vector容器

三，list容器

1.list概述
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点（组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据 元素的数据域，另一个是存储下一个结点地址的指针域。
相较于 vector 的连续线 性空间，它的好处是每次插入或者删除一个元素，就是配置 或者释放一个元素的空间。对于任何位置的元素插入或元素的移除，list 永远是常数时间。 List 和 vector 是两个最常被使用的容器。 List 容器是一个双向链表。

注：采用动态存储分配，不会造成内存浪费和溢出 链表执行插入和删除操作十分方 便，修改指针即可，不需要移动大量元素 链表灵活，但是时间复杂度和空间复杂度不是很好。
2. list 容器的迭代器
List 容器不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一 块连续的内存空间上。List 迭代器必须有能力指向 list 的节点，并有能力进行正确 的递增、递减、取值、成员存取操作。
所谓”list 正确的递增，递减、取值、成员取 用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的 数据值，成员取用时取的是节点的成员。 由于 list 是一个双向链表，迭代器必须 能够具备前移、后移的能力，所以 list 容器提供的是 Bidirectional Iterators. List 有 一个重要的性质，插入操作和删除操作都不会造成原有 list 迭代器的失效。
注意这在 vector 是不成立的，因为 vector 的插入操作可能造成记忆体重新配置，导致原有 的迭代器全部失效，甚至 List 元素的删除，也只有被删除的那个元素的迭代器失 效，其他迭代器不受任何影响。
3. list 容器的数据结构
list 容器不仅是一个双 向链表，而且还是一个循环的双向链表
4. list 常用 API
4.1 list 构造函数

   list<T> lstT;//list 采用采用模板类实现,对象的默认构造形式：
   list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。 
   list(n,elem);//构造函数将 n 个 elem 拷贝给本身。 
   list(const list &lst);//拷贝构造函数
1
2
3
4

。
4.2 list 数据元素插入和删除操作

push_back(elem);//在容器尾部加入一个元素 
pop_back();//删除容器中最后一个元素 
push_front(elem);//在容器开头插入一个元素 
pop_front();//从容器开头移除第一个元素 
insert(pos,elem);//在 pos 位置插 elem 元素的拷贝，返回新数据的位置。 insert(pos,n,elem);//在 pos 位置插入 n 个 elem 数据，无返回值。 
insert(pos,beg,end);//在 pos 位置插入[beg,end)区间的数据，无返回值。 
clear();//移除容器的所有数据 
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。 
erase(pos);//删除 pos 位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与 elem 值匹配的元素。
1
2
3
4
5
6
7
8
9
10

3.6.4.3 list 大小操作

 size();//返回容器中元素的个数 
 empty();//判断容器是否为空 
 resize(num);//重新指定容器的长度为 num， 若容器变长，则以默认值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除。 
 resize(num, elem);//重新指定容器的长度为 num， 若容器变长，则以 elem 值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除。 
1
2
3
4

3.6.4.4 list 赋值操作

 assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
  assign(n, elem);//将 n 个 elem 拷贝赋值给本身。 
  list& operator=(const list &lst);//重载等号操作符 
  swap(lst);//将 lst 与本身的元素互换。
1
2
3
4

3.6.4.5 list 数据的存取

 front();//返回第一个元素。 
  back();//返回最后一个元素。
1
2

3.6.4.6 list 反转排序

  reverse();//反转链表，比如 lst 包含 1,3,5 元素，运行此方法后，lst 就包含 5,3,1 元素。
  sort(); //list 排序
1
2

4.使用list容器实现简单的学生信息录入和删除功能

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

class Person
{
public:
	Person(int age, string name)
	{
		this->age = age;
		this->name = name;
	}
	int age;
	string name;
};

/*使用vector存储类成员名*/
vector<string> v;

/*用来存储对象的列表*/
list<Person> Test_List;

void print(Person& p)
{
	cout << p.age << "  " << p.name << endl;
}
void List_Con()
{
	list<Person>::iterator it_begin = Test_List.begin();
	list<Person>::iterator it_end = Test_List.end();
	cout << "------------------------------------------------------------------" << endl;
	if (it_begin != it_end)
	{
		for_each(it_begin, it_end, print);
	}
	else {
		cout << "列表内容为空 请先完成add操作" << endl;
	}
	cout << "------------------------------------------------------------------" << endl;
}
void Add()
{
	Person* p = new Person(10, "name");
	for (int i = 0; i < 2; i++)
	{
		cout << "请输入学生的" <<v[i] << endl;
		if(v[i] == "年龄") cin >> p->age;
		if (v[i] == "姓名") cin >> p->name;
	}
	Test_List.push_back(*p);
	cout << "添加名为" << p->name << "年龄为" << p->age << "的学生成功" << endl;
	
	delete p;
}

void Traversal_List(string name)
{
	list<Person>::iterator it_begin = Test_List.begin();
	list<Person>::iterator it_end = Test_List.end();

	for (; it_begin != it_end; it_begin++)
	{
		if (it_begin->name == name)
		{
			cout << "找到名为" << name << "的学生" << endl;
			break;
		}
	}
	if (it_begin == it_end)
	{
		cout << "没有找到想要删除的人名" << endl;
		return;
	}
	cout << "确定要删除吗? 请输入yes / no" << endl;
	string option;
	cin >> option;
	if (option == "yes")
	{
		Test_List.erase(it_begin);
		cout << "删除名为" << name << "的学生成功" << endl;
	}
	if (option == "no") return;
}

void Del()
{
	string temp;
	cout << "请输入要删除的人的name" << endl;
	cin >> temp;
	Traversal_List(temp);

}
void test01()
{
	string temp;
	
	cout << "请选择要进行的操作:" << endl;
	cout << "delete: 删除" << "   " << "add: 添加" << "   " << "print: 打印列表内容"<< endl;
	cin >> temp;
	if (temp == "add") Add();
	if (temp == "delete") Del();
	if (temp == "print") List_Con();

}
int main()
{
	v.push_back("年龄");
	v.push_back("姓名");

	while (true)
	{
		test01();
	}

	return 0;
}
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

执行效果：

上述代码可以加上成绩管理（排序，平均等）,更加完善。这里只是简单举例。如有错误，恳请大佬指出。