网站开发简历项目经验,石家庄网站系统建设,深圳公司网站设,国外优秀展厅设计#x1f493;博主CSDN主页:杭电码农-NEO#x1f493; ⏩专栏分类:C从入门到精通⏪ #x1f69a;代码仓库:NEO的学习日记#x1f69a; #x1f339;关注我#x1faf5;带你学习C #x1f51d;#x1f51d; 栈和队列 1. 前言2. 栈和队列的接口函数熟悉3. … 博主CSDN主页:杭电码农-NEO ⏩专栏分类:C从入门到精通⏪ 代码仓库:NEO的学习日记 关注我带你学习C 栈和队列 1. 前言2. 栈和队列的接口函数熟悉3. 适配器介绍4. 栈和队列的模拟实现5. deque的简单介绍6. 优先级队列深度剖析7. 优先级队列的模拟实现8. 总结以及拓展 1. 前言
和C语言学习期间的学习顺序一样 顺序表,链表过了就是栈和队列 但是栈和队列非常特殊,它的内部结构 并不是靠自己实现的,而是一种适配器模式
本章重点: 本篇文章着重讲解适配器原理 和栈,队列的接口函数熟悉以及模拟实现 适配器里有一个特殊容器:deque 最后讲解优先级队列相关知识和实现 2. 栈和队列的接口函数熟悉
栈的接口函数熟悉: 由于栈结构只能支持栈顶插入,栈顶pop 所以它的接口很少,这里就不多介绍了! 队列的接口函数熟悉: 队列只比栈多了一个接口:back 队列的front相当于栈的top 在了解了接口函数后,可以尝试做几个题巩固
最小栈栈的压入,弹出序列逆波兰表达式求值用两个栈实现队列 3. 适配器介绍
先看栈和队列的类模板: 我们发现第二个模板参数是:Container 并且它还有缺省值为 dequeT
这里就直接引出一个概念: 适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)该种模式是将一个类的接口转换成客户希望的另外一个接口。 一个比较经典的例子就是插头的适配器: 那么在数据结构栈中,这种适配器是什么呢? 很显然,在C语言阶段实现栈时,我们 使用的底层是顺序表来实现,也就是 把顺序表做了一层封装和限制,让它 的功能变得和栈一样,C这里也是一样! 我们在实现栈时不用再去写一个顺序表 而是直接调用库中的vector! 4. 栈和队列的模拟实现
栈的模拟实现要复用其他数据结构 所以在定义模板时要定义两个!
templateclass T, class Container dequeT
class Stack
{//......
private:Container _con;
}我们和库中的缺省值保持一致,使用deque 这个容器我们后面会有所解释! 这样使用栈非常的方便!因为此时的栈 就像富二代一样,不用写构造和析构函数 因为默认生成的构造或析构会去调用 内嵌类型的构造或析构帮助我们完成任务! 在此之后,只需要实现一些接口函数即可!
void push(const T val)
{_con.push_back(val);
}void pop()
{_con.pop_back();
}T top()//可读可写
{return _con.back();
}const T top() const
{return _con.back();
}bool empty() const
{return _con.empty();
}size_t size() const
{return _con.size();
}注:函数中的push_back或back等 函数接口是调用适配器中的!如vector中的 栈的结构实现完成,队列就交给你们了! 5. deque的简单介绍
deque也是一个STL库中的容器 先来看看它的介绍: deque又被称为双端队列是一种双开口的连续空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素,与list比较,空间利用率比较高 接下来看看它的接口函数: deque既有头插头删也有尾插尾删 这是意料之中,它也支持方括号[] 其实对于deque的了解到这里就差不多了 下面的内容属于拓展了解,有兴趣的可以看看
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 deque扩容是直接另外开辟一份空间 再让中控数组指向新开辟的空间 再将原先空间的内容拷贝至新空间
注意它有一个中控数组的概念! 6. 优先级队列深度剖析
优先级队列的英文是: priority_queue 它也是一个容量适配器,文档的大致翻译: 优先级队列默认是大堆! 并且它的底层适配器默认是vector 优先级队列默认有三个类模板,然而第三个 模板就是决定此优先级队列是大堆还是小堆 它叫仿函数,我们先不管它,下一篇文章回讲解 我们需要了解的是,默认的less是大堆 我们显示传参greater时是小堆! 优先级队列的接口函数熟悉: 注:如果你想使用小堆,就要将前两个 模板参数实例化后才能实例化第三个 当less变成greater时,就是小堆 7. 优先级队列的模拟实现
在学习仿函数之前,先实现无仿函数版本:
基本结构和框架:
templateclass T, class Container vectorT
class Priority_queue
{
public://成员函数
private:Container _con;//此容器可能是vector可能是deque
};由于优先级队列是富二代,所以 构造,析构和拷贝构造都可以忽略不写
优先级队列的插入和删除操作: 由于优先级队列实际上就是个堆 所以在插入,删除之后.都需要做一件事 那就是向上调整或向下调整!所以插入和 删除的关键其实就在于向上/下调整! 向上调整:
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}向下调整:
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (a[child1] a[child] child 1 n){child;}if (a[child] a[parent]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}这两个操作在学习堆时就已经实现过了,老朋友了
详情可看: 堆以及topk问题
优先级队列的插入和删除
void push(const T val)//堆的插入
{_con.push_back(val);adjust_up(_con.size() - 1);
}void pop()//堆的删除
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);
}插入和删除可谓是和堆的做法一模一样 其他的函数接口也是如此,这里就不多解读 我把优先级队列模拟实现的所有代码分享出来: 优先级队列模拟实现全部代码 8. 总结以及拓展
其实我们可以感受到,有了前面STL 容器的学习,现在学习栈和队列要轻松许多 不仅是模拟实现上可以复用以前的容器 连使用方法和函数接口都和之前一样 这就是CSTL的魅力所在!
拓展阅读: 对于deque我们还有很多未知的地方 比如它的扩容是怎样完成的?是否是缩容? deque是如何支持随机访问的?deque的缺陷?
有兴趣的老铁可以阅读下面这篇文章:
deque深度剖析 下期预告:模板进阶以及仿函数
