基于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;
}