【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)

前言

文章绑定了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特点

1. 后进先出（LIFO）：std::stack是一种后进先出的数据结构，这意味着最后压入堆栈的元素将首先被弹出。

2. 基于容器的适配器：std::stack是基于容器的适配器，它使用底层容器来存储元素。默认情况下，std::deque被用作底层容器，但你也可以选择其他容器，如std::vector或std::list。

3. 快速插入和删除：由于std::stack是基于容器的适配器，它使用底层容器的插入和删除操作来实现元素的压入和弹出。这些操作的时间复杂度通常是常数时间，因此插入和删除操作非常高效。

4. 无索引访问：std::stack不支持通过索引访问元素。你只能访问堆栈顶部的元素，即使用top()函数。如果你需要访问其他位置的元素，你需要先将顶部的元素弹出。

5. 无迭代器支持：std::stack不支持迭代器，因此你不能使用迭代器遍历堆栈中的元素。如果你需要遍历堆栈中的元素，你需要先将它们弹出。

6. 大小可变：std::stack的大小是可变的，你可以根据需要动态地压入和弹出元素。

3. stack使用

1. 包含头文件：首先，你需要包含<stack>头文件，以便使用std::stack类。

#include <stack>

2. 创建堆栈对象：使用std::stack类创建一个堆栈对象。你需要指定堆栈中元素的类型。例如，如果你想创建一个存储整数的堆栈，你可以这样做：

std::stack<int> myStack;

3. 压入元素：使用push(element)函数将元素压入堆栈的顶部。你可以连续调用push()函数来压入多个元素。

myStack.push(10);
myStack.push(20);
myStack.push(30);

4. 弹出元素：使用pop()函数从堆栈的顶部移除元素。你可以使用循环或条件语句来连续弹出元素。

myStack.pop();

5. 访问顶部元素：使用top()函数可以访问堆栈顶部的元素，但不会将其从堆栈中移除。

int topElement = myStack.top();

6. 检查堆栈是否为空：使用empty()函数可以检查堆栈是否为空。如果堆栈为空，返回true；否则返回false。

if (myStack.empty()) {// 堆栈为空
} else {// 堆栈不为空
}

7. 获取堆栈的大小：使用size()函数可以获取堆栈中元素的数量。

int stackSize = myStack.size();

这些是使用std::stack的一般步骤。可以根据需要进行堆栈的操作，如压入元素、弹出元素、访问顶部元素等。

queue

1. queue概念

queue的文档介绍

在C++中，queue（队列）是一种数据结构，它遵循先进先出（FIFO）的原则。它类似于现实生活中的排队，新元素被添加到队列的末尾，而从队列中移除元素时，总是从队列的前端开始。

2. queue特点

1. 先进先出（FIFO）：std::queue是一种先进先出的数据结构，这意味着最先添加到队列的元素将首先被移除。

2. 基于容器的适配器：std::queue是基于容器的适配器，它使用底层容器来存储元素。

3. 快速插入和删除：由于std::queue是基于容器的适配器，它使用底层容器的插入和删除操作来实现元素的添加和移除。这些操作的时间复杂度通常是常数时间，因此插入和删除操作非常高效。

4. 无索引访问：std::queue不支持通过索引访问元素。你只能访问队列的前端和末尾元素，即使用front()和back()函数。

5. 无迭代器支持：std::queue不支持迭代器。如果你需要遍历队列中的元素，你需要先将它们移除。

6. 大小可变：std::queue的大小是可变的，你可以根据需要动态地添加和移除元素。

3. queue使用

1. 包含头文件：首先，你需要包含<queue>头文件，以便使用std::queue类。

#include <queue>

2. 创建队列对象：使用std::queue类创建一个队列对象。你需要指定队列中元素的类型。例如，如果你想创建一个存储整数的队列，你可以这样做：

std::queue<int> myQueue;

3. 添加元素：使用push(element)函数将元素添加到队列的末尾。你可以连续调用push()函数来添加多个元素。

myQueue.push(10);
myQueue.push(20);
myQueue.push(30);

4. 移除元素：使用pop()函数从队列的前端移除元素。你可以使用循环或条件语句来连续移除元素。

myQueue.pop();

5. 访问前端和末尾元素：使用front()函数可以访问队列的前端元素，使用back()函数可以访问队列的末尾元素，但不会将它们从队列中移除。

int frontElement = myQueue.front();
int backElement = myQueue.back();

6. 检查队列是否为空：使用empty()函数可以检查队列是否为空。如果队列为空，返回true；否则返回false。

if (myQueue.empty()) {// 队列为空
} else {// 队列不为空
}

7. 获取队列的大小：使用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++、算法和编程的奥秘。祝您生活愉快，排便顺畅！