stack和queue底层是如何实现的？
参考回答：
在STL中，std::stack和std::queue都是容器适配器，它们都封装了其他容器来实现各自特定的行为。具体而言：
std::stack通常使用一个双端队列（std::deque）或动态数组（std::vector）作为底层容器来实现“后进先出”（LIFO）的栈操作。栈操作只允许在容器的一端进行插入和删除元素，即“栈顶”。std::queue通常使用双端队列（std::deque）作为底层容器来实现“先进先出”（FIFO）的队列操作。队列操作允许在容器的一端进行插入（队尾）和在另一端进行删除（队头）。
详细讲解与拓展：
1. std::stack 的底层实现
std::stack适配器封装了一个底层容器来支持栈操作。默认情况下，std::stack使用std::deque作为底层容器，也可以通过模板参数指定其他容器类型，如std::vector。
栈的操作主要有两个：
– push：将元素插入栈顶。
– pop：从栈顶移除元素。
– top：访问栈顶元素。
底层实现：
– 在std::stack的实现中，所有操作（push、pop、top）都只会影响容器的一端（栈顶），因此可以通过封装std::deque或std::vector来实现。std::deque提供了高效的在两端插入和删除操作，而std::vector提供了高效的随机访问和在末尾插入操作。
示例代码：
#include <stack>
#include <vector>
void example() {
std::stack<int, std::vector<int>> stk; // 使用 vector 作为底层容器
stk.push(1); // 压入元素 1
stk.push(2); // 压入元素 2
stk.push(3); // 压入元素 3
std::cout << "栈顶元素: " << stk.top() << std::endl; // 输出 3
stk.pop(); // 弹出元素 3
std::cout << "栈顶元素: " << stk.top() << std::endl; // 输出 2
}
在这个例子中，std::stack使用std::vector作为底层容器，操作栈时通过push、pop和top来实现栈式的LIFO操作。
2. std::queue 的底层实现
std::queue适配器封装了一个底层容器，通常是std::deque，来实现队列操作。队列的操作主要有两个：
– push：将元素插入队尾。
– pop：从队头移除元素。
– front：访问队头元素。
– back：访问队尾元素。
底层实现：
– std::queue通常使用std::deque作为底层容器。std::deque是双端队列，能够在两端高效地进行插入和删除操作。因此，std::queue可以通过std::deque提供的接口，确保在队尾插入元素和在队头删除元素的高效操作。
示例代码：
#include <queue>
#include <deque>
void example() {
std::queue<int, std::deque<int>> q; // 使用 deque 作为底层容器
q.push(1); // 入队 1
q.push(2); // 入队 2
q.push(3); // 入队 3
std::cout << "队头元素: " << q.front() << std::endl; // 输出 1
q.pop(); // 出队 1
std::cout << "队头元素: " << q.front() << std::endl; // 输出 2
}
在这个例子中，std::queue使用std::deque作为底层容器，队列操作通过push、pop、front和back方法进行，确保“先进先出”的队列行为。
为什么选择 std::deque 作为底层容器？
std::deque是一个双端队列，能够在两端高效地插入和删除元素。这使得它非常适合用于实现std::stack和std::queue，因为：
– 对于std::stack，我们只需要在容器的末端（栈顶）插入和删除元素。
– 对于std::queue，我们需要在容器的一端（队尾）插入元素，另一端（队头）删除元素。
std::deque的优势是它在这两端提供了高效的操作（O(1)时间复杂度），使得它成为这两个容器适配器的理想选择。
总结：
std::stack通常使用std::deque或std::vector作为底层容器，提供栈式操作（后进先出 LIFO）。std::queue通常使用std::deque作为底层容器，提供队列操作（先进先出 FIFO）。
这些适配器容器通过封装底层容器，简化了栈和队列的实现，并隐藏了底层容器的细节，使得开发者能够更加专注于容器的行为而不是底层实现。