STL常用容器—stack与queue容器(栈与队列)

发布时间:2024年01月24日

参考博文1:<C++> stack与queue容器概念模型|常用接口汇总
参考博文2: STL常用容器——queue容器的使用

??本文主要介绍C++ STL中的stack和queue两大容器的基本概念与方法调用,不涉及具体的底层实现,若要了解堆栈的底层设计与程序实现,请参考数据结构与算法专栏中的:

  1. 数据结构与算法基础——栈的原理及C语言底层实现
  2. 数据结构与算法基础——队列原理及C语言底层实现

stack容器

1. stack容器模型图

2. stack 基本概念

  • stack是一种 先进后出 (First In Last Out,FILO)的数据结构,它只有一个出口。
  • 允许进行操作的一端称为“栈顶”,另一固定端称为“栈底”
  • 栈中进入数据称为 入栈 push,栈中弹出数据称为 出栈 pop
  • 栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为,也不提供迭代器
  • 使用stack容器需要引入头文件 #include <stack>
  • 能够判断容器是否为空和得到元素个数,通过入栈来计数,并不是对出栈计数
  • 当栈中没有元素时称为 “空栈

生活中的栈:

3. stack 常用接口

构造函数:

函数原型功能
stack<T> stk;stack采用模板类实现, stack对象的默认构造形式
stack(const stack &stk);拷贝构造函数

赋值操作:

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

数据存取:

方法功能
push(elem);向栈顶一个元素
pop();从栈顶移除第一个元素,返回值为void
top( );返回栈顶元素

大小操作:

方法功能
empty( );判断堆栈是否为空
size( );返回栈的大小

示例:

#include <stack>

void stack_test()
{
	stack<int> s;	//定义栈
	
	//数据入栈
	s.push(10);
	s.push(20);
	s.push(30);
	s.push(40);

	cout << "栈的起始大小为: " << s.size() << endl;
	while(!s.empty())
	{
		//输出栈顶元素
		cout << "栈顶元素为: " << s.top() << endl;
		s.pop();	//出栈
	}
	
	cout << "栈的终止大小为: " << s.size() << endl;
}

总结:

  • 入栈 — push(x)
  • 出栈 — pop()
  • 返回栈顶 — top()
  • 判断栈是否为空 — empty()
  • 返回栈大小 — size()

queue 容器

1. queue 容器模型图

2. queue 基本概念

  • queue是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口
  • 队列容器规定从一端新增元素,从另一端移除元素
  • 允许进行插入操作的一端称为“队尾
  • 允许进行移除操作的一端称为“队头
  • 队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为,也不提供迭代器
  • 使用queue容器需要引入头文件 #include <queue>
  • 队列中插入数据称为 入队 push,移除称为 出队 pop
  • 能够判断容器是否为空和得到元素个数

生活中的队列:

3. queue 常用接口

??queuestack常用接口几乎一致,唯一不同的就是队列的队首和队尾与堆栈的栈顶表示有所不同

构造函数:

函数原型功能
queue<T> que;queue采用模板类实现,queue对象的默认构造形式
queue(const queue &que);拷贝构造函数

赋值操作:

  • queue& operator=(const queue &que); ??// 已经重载等号操作符

数据存取:

方法功能
push(elem);往队尾添加元素
pop();从队头移除第一个元素,返回值为void
back( );返回最后一个元素
front( );返回第一个元素

大小操作:

方法功能
empty();判断队列是否为空
size( );返回队列的大小

示例代码:

#include <queue>

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

void queue_test()
{
	queue<Person> sq;
	
	//实例化对象并入队
	Person p1("张三",18);
	Person p2("李四",22);
	Person p3("王五",20);
	Person p4("陈六",21);
	sq.push(p1);
	sq.push(p2);
	sq.push(p3);
	sq.push(p4);
	
	cout << "队列的起始大小为: " << sq.size() << endl;
	while(!sq.empty())
	{
		//获取队头信息
		cout << "name: "  << sq.front().name;
		cout << "\tage: " << sq.front().age << endl;
		sq.pop();	//出队
	}
	cout << "队列的终止大小为: " << sq.size() << endl;
}

总结:

  • 入队 — push
  • 出队 — pop
  • 返回队头元素 — front
  • 返回队尾元素 — back
  • 判断队是否为空 — empty
  • 返回队列大小 — size
文章来源:https://blog.csdn.net/weixin_46216674/article/details/135641242
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。