1.stack
在C++STL（标准模板库）中，栈被实现为一个容器适配器，提供了简化的接口，开发人员能够很轻松的使用栈数据结构。
1.1 特性
基于容器C++STL中的std::stack是一个容器适配器，它不是一个独立的数据结构，而是构建在其他容器之上的。默认情况下，std::stack使用std::deque作为其底层容器，但是也可以选择使用std::vector、std::list等其他容器来作为底层支持。
std::stack<int, std::deque<int>> stack1; // 使用 std::deque 作为底层容器
std::stack<int, std::vector<int>> stack2; // 使用 std::vector 作为底层容器1.2 C++ 标准库中的基本用法
std::stack提供了常用的栈操作，包括：push(val)：将元素压入栈顶。pop()：弹出栈顶元素。top()：访问栈顶元素。empty()：检查栈是否为空。size()：返回栈的大小。具体用法如以下代码所示。
//stack--C++ 标准库中的基本用法
void test_stack()
{stack<int> stack;int sum(0);//1、push()--将元素压入栈中for (int i = 0; i < 10; ++i)stack.push(i);//2、size()--返回栈中元素的个数cout << stack.size() << endl;//3、emplace()--在栈顶部添加一个新元素，该元素位于其当前顶部元素的上方。stack.emplace(11);cout << stack.size() << endl;//4、empty()--判断栈是否为空//5、top()--返回栈顶元素的引用//6、pop()--将栈顶元素弹出while (!stack.empty()){//取栈顶的数据cout << stack.top() << " ";stack.pop();//栈顶元素出栈}cout << endl;cout << stack.size() << endl;
}1.3 性能
std::stack的性能通常取决于其底层容器的性能特征。默认情况下，使用std::deque作为底层容器。选择不同的底层容器可能会影响性能。
使用std::vector作为底层容器：具有快速的随机访问性能，但在插入和删除元素时可能效率较低。使用std::list作为底层容器：具有快速的插入和删除性能，但随机访问较慢。因此，在选择底层容器时，需要根据具体的操作需求和性能考虑来进行权衡。
1.4 工作原理
关于栈的理论基础，可以看文章栈和队列的实现。
1.5 栈的模拟实现
本文演示了使用C++标准库提供的容器（std::deque）来实现一个栈，并提供了基本的栈操作。注意：实际的std::stack实现更加复杂和健壮。
1.5.1 push 方法
push方法用于将一个新元素压入栈顶。它调用容器的push_back方法将元素添加到底层容器_con的末尾。
void push(const T& val)
{_con.push_back(val);
}1.5.2 pop方法
pop方法用于移除栈顶元素。在移除元素之前，它首先检查栈是否为空，如果不为空，则调用pop_back来移除末尾元素；如果为空，则抛出一个runtime_error异常。
void pop()
{if (!empty()){_con.pop_back();}else{throw std::runtime_error("Stack is empty.");}
}1.5.3 top 方法
top方法返回对栈顶元素的引用。如果栈不为空，它返回底层容器最后一个元素的引用；如果栈为空，则抛出runtime_error异常。
T& top()
{if (!empty()){return _con.back();}else{throw std::runtime_error("Stack is empty.");}
}1.5.4 empty 方法
empty方法用于检查栈是否为空。该函数返回一个布尔值，通过调用底层容器_con的empty方法得出。
bool empty ()
{return _con.empty();
}1.5.5 size 方法
size方法返回栈中元素的数量。它通过调用底层容器_con的size方法来实现。
size_t size()
{return _con.size();
}完成代码如下：
//新增一个容器的模板参数，T是数据的类型，
//Container是一个容器的类型(容器具体是什么类型，可以根据需要传入)。
template<class T,class Container=std::deque<T>>
class MyStack
{
public:void push(const T& val){_con.push_back(val);}void pop(){if (!empty()){_con.pop_back();}else{throw std::runtime_error("Stack is empty.");}}T& top(){if (!empty()){return _con.back();}else{throw std::runtime_error("Stack is empty.");}}size_t size(){return _con.size();}bool empty (){return _con.empty();}private:Container _con;
};2.queue
2.1 特性
std::queue是STL中的一个容器，它提供了队列（FIFIO，即先进先出）的功能。
先进先出（FIFO）：如同现实生活中的队列，std::queue中的元素被安排在一系列的顺序中，最先加入的元素会最先被移除。
封装：std::queue在底层容器的基础上提供了封装。默认情况下，std::queue使用std::deque作为其底层容器，但也可以配置为使用std::list或其他符合要求的容器。
简单的接口：std::queue提供了一组简单的接口来添加、移除元素以及访问队列的首尾元素。
2.2 性能
时间复杂度：入队和出队操作通常是常数时间复杂度（O(1)），这意味着操作的时间不会随着队列大小的增加而显著增加。
空间复杂度：由于std::queue使用底层容器来存储元素，其空间复杂度取决于所使用的底层容器。例如，使用std::dequeue时，空间复杂度通常是线性的（O(n)），其中n是队列中元素的数量。
2.3 C++ 标准库中的基本用法
//队列
//C++ 标准库中的基本用法
void test_queue()
{queue<int> myqueue;//1、push--在队尾将元素i入队列for (int i = 0; i < 10; ++i)myqueue.push(i);//2、size--返回队列元素的个数cout << myqueue.size() << endl;//3、emplace--在队列的末尾添加一个新元素，该元素在当前队列最后一个元素的后面myqueue.emplace(11);cout << myqueue.size() << endl;//4、empty()--判断队列是否为空//5、front()--返回队头元素的引用//6、back()--返回队尾元素的引用//6、pop()--将队头元素出队列while (!myqueue.empty()){//返回队头的数据cout << myqueue.front() << " ";myqueue.pop();}cout << endl;cout << myqueue.size() << endl;
}2.4 工作原理
关于队列的理论基础，可以看文章
栈和队列的实现。
2.5 队列的模拟实现
本文中实现的MyQueue类是一个泛型队列，使用模板参数T来指定队列元素的类型，而模板参数Container来指定底层容器的类型，它默认为std::deque<T>，但也可以被替换为其他类型如std::list或std::vector。这种设计提供了灵活性，允许用户根据需要选择不同的底层容器。
2.5.1 构造函数
这里并未显示定义构造函数，所以MyQueue依赖于Container（默认为std::deque<T>）的默认构造函数来初始化_con成员。
2.5.2 push方法
目的：在队列的末尾添加一个元素。
参数：接受一个常量引用const T& value，代表要添加到队列中的元素。
实现：调用容器_con的push_back成员函数，将元素添加到容器的末尾。
代码如下：
//1、将元素添加队尾
void push(const T& val)
{_con.push_back(val);
}2.5.3 pop方法
目的：移除队列开始的元素。
参数：无参数。
实现：首先检查队列是否为空，如果不为空，则调用容器_con的pop_front成员函数移除第一个元素。如果队列为空，抛出一个std::runtime_error异常。
//2、移除队头元素
void pop()
{if (!empty()){_con.pop_front();}else{throw std::runtime_error("Queue is empty.");}
}2.5.4 front方法
目的：访问队列开始的元素
参数：无参数。
实现：如果队列不为空，返回容器_con的第一个元素的引用。如果队列为空，抛出一个std::runtime_error异常。
//3、访问队头元素的引用
T& front()
{if (!empty()){return _con.front();}else{throw std::runtime_error("Queue is empty.");}
}2.5.5 back方法
目的：访问队列末尾的元素。
参数：无参数。
实现：如果队列不为空，返回容器_con的最后一个元素的引用。如果队列为空，抛出一个std::runtime_error异常。
//4、访问队尾元素的引用
T& back()
{if (!empty()){return _con.back();}else{throw std::runtime_error("Queue is empty.");}
}2.5.6 empty方法
目的：检查队列是否为空。
参数：无参数。
实现：返回一个布尔值，指示容器_con是否为空，这是通过调用_con的empty成员函数实现的。
//5、检查队列是否为空
bool empty()
{return _con.empty();
}2.5.7 size方法
目的：返回队列中的元素数量。
参数：无参数。
实现：返回容器_con中元素的数量，这是通过调用_con的size成员函数实现的。
//6、返回队列的大小
size_t size()
{return _con.size();
}栈和队列模拟实现的完整代码可参考：栈的模拟实现、队列的模拟实现。
