深入探讨【C++容器适配器】：现代编程中的【Stack与Queue】的实现

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    std::cout << "Stack top: " << s.top() << std::endl; // 输出3
    s.pop();
    std::cout << "Stack top after pop: " << s.top() << std::endl; // 输出2
    
    return 0;
}

首先我们压入了三个元素1, 2, 3，栈顶元素是3。然后我们弹出了栈顶元素，栈顶变成了2。

小李的理解：
就像把三个盘子按顺序叠起来（1在最底下，3在最上面）。当我们移走最上面的盘子时，下面的盘子就成了新的顶部。

1.3 Stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

示例代码：

#include <vector>
#include <iostream>

namespace bite {
    template<class T>
    class stack {
    public:
        stack() {}
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_back(); }
        T& top() { return _c.back(); }
        const T& top() const { return _c.back(); }
        size_t size() const { return _c.size(); }
        bool empty() const { return _c.empty(); }
    private:
        std::vector<T> _c;
    };
}

int main() {
    bite::stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    std::cout << "Custom stack top: " << s.top() << std::endl; // 输出3
    s.pop();
    std::cout << "Custom stack top after pop: " << s.top() << std::endl; // 输出2
    
    return 0;
}

这表明我们的自定义stack实现与标准库中的行为一致。

小李的理解：
我们自己实现了一个简单的栈，用vector来存储元素。每次添加元素时，将它们推到vector的尾部；每次移除元素时，从vector的尾部移除。这和我们平时用的栈行为完全一样。

二、Queue（队列）

2.1 Queue的介绍

queue（队列）是一种容器适配器，专门用于先进先出（FIFO, First In First Out）的操作环境中。队列的元素插入操作在容器的一端进行，即队尾，而提取操作在容器的另一端进行，即队头。

队列的底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。这些容器类应支持以下操作：

empty(): 检测队列是否为空

size(): 返回队列中有效元素的个数

front(): 返回队头元素的引用

back(): 返回队尾元素的引用

push_back(): 在队列尾部插入元素

pop_front(): 在队列头部删除元素

标准容器deque和list满足这些要求。默认情况下，如果没有为queue指定特定的底层容器，则使用deque。

小李的理解：
队列就像排队买票，最早来的人最先买到票（先进先出）。在C++中，队列的底层可以用多种容器实现，但一般默认用deque，因为它支持高效的头尾操作。

2.2 Queue的使用

queue的常用操作包括：

queue(): 构造空的队列

empty(): 检测队列是否为空

size(): 返回队列中有效元素的个数

front(): 返回队头元素的引用

back(): 返回队尾元素的引用

push(val): 在队尾将元素val入队列

pop(): 将队头元素出队列

示例代码：

#include <queue>
#include <iostream>

int main() {
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    std::cout << "Queue front: " << q.front() << std::endl; // 输出1
    q.pop();
    std::cout << "Queue front after pop: " << q.front() << std::endl; // 输出2
    
    return 0;
}

首先我们压入了三个元素1, 2, 3，队头元素是1。然后我们弹出了队头元素，队头变成了2。

小李的理解：
就像排队买票，第一个人买了票离开，第二个人就成了最前面的人。

2.3 Queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实现queue。

示例代码：

#include <list>
#include <iostream>

namespace bite {
    template<class T>
    class queue {
    public:
        queue() {}
        void push(const T& x) { _c.push_back(x); }
        void pop() { _c.pop_front(); }
        T& back() { return _c.back(); }
        const T& back() const { return _c.back(); }
        T& front() { return _c.front(); }
        const T& front() const { return _c.front(); }
        size_t size() const { return _c.size(); }
        bool empty() const { return _c.empty(); }
    private:
        std::list<T> _c;
    };
}

int main() {
    bite::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    std::cout << "Custom queue front: " << q.front() << std::endl; // 输出1
    q.pop();
    std::cout << "Custom queue front after pop: " << q.front() << std::endl; // 输出2
    
    return 0;
}

这表明我们的自定义queue实现与标准库中的行为一致。

小李的理解：
我们自己实现了一个简单的队列，用list来存储元素。每次添加元素时，将它们推到list的尾部；每次移除元素时，从list的头部移除。这和我们平时用的队列行为完全一样。

三、容器适配器

3.1 什么是适配器

适配器是一种设计模式，该模式是将一个类的接口转换成客户希望的另外一个接口。在STL中，stack和queue就是通过适配器模式将deque、vector等容器类的接口转换成特定的LIFO或FIFO操作。

3.2 为什么选择deque作为stack和queue的底层默认容器

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque。主要原因如下：

stack和queue不需要遍历（因此stack和queue没有迭代器），只需要在固定的一端或者两端进行操作。

在stack中元素增长时，deque比vector的效率高（扩容时不需要搬移大量数据）；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美地避开了其缺陷，使其成为stack和queue的理想底层容器。

总结

C++中的stack和queue通过容器适配器实现，分别用于LIFO和FIFO操作。stack和queue的底层容器默认使用deque，但也可以根据需求选择其他标准容器。理解并灵活运用这些数据结构，对于高效编写算法和处理复杂数据具有重要意义。

原文地址:https://blog.csdn.net/2303_77720864/article/details/140378056 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1812072482149109760.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部