c++之stack_queue与反向迭代器的实现

1. 简单介绍stack与queue的使用

1.1 stack的介绍与使用

stack的介绍

stack的使用

1. 简单介绍stack与queue的使用

1.1 stack的介绍与使用

stack的介绍

1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。< 这里我们在模拟实现会重点讲解>
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

对于栈的特性想必大家都不陌生，下图是它的特性图。

stack的使用

stack的使用很简单，最常用的就是下表的几个函数，无非压栈出栈，判空取尾。

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部的元素弹出

这里就不做示范了，非常简单。

1.2 queue的介绍与使用

queue的介绍

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

2.stack与queue的模拟实现

容器适配器

学习stack与queue的模拟实现就必然要与容器适配器打招呼，那么什么是容器适配器呢？

在stack的介绍中我们看到有这样一句话。

下图有两个不同的容器，把水分别倒进去，此时两边的水就有了圆柱与圆锥的形状，但本质还是水，把沙子倒进去也一样。我们要学习的容器适配器同理。

分别用vector与list实现stack，此时的vector与list就具有了栈后进先出的特性，我们要实现的各种功能也都是调用vector与list的接口。

分别用vector与list实现queue，此时的vector与list就具有了队列先进先出的特性，我们要实现的各种功能同样都是调用vector与list的接口。

在这里可以把stack与queue理解成不同特性的容器。将vector等容器填充进去，使他们具备容器的特性。

接下来我们来看看c++中的适配器是什么？

在C++中，适配器（adapter）通常指的是一种设计模式，用于将一个类的接口转换成另一个类的接口，以便两者能够协同工作而无需修改原始类的代码。适配器模式可以分为类适配器模式和对象适配器模式。

1. 类适配器模式：通过继承原始类和实现目标接口来实现适配器。
2. 对象适配器模式：通过包含原始类的实例并实现目标接口来实现适配器。

在STL（标准模板库）中，也有一些称为适配器的特定类，如：
std::stack：基于deque、list或vector实现的栈适配器。
std::queue：基于deque或list实现的队列适配器。
std::priority_queue：基于vector实现的优先队列适配器。

这些适配器类提供了一些特定的接口和功能，使得使用栈、队列或优先队列更加方便和高效。

2.1 stack的模拟实现

既然已经明白了stack是一个容器适配器，那么stack的模拟实现自然就是向其内填充 vector等容器。

这里要注意，因为实现stack可以使用vector，list，deque等容器，因此我们需要使用到模板。

在模板参数中，我们将容器参数缺省为deque。各种功能接口也都是调用其内容器的接口。

	template <class T, class container = deque<T>>
	class stack
	{
	public:
		stack(container con = container())
			:_con(con)
		{}

		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		T& top()
		{
			return _con.back();
		}

		const T& top()const
		{
			return _con.back();
		}

		size_t size()const
		{
			return _con.size();
		}

		bool empty()const
		{
			return _con.empty();
		}
	private:
		container _con;
	};

2.2 queue的模拟实现

queue的原理同stack一样，直接上代码。

    template<class T, class Con = deque<T>>

    class queue

    {

    public:

        queue(Con con=Con())
            :_con(con)
        {}

        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
        }
     
        T& back()
        {
            
        }

        const T& back()const
        {
            return _con.back();
        }

        T& front()
        {
            return _con.front();
        }

        const T& front()const
        {
            return _con.front();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:

        Con _con;

    };

2.3 priority_queue的模拟实现

priority_queue是什么呢？

优先级队列，顾名思义，优先级队列是会给队列中的数据排序的，那么是怎么做到的呢？

这里请想想堆，堆在插入数据时尾插，插入时按照向上调整算法维护堆；删除数据时删头，交换头尾，删除尾，再进行向下调整算法维护堆。和队列的特性非常符合，是完美的优先级队列底层结构。

template <class T>
class less
{
public:
    bool operator()(T x, T y)
    {
        return x < y;
    }
};
template <class T>
class greater
{
public:
    bool operator()(T x, T y)
    {
        return x > y;
    }
};
template <class T, class Container = vector<T>, class Compare = greater<T> >
class priority_queue

{

public:
    Compare com;
    priority_queue(Container con=Container())
        :_con(con)
    {}

    bool empty() const
    {
        return _con.empty();
    }

    size_t size() const
    {
        return _con.size();
    }

    const T& top() const
    {
        return _con[0];
    }

    void Addjust_Up(int child)
    {
        T parent = (child - 1) / 2;
        while (parent >= 0)
        {
            if (com(_con[child], _con[parent]))
            {
                std::swap(_con[parent], _con[child]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }

    }
    void push(const T& x)
    {
        _con.push_back(x);

        Addjust_Up(_con.size()-1);
    }

    void AddJust_Down(int parent)
    {
        size_t child = parent * 2 + 1;
        
        while (child < _con.size())
        {
            if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
            {
                ++child;
            }
            if (com(_con[child], _con[parent]))
            {
                std::swap(_con[parent], _con[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    void pop()//堆顶的删除，先交换堆顶与堆尾，然后删除堆尾，再向下调整
    {
        
            std::swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();

            AddJust_Down(0);
        
    }
private:

    Container _con;
};

priority_queue的模拟实现相较普通queue要复杂一些，因为我们要实现建堆与堆删除的向上调整与向下调整算法。同时堆有大堆小堆之分，但他们的代码只在某个位置有所不同，为了提高代码的复用率，我们使用了仿函数。

仿函数是什么？

在C++中，仿函数（functor）是一个类或结构体，它重载了函数调用运算符()，从而可以像函数一样被调用。仿函数可以用作函数对象，用于实现自定义的函数行为。

如下图就是仿函数的使用方法。

在优先级队列的向上（下）调整算法中我们使用到了它。

3. deque的介绍

在上文中，我们提到stack与deque的默认实现结构都是deque，那么他到底有怎样神奇的力量呢？

3.1 deque的原理

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

这里的map是一个指针数组，map内存放的指针各自指向一个存放数据的数组。我们将map内存放的数组叫做buffer。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示

对于一个数组buffer，first指向buffer的第一个元素，last指向最后一个元素的下一个，cur指当前元素，node则是指向buffer的，用来表明当前处于哪一个buffer。

那deque是如何借助其迭代器维护其假想连续的结构呢？

不同的编译器，对于buffer的处理不同，每一个map内存放的缓冲区buffer有可能是登场的，也可能是非等长的，这里我们只需要了解。

3.2 deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。

4. 反向迭代器

在之前的list与vector模拟实现中，我们实现了他们的正向迭代器，并未对反向迭代器做处理。

为什么在这里谈反向迭代器呢？是因为当我们实现了stack与queue后再学习反向迭代器会简单很多，反向迭代器的实现与stack有异曲同工之妙，让我们来看看吧！

下面的代码就是反向迭代器的模拟实现。复用传入的迭代器来实现我们需要的功能。

这里的rbegin与rend指向位置同begin，end位置是对称的。因此我们实现operator*时需要返回前一个的数值。

	template<class Iterator, class Ref, class Ptr>
	struct Reverse_iterator
	{
		typedef Reverse_iterator<Iterator, Ref, Ptr> self;
		Reverse_iterator(Iterator it)
		{
			_it(it);
		}

		Ref operator*()
		{
			Iterator tmp(_it);
			tmp--;
			return *tmp;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

		self& operator++()
		{
			return --_it;
		}

		self& operator++(int)
		{
			Iterator tmp(_it);
			--_it;
			return tmp;
		}

		self& operator--()
		{
			return ++_it;
		}

		self& operator--(int)
		{
			Iterator tmp(_it);
			++_it;
			return tmp;
		}

		bool operator==(const self& s)
		{
			return s._it == _it;
		}

		bool operator!=(const self& s)
		{
			return s._it != _it;
		}


		Iterator _it;


	};