【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)
阅读导航
- 前言
- stack
- 1. stack概念
- 2. stack特点
- 3. stack使用
- queue
- 1. queue概念
- 2. queue特点
- 3. queue使用
- 容器适配器
- 1. 什么是适配器
- 2. STL标准库中stack和queue的底层结构
- 3. STL标准库中对于stack和queue的模拟实现
- ⭕stack的模拟实现
- ⭕stack的模拟实现
- 总结
- 温馨提示
前言
文章绑定了VS平台下std::stack和std::queue的源码，大家可以下载了解一下😍
前面我们讲了C语言的基础知识，也了解了一些数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— stack & queue（STL）。下面话不多说坐稳扶好咱们要开车了😍
stack
1. stack概念
stack 的文档介绍
在C++中std::stack是一个模板类，它是基于容器的适配器，用于实现堆栈数据结构。堆栈是一种后进先出（LIFO）的数据结构，类似于现实生活中的一叠盘子。std::stack类位于<stack>头文件中，并且是C++标准库的一部分。它提供了一组成员函数和操作符，用于对堆栈进行操作。
2. stack特点
-
后进先出（LIFO）：
std::stack是一种后进先出的数据结构，这意味着最后压入堆栈的元素将首先被弹出。 -
基于容器的适配器：
std::stack是基于容器的适配器，它使用底层容器来存储元素。默认情况下，std::deque被用作底层容器，但你也可以选择其他容器，如std::vector或std::list。 -
快速插入和删除：由于
std::stack是基于容器的适配器，它使用底层容器的插入和删除操作来实现元素的压入和弹出。这些操作的时间复杂度通常是常数时间，因此插入和删除操作非常高效。 -
无索引访问：
std::stack不支持通过索引访问元素。你只能访问堆栈顶部的元素，即使用top()函数。如果你需要访问其他位置的元素，你需要先将顶部的元素弹出。 -
无迭代器支持：
std::stack不支持迭代器，因此你不能使用迭代器遍历堆栈中的元素。如果你需要遍历堆栈中的元素，你需要先将它们弹出。 -
大小可变：
std::stack的大小是可变的，你可以根据需要动态地压入和弹出元素。
3. stack使用
- 包含头文件：首先，你需要包含
<stack>头文件，以便使用std::stack类。
#include <stack>
- 创建堆栈对象：使用
std::stack类创建一个堆栈对象。你需要指定堆栈中元素的类型。例如，如果你想创建一个存储整数的堆栈，你可以这样做：
std::stack<int> myStack;
- 压入元素：使用
push(element)函数将元素压入堆栈的顶部。你可以连续调用push()函数来压入多个元素。
myStack.push(10);
myStack.push(20);
myStack.push(30);
- 弹出元素：使用
pop()函数从堆栈的顶部移除元素。你可以使用循环或条件语句来连续弹出元素。
myStack.pop();
- 访问顶部元素：使用
top()函数可以访问堆栈顶部的元素，但不会将其从堆栈中移除。
int topElement = myStack.top();
- 检查堆栈是否为空：使用
empty()函数可以检查堆栈是否为空。如果堆栈为空，返回true；否则返回false。
if (myStack.empty()) {// 堆栈为空
} else {// 堆栈不为空
}
- 获取堆栈的大小：使用
size()函数可以获取堆栈中元素的数量。
int stackSize = myStack.size();
这些是使用std::stack的一般步骤。可以根据需要进行堆栈的操作，如压入元素、弹出元素、访问顶部元素等。
queue
1. queue概念
queue的文档介绍
在C++中，queue（队列）是一种数据结构，它遵循先进先出（FIFO）的原则。它类似于现实生活中的排队，新元素被添加到队列的末尾，而从队列中移除元素时，总是从队列的前端开始。
2. queue特点
-
先进先出（FIFO）：
std::queue是一种先进先出的数据结构，这意味着最先添加到队列的元素将首先被移除。 -
基于容器的适配器：
std::queue是基于容器的适配器，它使用底层容器来存储元素。 -
快速插入和删除：由于
std::queue是基于容器的适配器，它使用底层容器的插入和删除操作来实现元素的添加和移除。这些操作的时间复杂度通常是常数时间，因此插入和删除操作非常高效。 -
无索引访问：
std::queue不支持通过索引访问元素。你只能访问队列的前端和末尾元素，即使用front()和back()函数。 -
无迭代器支持：
std::queue不支持迭代器。如果你需要遍历队列中的元素，你需要先将它们移除。 -
大小可变：
std::queue的大小是可变的，你可以根据需要动态地添加和移除元素。
3. queue使用
- 包含头文件：首先，你需要包含
<queue>头文件，以便使用std::queue类。
#include <queue>
- 创建队列对象：使用
std::queue类创建一个队列对象。你需要指定队列中元素的类型。例如，如果你想创建一个存储整数的队列，你可以这样做：
std::queue<int> myQueue;
- 添加元素：使用
push(element)函数将元素添加到队列的末尾。你可以连续调用push()函数来添加多个元素。
myQueue.push(10);
myQueue.push(20);
myQueue.push(30);
- 移除元素：使用
pop()函数从队列的前端移除元素。你可以使用循环或条件语句来连续移除元素。
myQueue.pop();
- 访问前端和末尾元素：使用
front()函数可以访问队列的前端元素，使用back()函数可以访问队列的末尾元素，但不会将它们从队列中移除。
int frontElement = myQueue.front();
int backElement = myQueue.back();
- 检查队列是否为空：使用
empty()函数可以检查队列是否为空。如果队列为空，返回true；否则返回false。
if (myQueue.empty()) {// 队列为空
} else {// 队列不为空
}
- 获取队列的大小：使用
size()函数可以获取队列中元素的数量。
int queueSize = myQueue.size();
这些是使用std::queue的一般步骤。可以根据需要进行队列的操作，如添加元素、移除元素、访问前端和末尾元素等。
容器适配器
1. 什么是适配器
适配器是一种设计模式，它允许将一个类的接口转换为另一个类的接口，以便两个类可以协同工作。适配器模式通常用于解决两个不兼容的接口之间的问题。
在C++中，适配器也可以指代标准库中的容器适配器。容器适配器是一种特殊类型的容器，它使用底层容器来提供不同的接口和功能。适配器通过封装底层容器的操作，提供了一组新的操作和语义。
2. STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL标准库中std::stack和std::queue。它们分别基于底层容器（默认为std::deque）提供了堆栈和队列的功能。
3. STL标准库中对于stack和queue的模拟实现
⭕stack的模拟实现
template<class T, class Container = deque<T>>
class stack
{
public://入栈void push(const T& x){_con.push_back(x);}//出栈void pop(){_con.pop_back();}//返回栈顶数据T& top(){return _con.back();}//返回const类型栈顶数据const T& top() const{return _con.back();}//判断是否为空bool empty(){return _con.empty();}//返回栈的大小size_t size() const{return _con.size();}
private:Container _con;
};
⭕stack的模拟实现
template<class T, class Container = deque<T>>
class queue
{
public://进入队列void push(const T& x){_con.push_back(x);} //出队列void pop(){_con.pop_front();}//返回队尾数据T& back(){return _con.back();}//返回队头数据T& front(){return _con.front;}//返回const类型队尾数据const T& back() const{return _con.back();}//返回const类型队头数据const T& front() const{return _con.front;}//判断是否为空bool empty() const{return _con.empty();}//返回队列大小size_t size() const{return _con.size();}
private:Container _con;
};
总结
stack是一种后进先出（LIFO）的数据结构，它是一种容器适配器。它的特点是最后添加的元素将首先被移除。stack使用底层容器来存储元素，默认情况下使用std::deque作为底层容器。。queue是一种先进先出（FIFO）的数据结构，也是一种容器适配器。它使用底层容器来存储元素，默认情况下使用std::deque作为底层容器。适配器是一种设计模式，它允许将一个类的接口转换为另一个类的接口，以便两个类可以协同工作。在STL标准库中，stack和queue是基于其他容器实现的容器适配器。它们使用底层容器来存储元素，并提供了堆栈和队列的功能。
温馨提示
感谢您对博主文章的关注与支持！在阅读本篇文章的同时，我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章，可以点赞、评论和分享给您的同学，这将对我提供巨大的鼓励和支持。另外，我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！
再次感谢您的支持和关注。我们期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！
