stack,queue的模拟实现,deque的模拟实现和小知识点的杂糅

1.stack的模拟实现

由于之前更新了一期链表的模拟实现,其实链表,stack,和queue的模拟实现的方式都差不多.

但这次,有一个新的玩法.

那就是不用自己写,直接去用别人现成的接口就行.

怎么得出这个结论 的?

首先我们可以看到,stack和queue大同小异,而且很多的操作和vector有着非常多的相似之处.

因此,我们可以尝试使用vector来实现stack和queue

namespace ay_s
{template <class T, class Container = std::vector<int>>class stack{public:void push(const T& x){_con.push_back(x);            }void pop(){assert(_con.empty()!= true);_con.pop_back();}T& top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}void Print(){for (auto e : _con){std::cout << e << ' ';}std::cout << std::endl;}void Check(){size_t top = _con.back();std::cout << top << std::endl;}private:Container _con;};

代码非常简短,就直接上代码了.

在这里我的思路就是定义一个模板类,然后第一个传的是参数类型,第二个传的则是类,什么类?

这边我给的是一个缺省值vector,也就是说,如果不传任何东西的话,那他这边的默认值则是vector,而里面的接口则是vector的底层;同样的,如果我们不想用vector,也是可以传一个list来用的,虽然这个时候我们在用的时候没有感受到任何区别,但是他们的底层已经发生了翻天覆地的变化.

2.queue的模拟实现

namespace ay_q
{template<class T ,class Container=std:: deque <int>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){// assert(_con.empty() != true)_con.pop_back();}void Print(){for (auto e : _con){std::cout << e << std::endl;}}size_t size(){return _con.size();}void Check(){size_t head = _con.front();std::cout << head << std::endl;}bool empty(){return _con.empty();}private:Container _con;};

而queue的模拟实现,我们调用的则是deque,除了这点跟上面的stack实现的方式不同以外,其它的都是差不多的,在函数里面调用deque的接口就行.

3.优先级队列priority_queue的详解

1.priority_queue的使用

接下来我们来详细谈谈这个priority_queue是一个什么东西.

首先,他被包含在一个叫做deque的文件里面,我们来看看他的接口有哪些.

接口就这几个,是不是发现他和stack特别相似?

int main()
{priority_queue<int, vector<int>> pq;pq.push(2);pq.push(1);pq.push(3);pq.push(4);while (!pq.empty()){cout << pq.top() << endl;pq.pop();}return 0;
}

上面这段代码运行过后的结果是,4  3  2  1,有没有发现他跟之前的某个数据结构很像?

输入一段乱序的数据,结果输出来的是有序数据,这个不就是堆嘛~

是的,他的底层就是一个大堆

那他默认是一个大堆,我们有没有办法改成一个小堆呢?

首先我们来看看他的所接收的模板参数

他接收的模板参数,第一个就是 类型 ,第二个是一个vector,说明他的缺省值就是vector , 然后第三个却是一个less,而这个less,则就是让这个是大堆的"罪魁祸首"

这点有点奇怪的是,这边传入的less , 却是一个大堆 , 跟之前的完全是相反的 , 那相应的 , 传入一个greater则是一个小堆~

而sort也是可以这样用的,比如

这样输出的也是一个大堆.

通过对比我们可以发现,为什么在上面的那个地方,最后一个传的是greater int<> ; 而在下面这里,我们传的却是一个greater <int>() 呢?

我们通过看文档得知,由于priority_queue是一个类模板,传的第三个参数是一个类型,而sort传的是一个函数参数,则传的是一个对象,传了一个什么对象呢?是一个匿名对象.

2.仿函数

仿函数故名思意,就是仿造一个函数.

对运算符()进行重载.也是第一次见到这个东西,记录一下.

3.priority_queue的模拟实现

接下来,就来模拟实现一下这个函数

前面讲了,这个东西的底层是一个大堆,也就是说,如果你不加以控制,他默认排序方式是大堆,

1.pop,empty,push,size,top的实现.

首先我们仍然是要用一个模板类来实现,而这些接口,是这个东西的最基本的接口,跟之前的stack也是差不多的.

		void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}

我们可以看到,其实这个东西的设置跟堆是大同小异的,当我们插入一个数据的时候,他会做一个向上调整,如果是小堆,则把小的调整上去;如果是大堆,则会把大堆调整上去.而当我们要弹出数据的时候,对于堆来说,弹出的一般是堆顶,那这个时候,就得让堆顶和堆尾来交换一下位置,然后再进行弹出.

2.adjust_up , adjust_down的模拟实现

这就是之前堆模拟实现的一个一模一样的东西了.

来回顾一下,向上调整算法,首先,向上调整是一个当有数据插入时的一种情况,当有数据插入时,我们此时堆已经是乱的了,需要向上调整,如果这个堆是一个小堆,那么就让这个子节点和父节点来比较,如果是小于父节点,则两个交换,然后子节点就找自己的父节点,父节点则找自己的父节点;而向下调整算法也是一样,这个则用于删除数据,一般来说,删掉的数据就是一个堆顶的数据,把他跟堆尾的数据交换一下,就可以直接删掉了,那此时,堆尾的数据就跑到了堆顶,那这个时候就需要用到向下调整了.来说一下这个的思路,首先,下面的两个子节点来比较大小,一般来说,都会假设左节点(child)大,如果他比右节点小,则child++,然后就可以用这个较大的子节点跟当前父节点来向下调整了.比较完了就子节点找自己的子节点,父节点找自己的子节点

child = parent*2 +1

parent = (child - 1) / 2

以上是计算子节点和父节点的公式

		void adjust_up(size_t child){Comp com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Comp com;int 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[child], _con[parent]);parent = child;child = child * 2 + 1;}else{break;}}}

3.任意的控制大堆和小堆

priority_queue这个函数的第三个参数是传一个greater来控制小堆,传一个less来控制大堆,在这里,我们可以通过使用仿函数来控制.

	template<class T>class less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class greater{public:bool operator() (const T& a, const T& b){return a > b;}};

是弄出来了,那具体该怎么控制呢?我们都知道,决定大小堆的,是在调整函数中的交换部分,这个地方的判断语句就是如果 a > b 或者 a < b ,那我们由此可以用less 和greater 来创造一个变量,然后用这个反函数来对其进行比较,如果需要用小堆,我们就传less进去,如果是大堆,我们就传一个greater进去

	template<class T, class Container = std::vector<T> , class Comp = greater<int>>class priority_queue{public:void adjust_up(size_t child){Comp com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Comp com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 > _con.size() && _con[child + 1] > _con[child]){child++;}if (com(_con[child] , _con[parent])){std::swap(_con[child], _con[parent]);parent = parent * 2 + 1;child = child * 2 + 1;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}bool empty(){return _con.empty();}size_t size(){return _con.size();}const T& top(){return _con[0];}private:Container _con;};
}

这个也就是整体的代码.