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

大耳朵土土垚

发布于 2024-06-04 08:33:57

1250

发布于 2024-06-04 08:33:57

文章被收录于专栏：c/c++

💞💞 前言

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

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<class T, class Con = deque<T>>

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

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

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

✨stack实现代码

#pragma once
using namespace std;
#include<iostream>
#include<deque>
#include<vector>

namespace tutu_stack
{
    template<class T, class Con = deque<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:

        Con _c;

    };
};

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

✨stack测试代码

  //测试代码
    void test_stack()
    {
        stack<int,vector<int>> s;
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);

        while (!s.empty())
        {
            cout << s.top() << " ";
            s.pop();
        }
    }

注意测试代码要包含在自己的命名空间中哦，我们这里显示的将容器给了vector来存储数据，记得要包含vector的头文件#include<vector>

3.queue模拟实现

queue的实现与vector非常类似

queue函数	作用
push	队尾入队列
pop	队头出队列
front	获取队头元素
const front	const对象使用
back	获取队尾元素
const back	const对象使用
size	获取队列元素个数
empty	判断队列是否为空
swap	交换两个队列

与stack类似，它也使用了类模板 template<class T, class Container = std::deque<T>>并给了缺省值，使用deque（双端队列），同样其构造函数也不需要写，直接调用自定义类型的默认构造即可，队列是使用标准库里的容器来存储数据的，所以不需要手动实现拷贝

✨queue实现代码

using namespace std;
#include<iostream>
#include<deque>
#include<vector>
#include<list>

namespace tutu_queue
{
        template<class T, class Container = std::deque<T>>
        class queue
        {
        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<T, Container>& q)
            {
                _c.swap(q._c);
            }
        private:
            Container _c;
        };

✨queue测试代码

//测试代码
//使用list容器
    void test_queue2()
    {
        queue<int, list<int>> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        while (!q.empty())
        {
            cout << q.front() << " ";
            q.pop();
        }

    }
}