STL中stack，queue,privority_queue,反向迭代器的模拟实现

stack的简要介绍

template <class T, class Container = deque > class stack;

Container = deque这个叫做适配器，是一种复用。

一、基本概念
栈是一种**后进先出（LIFO, Last In First Out）的线性数据结构，仅允许在同一端（栈顶）**进行插入和删除操作。其核心操作包括：

入栈（Push）：向栈顶添加元素
出栈（Pop）：移除栈顶元素
查看栈顶（Peek/Top）：获取但不移除栈顶元素
二、核心特性
操作受限只能访问栈顶元素
动态大小栈空间可动态扩展（链式栈）或固定大小（数组栈）
时间复杂度所有操作均为 O(1)（假设无扩容开销）
空间复杂度 O(n)，n 为元素数量

stack是不支持迭代器的，因为他是一中先进后出的结构。

stack接口

void push(const T& val)插入队尾的元素
void pop()删除队尾的元素
T& top()获取栈顶的元素
size_t size()const元素的个数
bool empty()判断是否位空

stack的实现

template<class T,class container=vector<T>>//空间适配器
class stack
{
public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top(){return _con.back();}size_t size()const{return _con.size();}bool empty(){return _con.empty();}
private:container _con;

queue的简要介绍

template <class T, class Container = deque > class queue;

也是一使用适配器来实现
一、基本概念
队列是一种先进先出（FIFO, First In First Out）的线性数据结构，操作限制在两端：
• 队尾（rear）：仅允许插入（入队/enqueue）
• 队首（front）：仅允许删除（出队/dequeue）

queue接口

void push(const T& val)在队头插入数据
void pop()删除队头的元素
size_t size()获取元素的个数
T& front()获取队头的数据
bool empty()判断队列是否为空

queue实现

void push(const T& val)
{_con.insert(_con.end(),val);
}
void pop()
{_con.erase(_con.begin());
}
size_t size()
{return _con.size();
}
T& front()
{return _con.front();
}
bool empty()
{return _con.empty();
}

privority_queue(优先级队列)的简要介绍

template <class T, class Container = vector, class Compare =
less > class priority_queue;

priority_queue是队列吗？答案不是的。
一、基本定义
优先级队列是一种特殊的队列数据结构，其中每个元素都关联一个优先级值。与普通队列不同，元素出队顺序不取决于入队时间，而是由其优先级决定。最高优先级的元素总是最先被移除。
二、核心特性

元素访问规则
只能访问优先级最高（或最低）的元素
无法直接访问中间优先级的元素
动态排序机制
◦ 插入新元素时自动调整内部排序
◦ 删除元素后自动维护优先级顺序
多形态支持
可配置为最大优先或最小优先模式
支持自定义优先级比较规则

privority_queue接口的介绍

void adjustdown(int parent)向下调整算法·
void adjustup(int child)向上调整算法
priority_queue(inputiterator first, inputiterator last)构造函数
void push(const T& val)插入元素
void pop()删除堆顶的元素
size_t size()获取元素的个数
bool empty()判断是否为空
T& top()获取堆顶的元素

privority_queue函数实现

构造函数的实现

在这里插入图片描述

首先准备给了一个模板，输出迭代器，然后只要这个first迭代器只要不等于last迭代器，我们就一直插入元素，最后我们在优先级队列里面就会得到一堆元素，然后我们要对这一整个元素进行排序调整。我们可以需要使用循环。

template <class inputiterator>
priority_queue(inputiterator first, inputiterator last)
{while (first != last){_con.push_back(*first);first++;}for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){adjustdown(i);}
}

向下调整算法的实现
我们默认实现的是大堆，当我们知道父亲的位置的时候，孩子的位置就是父亲的元素下标2+1；但是child有俩个，我们刚刚计算的child2+1是左孩子的位置，我们需要比较一下左右孩子的大小，因，所以我们当右孩子大的话，我们就++一下。接下来我们需要比较孩子跟父亲的大小，只要孩子比父亲大，我们就交换这俩个元素，然后将孩子的位置给父亲，在计算孩子的大小，因此我们可以知道这个一个循环。
在这里插入图片描述

void adjustdown(int parent)//默认是大堆
{compare com;int child = parent * 2 + 1;//左孩子while (child<_con.size()){if (child + 1 < _con.size() && com(_con[child] ,_con[child + 1])){child++;}else if (com(_con[parent],_con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

pop接口的实现
我们可以认为堆就是vector，在vector中是没有提供头删跟头插的方式的，为什么呢？效率太差了，而我们要删除一个堆顶的元素，应该怎么删呢？挪动数据吗？那样子效率太差了，我们可以先交换一下堆顶跟堆尾的数据，然后删除尾部的数据，那样子不就是O(1)时间复杂度吗！然后我们只需要将堆顶的元素与再次向下调整一下就行。
在这里插入图片描述

void pop()
{swap(_con[0], _con[_con.size() - 1]);//交换一下栈顶的元素跟最后一个元素的位置；_con.pop_back();adjustdown(0);
}

push接口的实现

实现思路：尾插一个数据，然后我们需要调整每次插入的时候，都要调整我们堆元素的位置，每次调整需要从最后面开始。

void push(const T& val)
{_con.push_back(val);//调整完开始调整堆;adjustup(_con.size() - 1);
}

向上调整算法的实现

向上调整算法实现稍微简单点，之前我们向下调整过了，当我们插入新的元素的时候，我们只需要跟我们的父亲比较一下大小，孩子大的话，就交换一下俩者的位置，然后将跟新孩子跟父亲的位置。
在这里插入图片描述

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

剩余的接口实现

size_t size()
{return _con.size();
}
bool empty()
{return _con.empty();
}
T& top()
{return _con.front();
}

仿函数的介绍

什么是仿函数呢？
我们可以来看一段代码

class Less
{
public:bool operator()(const T& x1, const T& x2){return x1 < x2;}
};

在这里插入图片描述
我们就可以像使用函数来使用，本质还是使用运算符重载来实现的。
这个时候我们就可以调整大队和小堆了，使用less默认是大堆,greater是小堆。

class Greater
{
public:bool operator()(const T& x1, const T& x2){return x1 > x2;}
};

反向迭代器的实现

反向迭代器也是一个类，也是一种适配器，适配的是iterator;

namespace wcd2
{template<class iterator, class Ref,class ptr >class Reverse_iterator{typedef Reverse_iterator< iterator,Ref,ptr > self;public:Reverse_iterator(iterator it):_rit(it){}Ref operator*(){iterator tmp = _rit;return *(--tmp);}ptr operator->(){return &(operator*());}self operator++(){--_rit;return *this;}self operator++(int){iterator tmp = _rit;--_rit;return tmp;}self operator--(){++_rit;return *this;}self operator--(int){iterator tmp = _rit;++_rit;return tmp;}bool operator!=(const self& s){return _rit != s._rit;}bool operator==(const self& s){return _rit == s._rit;}private:iterator _rit;};
}