前言
在C++标准模板库(STL)的广阔世界中,容器是构建高效程序的基石。它们如同一个个精心设计的容器盒,以不同的结构和规则存储、管理数据,满足程序在不同场景下的需求。queue
和stack
作为STL容器家族中的重要成员,以其独特的数据结构和操作特性,在算法设计、程序逻辑构建以及资源管理等多方面发挥着不可替代的作用。
接下来,让我们开启对queue
和stack
这两个STL容器的深入探索之旅。
队列——queue
队列(Queue)是一种遵循先进先出(First In First Out,简称 FIFO)原则的线性数据结构。就像日常生活中人们排队等候一样,最先进入队列的元素将最先被处理或移除。
向队列中添加元素,只能从最末尾添加
删除队列中的元素,只能从头部删除
这样,最先进入的元素会先被删除,达成先进先出的准则
构造函数
要使用,得先构造
方法一:默认构造
std::queue<T> q;//直接创造一个空的queue对象
方法二:使用初始化列表构造
queue<T> q = { elem1, elem2, ..., elemN };
入队——push函数
push
操作用于在队列的末尾插入一个新元素。。
函数造型:
void push(const T& value);
参数说明:
const T& value
:要插入队列的元素的常量引用。
基本用法:
std::queue<int> q;
//使用 push 添加元素
q.push(10);
出列——pop函数
pop
函数用于移除队列的第一个元素(即队首元素)。
函数造型:
void pop();
基本用法:
std::queue<int> q;q.push(10);//使用 push 添加元素q.pop();/移除队首元素
查看队尾元素——back
back()
函数用于返回队列的最后一个元素的引用。这使得用户可以查看队列中最新添加的元素而不移除它。
函数造型
T& back();
const T& back() const;
返回值说明
- 非
const
版本返回队尾元素的引用,允许修改该元素。 const
版本返回队尾元素的常量引用,不允许修改该元素。
基本用法:
std::queue<int> q;// 使用 push 添加元素
q.push(10);// 访问队尾元素
std::cout << "队尾元素: " << q.back() << std::endl; // 输出: 队尾元素: 30
查看队首元素——front
front()
函数用于返回队列的第一个元素的引用。这使得用户可以查看队列中最早添加的元素而不移除它。
函数造型:
T& front();
const T& front() const;
基本用法:
std::queue<int> q;// 使用 push 添加元素
q.push(10);// 访问队首元素
std::cout << "队首元素: " << q.front() << std::endl; // 输出: 队首元素: 10
队列的其他函数
我们上面介绍的函数,都是队列常用的函数,建议大家实践一下,并记住
以下是一些不常用的函数,看一下,知道有即可,这里不再一 一赘述
栈——stack
栈(Stack)是一种遵循后进先出(Last In First Out,简称 LIFO, Last In First Out)原则的线性数据结构。
它只允许在末尾添加元素,也只允许在末尾删除元素
这样,就达成了栈的后进后出的原则
栈的构造
要使用,得先创造
方法一:使用默认构造
stack<T> s;
朴实无华,创建一个空的stack对象
方法二:使用初始化列表构造
stack<T> s = { elem1, elem2, ..., elemN };
创建一个包含指定元素的
stack
对象。
入栈——push函数
push
函数用于在栈的顶部(尾部)插入一个新元素。
函数造型:
void push(const T& value);
参数说明:
const T& value
:要插入栈顶的元素的常量引用。
基本用法:
std::stack<int> s;// 使用 push 添加元素
s.push(10);
出栈——pop函数
pop()
函数用于移除栈顶元素,也就是尾部的元素
查看栈顶元素——top函数
top()
函数用于返回栈顶(尾部)元素的引用。
这使得用户可以查看栈中最新添加的元素而不移除它。
函数造型:
void pop();
基本用法:
s.push(10);
s.push(20);
s.push(30);// 移除栈顶元素
s.pop();
注意:
pop()
函数不返回被移除的元素。如果需要访问被移除的元素,应先使用top()
获取该元素,然后再调用pop()
移除它。
栈的其他函数
我们上面介绍的函数,都是栈常用的函数,建议大家实践一下,并记住
以下是一些不常用的函数,看一下,知道有即可,这里不再一 一赘述
适配器
我们发现,queue和stack并不同于我们前面介绍的STL容器,它们的接口很少,也很简单
实际上,它们并不是像vector、list的纯正的STL容器,而是 C++ 标准模板库(STL)中的一个容器适配器
什么是容器适配器?
容器适配器(Container Adapters)是C++标准模板库(STL)中的一种工具,它们提供了一种方式,使得不同的容器类型可以通过统一的接口进行访问和操作。
容器适配器本质上是对底层容器的封装,提供特定的接口以满足某种特定的需求,同时隐藏了底层容器的具体实现细节。
我们的 queue 和 stack ,在我们眼里就是不同的容器
一个遵循先入先出的原则,一个遵守先入后出的原则
但我们统统使用统一的接口对二者进行访问和操作
它们的底层可以一样,也可以不一样
因为他们的底层是不固定的,是可以更改的
它们的底层是一个容器,这个容器是随意的,只要这些容器本身自带尾插、尾删、头删即可
即可以是vector,也可以是list,这也是容器适配的体现
适配其他容器,让别的容器充当自己的底层,来实现自己的接口!
以queue来举例
//使用默认的底层容器创建queue
std::queue<int> defaultQueue;// 使用 std::deque 作为底层容器显式创建 queue
std::queue<int, std::deque<int>> dequeQueue;// 使用 std::vector 作为底层容器创建 queue
std::queue<int, std::vector<int>> vectorQueue;
我们可以显示传递容器类型,也可以不传递,使用容器适配器默认的容器
容器适配器的出现,为我们提供了一种代码复用的可能,掌握容器适配器的思想,能够节省大量书写代码的时间,并让你的代码更高级简单!
结语
理解和掌握queue
、stack
及其相关适配器的使用,不仅能够提升我们的编程效率,还能帮助我们在面对复杂问题时,选择最合适的数据结构来优化解决方案。无论是在系统设计、算法实现,还是在日常的编程实践中,容器适配器都扮演着不可或缺的角色。
希望本文的介绍和示例能够帮助你更好地理解queue
、stack
及其适配器的应用。在实际开发中,灵活运用这些工具,将使你的代码更加简洁、高效和易于维护。如果你对容器适配器有更多的兴趣或疑问,欢迎继续深入学习C++ STL的更多内容,探索更多的可能性与技巧。