【C++】STL：栈和队列模拟实现

前言

hello hello~ ，这里是大耳朵土土垚~ ，欢迎大家点赞关注收藏

个人主页：大耳朵土土垚的博客

所属专栏：C++入门至进阶

这里将会不定期更新有关C++的内容，希望大家多多点赞关注收藏

目录

• 前言
• 1.stack和queue简介
• 2.stack模拟实现
• • ✨stack实现代码
  • ✨stack测试代码
  • 3.queue模拟实现
  • • ✨queue实现代码
    • ✨queue测试代码
    • 4.结语

      1.stack和queue简介

      C++中的stack（栈）和queue（队列）是两种常见的数据结构，用于存储和管理数据。

      栈是一种先进后出（LIFO）的数据结构，类似于我们平时堆叠的一摞书，只能在顶部进行操作。在C++中，可以使用std::stack模板类来创建栈。栈的主要操作包括压入（push）元素到栈顶、弹出（pop）栈顶元素以及获取栈顶元素等。

      队列是一种先进先出（FIFO）的数据结构，类似于排队等候的人群，新元素插入队尾，最早插入的元素在队头。在C++中，可以使用std::queue模板类来创建队列。队列的主要操作包括插入（push）元素到队尾、删除（pop）队头元素以及获取队头元素等。

      如下图所示：

      stack和queue都有自己的特点和适用场景。栈常用于实现递归算法、表达式求值和括号匹配等问题，而队列常用于实现广度优先搜索（BFS）算法、任务调度和缓冲区管理等问题。

      在C++中，stack和queue都是基于deque（双端队列）实现的，默认使用deque容器作为底层数据结构。此外，C++还提供了其他数据结构，如priority_queue（优先队列）和deque（双端队列），可以根据具体需求选择合适的数据结构来解决问题。

      2.stack模拟实现

      stack函数	作用
      push	尾插（栈顶入栈）
      pop	尾删（栈顶出栈）
      top	获取栈顶元素(也就是尾部元素)
      const top	给const对象使用
      size	栈中元素个数
      empty	判断栈是否为空

      stack模拟实现我们就可以使用之前学习过的vector或者list容器来实现，可以创建一个类模板，除了数据的类型可以改变，其使用的容器也可以改变，代码如下：

      template

      这样我们只需要传入数据类型以及使用的容器类型就可以确定stack是使用什么容器来实现存储和管理数据了，默认传入的是deque容器(给的是缺省值)

      deque（双端队列）是C++标准库中的一种容器，它可以在两端进行插入和删除操作。deque的全称是double-ended queue，它融合了向量（vector）和双向链表（doubly linked list）的特性。

      使用deque记得包含头文件#include

      ✨stack实现代码

      #pragma onceusing namespace std;#include#include#includenamespace tutu_stack{    template    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:        Con _c;    };};

      stack的构造，因为是使用STL标准库里的容器来实现，所以我们只需要调用标准库里给的构造函数即可，因为类的默认构造会自动调用自定义类型的默认构造，所以这里的默认构造可以不写，栈是使用标准库里的容器来存储数据的，所以不需要手动实现拷贝

      ✨stack测试代码

        //测试代码    void test_stack()    {        stack s;        s.push(1);        s.push(2);        s.push(3);        s.push(4);        while (!s.empty())        {            cout         template        public:            //队尾入队列            void push(const T& x)            {                _c.push_back(x);            }            //队头出队列            void pop()            {                _c.pop_front();            }            //获取队头元素            T& front()            {                return _c.front();            }            const T& front() const            {                return _c.front();            }            //获取队尾元素            T& back()            {                return _c.back();            }            const T& back() const            {                return _c.back();            }            //获取队列中有效元素个数            size_t size() const            {                return _c.size();            }            //判断队列是否为空            bool empty() const            {                return _c.empty();            }            //交换两个队列中的数据            void swap(queue                _c.swap(q._c);            }        private:            Container _c;        };            queue            cout