基于STL的自定义栈与队列实现：灵活选择底层容器的模板设计
基于STL的自定义栈与队列实现：灵活选择底层容器的模板设计
前言：
在本文中，我们将分析一个模拟C++标准模板库（STL）栈的自定义实现以及模仿C++标准模板库（STL）队列的自定义实现。该stack类模板允许在底层容器的选择上具有灵活性、该queue类模板采用灵活的容器选择机制，默认使用std::deque作为底层容器，这与STL设计相似。接下来，我们将深入研究代码的结构、功能，以及使用模板和容器组合在C++中实现的优势。
代码
这是在Stack命名空间下的主要类定义：
namespace Stack
{
template<class T, class Container>
class stack
{
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_back(); }
const T& top() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
private:
Container _con;
};
}模板设计
该类是一个模板，接受两个参数： T：存储在栈中的元素类型。 Container：底层容器类型，用于管理栈元素的存储。 这种设计使我们能够自定义底层的存储容器，允许使用std::vector、std::list或std::deque作为底层数据结构。在标准库中，std::stack默认使用std::deque作为底层容器，因为它在两端插入和移除元素时的效率较高。
主要成员函数
让我们逐一了解主要的成员函数：
push(const T& x)：用于将一个元素x压入栈顶。此实现使用了push_back函数，因为无论使用哪种容器，我们都希望在容器末尾添加新元素。
pop()：用于移除栈顶元素。与push类似，此处使用pop_back，因为需要从容器的末尾移除元素。
top() const：返回栈顶元素的常量引用。这是只读访问，因为栈顶元素不能通过top()修改。
size() const：返回栈中的元素数量，直接调用容器的size()函数。
empty() const：用于检查栈是否为空，直接调用容器的empty()函数。
底层容器的选择
在这个实现中，底层容器的选择灵活。例如： std::vector：可以用于存储连续内存中的栈，但当栈中的元素较多时，可能会带来内存的重新分配开销。 std::list：是链式存储结构，不支持随机访问，但在频繁插入和删除操作时性能较优。 std::deque：是双端队列，既支持随机访问，又可以在两端进行高效的插入和删除操作，是STL中std::stack的默认容器。 小结 该stack模板类通过组合不同的容器类型实现了灵活的栈结构，符合STL设计原则。在实际使用中，根据需求选择合适的底层容器，可以进一步优化栈的性能。
这是在Queue命名空间下的queue类定义：
namespace Queue
{
template<class T, class Container = std::deque<T>>
class queue
{
public:
void push(const T& x) { _con.push_back(x); }
void pop() { _con.pop_front(); }
const T& front() const { return _con.front(); }
const T& back() const { return _con.back(); }
size_t size() const { return _con.size(); }
bool empty() const { return _con.empty(); }
private:
Container _con;
};
}模板设计
该类是一个模板，接受两个参数： T：存储在队列中的元素类型。 Container：底层容器类型，用于存储队列元素，默认使用std::deque。 这种设计允许我们在实现队列时选择不同的容器，如std::deque、std::vector或std::list。然而，std::deque是STL中默认的底层容器，因其支持在两端快速插入和删除元素，非常适合队列的FIFO（First In, First Out）特性。
主要成员函数解析 以下是queue类中的核心成员函数：
void push(const T& x) push函数将元素x添加到队列末尾。此函数调用_con.push_back(x)，无论底层容器是什么类型，都确保新元素添加到队列的“尾部”。
void pop() pop函数移除队列的第一个元素。它调用_con.pop_front()，遵循队列的FIFO特性，将队首元素出队。这种操作在std::deque和std::list中效率较高，而在std::vector中效率相对较低。
const T& front() const front函数返回队列首元素的常量引用。由于是常量引用，用户可以读取但不能修改队首元素。
const T& back() const back函数返回队列尾元素的常量引用。用户可以读取队列中的最后一个元素，但不能通过此方法修改它。
size_t size() const size函数返回队列中元素的数量，直接调用底层容器的size()函数。
bool empty() const empty函数检查队列是否为空，直接调用底层容器的empty()函数。
底层容器的选择
在该实现中，可以选择不同的容器作为底层数据结构，以下是常见的选择及其特点： std::deque：STL中std::queue的默认容器。支持两端快速插入和删除，非常适合队列的特性。 std::list：链表结构，允许在两端常数时间内插入和删除元素，适用于需要频繁插入和删除的场景。 std::vector：虽然可以作为底层容器，但由于在队首插入和删除元素效率较低，通常不推荐在队列中使用。
关于stack的示例代码
#include "stack.h"
#include <vector>
#include <list>
#include <iostream>
int main() {
// 使用 std::vector 作为底层容器的栈
bit::stack<int, std::vector<int>> vector_stack;
vector_stack.push(10);
vector_stack.push(20);
vector_stack.push(30);
vector_stack.pop(); // 移除栈顶元素
std::cout << "Top element in vector-based stack: " << vector_stack.top() << std::endl; // 输出栈顶元素
std::cout << "Stack size: " << vector_stack.size() << std::endl; // 输出栈的大小
// 使用 std::list 作为底层容器的栈
bit::stack<int, std::list<int>> list_stack;
list_stack.push(40);
list_stack.push(50);
list_stack.push(60);
list_stack.pop(); // 移除栈顶元素
std::cout << "Top element in list-based stack: " << list_stack.top() << std::endl; // 输出栈顶元素
std::cout << "Stack size: " << list_stack.size() << std::endl; // 输出栈的大小
return 0;
}关于queue的示例代码
#include "queue.h"
#include <deque>
#include <list>
#include <vector>
#include <iostream>
int main() {
bit::queue<int, std::deque<int>> deque_queue;
deque_queue.push(10);
deque_queue.push(20);
deque_queue.push(30);
deque_queue.pop();
std::cout << "Front element in deque-based queue: " << deque_queue.front() << std::endl;
bit::queue<int, std::list<int>> list_queue;
list_queue.push(40);
list_queue.push(50);
list_queue.push(60);
list_queue.pop();
std::cout << "Front element in list-based queue: " << list_queue.front() << std::endl;
return 0;
}腾讯云开发者
