程序员经验分享-hwhale

2021-03-18-C++学习之17-stack、queue、list

2023-11-17

一、stack容器
1. stack基本概念

  • stack是一种先进后出（First In Last Out, FILO）的数据结构，它只有一个出口。
    在这里插入图片描述
    只有顶部元素才可以被外界使用，因此栈不允许有遍历行为。通常有empty函数来判断容器是否为空；size函数来返回元素个数。
    入栈 — push
    出栈 — pop

2. stack常用接口
功能：栈容器常用的对外接口

  • 构造函数：
    • stack<t> stk; //stack采用模板类实现，stack对象的默认构造形式
    • stack(const stack& stk); //拷贝构造函数
  • 赋值操作：
    • stack& operator=(const stack &stk); //重载等号操作符
  • 数据存取：
    • push(elem); //向栈顶添加元素
    • pop(); //从栈顶移除第一个元素
    • top(); //返回栈顶元素
  • 大小操作
    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小

代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<stack>
#include<algorithm> //标准算法头文件

void test01()
{
	//特点：先进后出的数据结构
	stack<int>stk1;
	//入栈
	//向栈顶添加元素
	stk1.push(10);
	stk1.push(20);
	stk1.push(30);
	stk1.push(40);

	//只要栈不为空，查看栈顶，并且执行出栈操作
	cout << "栈的大小：" << stk1.size() << endl;
	while (!stk1.empty())
	{
		//查看栈顶元素
		cout << "栈顶元素为：" << stk1.top() << endl;

		//出栈
		stk1.pop();
	}
	cout << "栈的大小：" << stk1.size() << endl;
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出：

栈的大小：4
栈顶元素为：40
栈顶元素为：30
栈顶元素为：20
栈顶元素为：10
栈的大小：0
请按任意键继续. . .
  • 总结：
    • 入栈 — push
    • 出栈 — pop
    • 返回栈顶 — top
    • 判断栈是否为空 — empty
    • 返回栈大小 — size

二、queue容器
1. queue基本概念
queue是一种先进先出（First In First Out, FIFO）的数据结构，它有两个出口。
在这里插入图片描述
只有对头和队尾被外界访问，因此不允许有遍历行为。

2. queue常用接口
功能：描述栈容器常用的对外接口。

  • 构造函数：
    • queue<T> que; //queue采用模板类实现，queue对象的默认构造形式
    • queue(const queue &que); //拷贝构造函数
  • 赋值函数：
    • queue& operator=(const queue &que); //重载等号操作符
  • 数据存取：
    • push(elem); //往队尾添加元素
    • pop(); //从对头移除第一个元素
    • back(); //返回最后一个元素
    • front(); //返回第一个元素
  • 大小操作
    • empty(); //判断堆栈是否为空
    • size(); //返回栈的大小

2. queue常用接口
代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<queue>
#include<algorithm> //标准算法头文件

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

void test01()
{
	queue<Person>q1;

	//准备数据
	Person p1("唐僧", 30);
	Person p2("孙悟空", 1000);
	Person p3("猪八戒", 900);
	Person p4("沙僧", 800);
	//入队
	q1.push(p1);
	q1.push(p2);
	q1.push(p3);
	q1.push(p4);

	//判断只要队列不为空，查看对头，查看队尾，出队
	cout << "队列大小为：" << q1.size() << endl;
	while (!q1.empty())
	{
		//查看对头元素
		cout << "队头元素 --- 姓名：" << q1.front().m_Name << " 年龄：" << q1.front().m_Age << endl;

		//查看队尾元素
		cout << "队尾元素 --- 姓名：" << q1.back().m_Name << " 年龄：" << q1.back().m_Age << endl;

		//出栈
		q1.pop();
		cout << endl;
	}
	cout << "队列大小为：" << q1.size() << endl;
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出：

队列大小为：4
队头元素 --- 姓名：唐僧 年龄：30
队尾元素 --- 姓名：沙僧 年龄：800

队头元素 --- 姓名：孙悟空 年龄：1000
队尾元素 --- 姓名：沙僧 年龄：800

队头元素 --- 姓名：猪八戒 年龄：900
队尾元素 --- 姓名：沙僧 年龄：800

队头元素 --- 姓名：沙僧 年龄：800
队尾元素 --- 姓名：沙僧 年龄：800

队列大小为：0
请按任意键继续. . .

三、list容器
1. list基本概念

  • 功能：将数据进行链式存储‘

  • 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接来实现的。

  • 链表的组成：链表由一系列结点组成

  • 结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

  • STL中的链表是一个双向循环链表

  • 链表和数组：
    在这里插入图片描述

  • 链表优点：可以对任意位置进行插入或删除元素。

  • 链表缺点：容器的元素的遍历速度没有数组快，而且占用空间比数组大。
    STL中的链表是一个双向循环链表：
    在这里插入图片描述

  • 双向循环链表是指一个结点既指向下一个结点，又指向前一个结点的地址，第一个结点所指向的前一个结点是最后一个结点的地址，最后一个结点所指向的地址是第一个结点的地址。

  • 由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器。

  • list的优点：

    • 采用动态存储分配，不会造成内存浪费和溢出
    • 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素

  • list缺点：

    • 链表灵活，但是空间（指针域）和时间（遍历）额外耗费比较大

  • List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。

  • 总结：STL中，List和vector是两个最常用的容器。

2. list构造函数
函数原型：
在这里插入图片描述
代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//添加数据
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	//遍历容器
	printList(l1);

	//区间方式构造
	list<int>l2(l1.begin(), l1.end());
	printList(l2);

	//拷贝构造
	list<int>l3(l2);
	printList(l3);

	//n个elem
	list<int>l4(3, 100);
	printList(l4);
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出;

10 20 30 40
10 20 30 40
10 20 30 40
100 100 100
请按任意键继续. . .

3. List赋值和交换
函数原型：
在这里插入图片描述
代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
//赋值
void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//添加数据
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	//遍历容器
	printList(l1);

	list<int>l2;
	l2 = l1;//operator= 赋值
	printList(l2);

	list<int>l3;
	l3.assign(l2.begin(), l2.end());
	printList(l3);

	list<int>l4;
	l4.assign(3, 100);
	printList(l4);
}
//交换
void test02()
{
	//创建list容器
	list<int>l1; //默认构造
	//添加数据
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	list<int>l2;
	l2.assign(3, 100);
	cout << "---------交换前---------" << endl;
	cout << "l1：";
	printList(l1);
	cout << "l2：";
	printList(l2);

	l1.swap(l2);
	cout << "---------交换后---------" << endl;
	cout << "l1：";
	printList(l1);
	cout << "l2：";
	printList(l2);
}

int main()
{
	test01();
	test02();
	
	system("pause");
	return 0;
}

输出：

10 20 30 40
10 20 30 40
10 20 30 40
100 100 100
---------交换前---------
l1：10 20 30 40
l2：100 100 100
---------交换后---------
l1：100 100 100
l2：10 20 30 40
请按任意键继续. . .

4. list大小操作
函数原型：
在这里插入图片描述
代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//添加数据
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);

	//遍历容器
	printList(l1);

	//判断容器是否为空
	if (l1.empty())
	{
		cout << "l1为空" << endl;
	}
	else
	{
		cout << "l1不为空" << endl;
		cout << "l1的元素个数为：" << l1.size() << endl;
	}

	//重新指定大小
	//大小为10，用10000来填充
	l1.resize(10, 10000);
	//10 20 30 40 10000 10000 10000 10000 10000 10000
	printList(l1);

	l1.resize(2);
	//10 20
	printList(l1);
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出：

10 20 30 40
l1不为空
l1的元素个数为：4
10 20 30 40 10000 10000 10000 10000 10000 10000
10 20
请按任意键继续. . .

5. list插入和删除
函数原型：
在这里插入图片描述
代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

void printList(const list<int>& l)
{
	for (list<int>::const_iterator it = l.begin(); it != l.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//头插
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	//尾插
	l1.push_front(100);
	l1.push_front(200);
	l1.push_front(300);
	//遍历容器
	//300 200 100 10 20 30
	printList(l1); 
		
	//尾删
	l1.pop_back();
	//300 200 100 10 20
	printList(l1);

	//头删
	l1.pop_front();
	//200 100 10 20
	printList(l1);

	//insert插入
	list<int>::iterator it = l1.begin();
	l1.insert(++it, 10000);
	//200 10000 100 10 20
	printList(l1);

	//删除
	it = l1.begin();
	l1.erase(++it);
	//200 100 10 20
	printList(l1);

	//移除
	l1.push_back(10000);
	l1.push_back(10000);
	l1.push_back(10000);
	l1.push_back(10000);
	// 10000 10000 10000 10000
	printList(l1);

	l1.remove(10000);
	//200 100 10 20
	printList(l1);

	//清空
	l1.clear();
	//换行
	printList(l1);
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出：

300 200 100 10 20 30
300 200 100 10 20
200 100 10 20
200 10000 100 10 20
200 100 10 20
200 100 10 20 10000 10000 10000 10000
200 100 10 20

请按任意键继续. . .
  1. list数据存取
    函数原型：
  • front(); //返回第一个元素
  • back(); //返回最后一个元素

代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//头插
	l1.push_back(10);
	l1.push_back(20);
	l1.push_back(30);
	l1.push_back(40);
	
	//l1[0]; //不可以用[]访问list容器中的元素
	//l1.at(0);  //不可以用at方式访问list容器中的元素
	//原因是list本质是链表，不是用连续线性空间存储数据，迭代器也是不支持随机访问
	cout << "第一个元素为：" << l1.front() << endl;  //10
	cout << "最后一个元素为：" << l1.back() << endl; //40

	//验证迭代器是不支持随机访问的
	list<int>::iterator it = l1.begin();
	it++;//正确，支持双向
	it--;//正确，支持双向
	// it = it + 1; //错误，因为也可以是it = it + 3;  这样就是跳着的随机访问了
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

7. list反转和排序
函数原型：

  • reverse(); //反转链表
  • sort(); //链表排序

代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

//加const为了防止误操作
void printList(const list<int>& L)
{
	for (list<int>::const_iterator it = L.begin(); it != L.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test01()
{
	//创建list容器
	list<int>l1; //默认构造
	//头插
	l1.push_back(20);
	l1.push_back(10);
	l1.push_back(50);
	l1.push_back(40);
	l1.push_back(30);
	cout << "反转前：";
	//反转前：20 10 50 40 30
	printList(l1);
	
	//反转
	l1.reverse();
	cout << "反转后：";
	//反转后：30 40 50 10 20
	printList(l1);
}
//回调函数
bool myCompare(int v1, int v2)
{
	//降序：就让第一个数 > 第二个数
	return v1 > v2;
}
//排序
void test02()
{
	list<int>l1; //默认构造
	//头插
	l1.push_back(20);
	l1.push_back(10);
	l1.push_back(50);
	l1.push_back(40);
	l1.push_back(30);
	cout << "排序前：";
	//排序：20 10 50 40 30
	printList(l1);

	//排序，不能用全局函数sort()进行排序，要用迭代器的成员函数l1.sort()进行排序
	//所有不支持随机访问迭代器的容器，不可以用标准算法
	//不支持随机访问迭代器的容器，内部会提供对应的一些算法
	//sort(l1.begin(),l1.end()); //错误
	//默认从小到大排序
	l1.sort();
	cout << "排序（默认升序）后：";
	printList(l1);

	l1.sort(myCompare);
	cout << "排序（降序）后：";
	printList(l1);
}

int main()
{
	test01();
	test02();
	
	system("pause");
	return 0;
}

输出：

反转前：20 10 50 40 30
反转后：30 40 50 10 20
排序前：20 10 50 40 30
排序（默认升序）后：10 20 30 40 50
排序（降序）后：50 40 30 20 10
请按任意键继续. . .

8. 排序案例

  • 案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
  • 排序规则：按照年龄进行升序排序，如果年龄相同按照身高进行排序。

代码测试：

#include<iostream>
using namespace std;
#include<string>
//STL中的每个容器在使用时都需要包含头文件
#include<list>
#include<algorithm> //标准算法头文件

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

//指定排序规则
bool comparePerson(Person& p1, Person& p2)
{
	if (p1.m_Age == p2.m_Age)
	{
		//年龄相同，按照身高降序排列
		return p1.m_Height > p2.m_Height;
	}
	else
	{
		//年龄升序排列
		return p1.m_Age < p2.m_Age;
	}
}
void test01()
{
	list<Person>L;

	//准备数据
	Person p1("刘备", 35, 175);
	Person p2("曹操", 45, 180);
	Person p3("孙权", 40, 170);
	Person p4("赵云", 25, 190);
	Person p5("张飞", 35, 160);
	Person p6("关羽", 35, 200);
	//向容器中插入数据
	L.push_back(p1);
	L.push_back(p2);
	L.push_back(p3);
	L.push_back(p4);
	L.push_back(p5);
	L.push_back(p6);

	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名：" << (*it).m_Name << " 年龄：" << (*it).m_Age << " 身高：" << (*it).m_Height << endl;
	} 

	//排序
	cout << "--------排序后--------" << endl;
	L.sort(comparePerson);
	for (list<Person>::iterator it = L.begin(); it != L.end(); it++)
	{
		cout << "姓名：" << (*it).m_Name << " 年龄：" << (*it).m_Age << " 身高：" << (*it).m_Height << endl;
	}
}

int main()
{
	test01();
	
	system("pause");
	return 0;
}

输出：

姓名：刘备 年龄：35 身高：175
姓名：曹操 年龄：45 身高：180
姓名：孙权 年龄：40 身高：170
姓名：赵云 年龄：25 身高：190
姓名：张飞 年龄：35 身高：160
姓名：关羽 年龄：35 身高：200
--------排序后--------
姓名：赵云 年龄：25 身高：190
姓名：关羽 年龄：35 身高：200
姓名：刘备 年龄：35 身高：175
姓名：张飞 年龄：35 身高：160
姓名：孙权 年龄：40 身高：170
姓名：曹操 年龄：45 身高：180
请按任意键继续. . .
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

学习笔记

c

2021-03-18-C++学习之17-stack、queue、list 的相关文章

随机推荐

  • maven配置华为云镜像

    第一步 在maven的目录中找到配置文件 D softwaretools apache maven 3 5 4 conf settings xml 第二步 配置华为云服务器 在server标签下粘贴

  • springboot常用注解详解

    在springboot中 经常会用到一些注解 它们各自代表着什么呢 在这个属于我们的节日里 快来了解一下吧 1 SpringBootApplication 一般不会主动去使用它 但是要知道它是一个组合注解 Configuration Ena

  • java-php-python-ssm校园统一网络授课平台系统计算机毕业设计

    java php python ssm校园统一网络授课平台系统计算机毕业设计 java php python ssm校园统一网络授课平台系统计算机毕业设计 本源码技术栈 项目架构 B S架构 开发语言 Java语言 开发软件 idea ec

  • benchmarking graph neural networks 翻译

    摘要 图神经网络 GNN 已成为分析和学习图数据的标准工具包 随着领域的发展 确定关键架构并验证可推广到更大 更复杂的数据集的新思路变得至关重要 不幸的是 在缺乏具有一致实验设置的标准化基准的情况下 评估新模型的有效性变得越来越困难 在本文

  • 【DLL】【一文搞懂】【学习笔记】（四）GetProcAddress函数

    官方文档 GetProcAddress 函数用于获取DLL中导出函数的地址 显式链接时使用 GetProcAddress将 DLL 模块处理 由LoadLibrary 或 GetModuleHandle 返回的参数 并采用要调用的函数的名称

  • 第四章 Verilog 逻辑设计介绍

    第四章 Verilog 逻辑设计介绍 4 1 组合逻辑的结构化模型 介绍了verilog 原语 即一些基本的逻辑门 例化时不必写例华名 介绍了verilog module 的结构 4 2 逻辑系统的验证和测试方法 四值逻辑 0 1 x z

  • 用MD5实现hash长度扩展攻击 By Assassin

    今天心血来潮 看到了扩展攻击 猛然想到了之前看的扩展攻击的原理还没有弄懂 这里补充一下 hash长度扩展攻击到底是怎么实现的 题目 首先从实验吧上面见到的经典的题目 下面给出源码

  • Python Flask+Echarts+sklearn+MySQL(评论情感分析、用户推荐、BI报表)项目分享

    Python Flask Echarts sklearn MySQL 评论情感分析 用户推荐 BI报表 项目分享 项目背景 随着互联网的快速发展和智能手机的普及 人们越来越倾向于在网上查找餐厅 购物中心 酒店和旅游景点等商户的点评和评分信息

  • 掌握 Ajax，第 5 部分：操纵 DOM

    Brett McLaughlin 作者 编辑 O Reilly Media Inc 2006 年 4 月 27 日 如果阅读过本系列的 上一篇文章 那么您就非常清楚当 Web 浏览器显示网页时幕后发生的一切了 前面已经提到 当 HTML 或

  • 实验室云平台架构学习笔记

    这些日子学习了实验室云平台的体系架构 在多次与小孟哥请教后对该架构有了一定了解 首先应明白建立云平台的目的 与传统的服务器相比 云平台可以将物理资源虚拟化为虚拟机资源池 灵活调用软硬件资源 实现对用户的按需访问 而且在运行过程中根据用户并发

  • LeetCode刷题笔记-压缩字符串

    压缩字符串 给你一个字符数组 chars 请使用下述算法压缩 从一个空字符串 s 开始 对于 chars 中的每组 连续重复字符 如果这一组长度为 1 则将字符追加到 s 中 否则 需要向 s 追加字符 后跟这一组的长度 压缩后得到的字符串

  • 10个程序员常用的代码简写技术，看懂一种是入门，全懂就是大神

    今天小编我给大家整理了一份10个程序员常用的代码简写技术 看懂一种是入门 全懂就是大神 你能知道几个呢 这篇文章分享之前我还是要推荐下我自己的前端群 595549645 不管你是小白还是大牛 小编我都挺欢迎 不定期分享干货 包括我自己整理的

  • Qt 模型视图编程之自定义只读数据模型

    背景 Qt 中的模型视图架构是用来实现大量数据的存储 处理及其显示的 主要原理是将数据的存储与显示分离 模型定义了标准接口对数据进行访问 视图通过标准接口获取数据并定义显示方式 模型使用信号与槽机制通知视图数据变化 QModelIndex

  • asm.js 和 Emscripten 入门教程

    文章转载自 http www ruanyifeng com blog 2017 09 asmjs emscripten html Web 技术突飞猛进 但是有一个领域一直无法突破 游戏 游戏的性能要求非常高 一些大型游戏连 PC 跑起来都很

  • Webpack5 搭建Vue项目（进阶版）

    Webpack5 搭建Vue项目 进阶版 提示 中间隔了好长时间 我胡汉三又回来继续更新了 文章目录 Webpack5 搭建Vue项目 进阶版 前言 一 进阶版本有哪些特点 二 主要的文件代码如下 1 设置一个公共配置 webpack co

  • 使用小工具QuickLook的使用

    终于期末考试结束了 正式步入科研生活 今天正好看到了quicklook这个软件 就顺便下载一下来试试 经常我们困难会为了简单的查看一个文件 却要等待一个大型软件的缓慢加载过程 比如 m ppt文件 在使用这个软件后 不必等待 重型 的 Of

  • 快速从网页爬取图片数据

    1 代码实现 import os import re import time from selenium import webdriver from bs4 import BeautifulSoup from urllib request

  • 数据采集与埋点简介之 代码埋点、可视化埋点与无痕埋点

    转自 https sensorsdata cn blog shu ju jie ru yu mai dian 博主做移动手机系统中的数据采集与埋点也有近两年 那段时间内一方面是集中在具体的开发和问题细节处理 另外一方面则是在把采集系统适配到

  • 数据库性能

    1 建立合理的索引 2 优化SQL语句 3 优化表结构 能用小字段类型就用小字段类型 如能用short就不用int 能用数据类型就不用字符串类型 4 拆分表 横向拆分不更改表结构 重复多建立几张表 纵向拆分影响表结构 通过索引连接多个表 5

  • 2021-03-18-C++学习之17-stack、queue、list

    一 stack容器 1 stack基本概念 stack是一种先进后出 First In Last Out FILO 的数据结构 它只有一个出口 只有顶部元素才可以被外界使用 因此栈不允许有遍历行为 通常有empty函数来判断容器是否为空 s

热门标签