app网站公司,请输入搜索关键词,网站建设需要的人才,网站转小程序一、stack栈
介绍
1.栈是一种特殊的线性表#xff0c;其元素遵循“后进先出”的原则#xff0c;即仅允许在在表的一端进行插入、删除操作#xff0c;这一模式被称为“后进先出”或LIFO#xff08;last in fisrt out#xff09;。 2.从底层实现来看#xff0c;stack是作…一、stack栈
介绍
1.栈是一种特殊的线性表其元素遵循“后进先出”的原则即仅允许在在表的一端进行插入、删除操作这一模式被称为“后进先出”或LIFOlast in fisrt out。 2.从底层实现来看stack是作为容器适配器被实现的什么是容器适配器我们来解释一下先。
先来看看我们身边的适配器。比方说你有注意到笔记本电脑的充电器吗
其实笔记本的充电器就是一个适配器。适配器要做的就是电压的转换。一般来说电脑的电池电压为14V左右而标准电压为220V要想给电脑充电这就需要对标准电压进行转换这就是适配器发挥的作用适配就是转换的意思。 适配器是一种设计模式该模式将一个类的接口转换为用户希望的另一个类的接口你可以认为适配器是一种转换器。 容器适配器能让程序员选择一种合适的底层数据结构。如stack之前我们写c语言时要用到栈的数据结构时是不是得还先模拟一个栈出来 那现在就不用这么麻烦了要用到栈和队列的地方直接用就行。 3.stack的底层容器可以是 任何容器类模板 or 其他特定的容器类。 这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 栈的底层实现简易版
可以看到栈的这些方法都是直接复用容器的方法体现了代码复用的思想。 这里的Container就是容器类它可以是vector、deque、list也可以省略不传。若省略那默认情况下是deque类。 使用
使用时要包stack头文件。 栈提供的方法有判空、取大小、取栈顶数据、压栈插入、出栈删除、交换 还有emplace安放。 这里对其中几点方法做个说明 1.构造函数 stackType, Container (数据类型容器类型 stackName; 数据类型一定要有容器类型可以是vector、deque、list。容器类型可省略默认是deque 2.在用top()前得判断下栈是否为空。只有不为空的时候才能调用top()不然会发生段错误。 这是因为在栈为空时stack 的top函数返回的是超尾-1而不是NULL。 3.和上面的top一样在调用pop函数前也要确保栈中至少有一个元素。 如果栈为空,调用pop会抛出EmptyStackException异常。 4.关于emplace意为“安放”就是说构造一个新的元素放入栈顶。emplace和push很像这里做一下区分。 push的话得是你先构造好对象然后push插进栈里emplace则是主动帮你调用构造函数构造出对象然后插进栈里。 示例
#includeiostream
#includestack
using namespace std;
int main() {stackint st;st.push(1);st.push(2);st.push(3);
while (!st.empty()) {cout st.top() ;st.pop();}cout endl;return 0;
} 从底层来看Container是一个模板你传数组or链表都可以。
来看看它是怎么适配的 二、queue队列
介绍
1.队列是一种特殊的线性表它只能在队尾插入数据队头出数据这一模式被称为“先进先出”或FIFOfirst in first out。 2.从底层实现来看queue也是作为容器适配器被实现的。
展示下queue简易版的底层实现 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。 该底层容器应至少支持以下操作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 标准容器类deque和list满足了这些要求。也就是说Container的位置可以传deque/ list过去也可以省略不传。当省略不传时那默认Container是deque。
为什么vector不满足呢因为vector没有头删。之前我们说过vector嫌头删效率低就没实现 使用
使用时要包头文件queue。 根据队列的特性实现的方法有判空、取大小、取队头、取队尾、队尾插入、队头删除、交换 和emplace安放。 几点说明 1.构造函数 queueType, Container (数据类型容器类型 queueName; 在初始化时必须要有数据类型容器可省略省略时默认为deque 类型。 所以构造一个queue可以是这样两种情况 queueint q;
queueint,listint q; 示例
#includeiostream
#includequeue
#includevector
using namespace std;
int main() {queueint q;q.push(1);q.push(2);q.push(3);
while (!q.empty()) {cout q.front() ;q.pop();}cout endl;return 0;
} 这张图说明了为什么deque是容器适配器 三、priority_queue优先级队列
介绍
1.优先级队列是一种特殊的队列结构它队列中的顺序并非插入的顺序而是按权重来排序。
它给每个元素加上了优先级每次出队的元素是队列中优先级最高的那个元素。 注不是越大的元素优先级就越高。 那优先级是如何评定的呢其实优先级队列在创建伊始它的优先级就已经定好了默认为降序。 那要如何排升序呢一会会在仿函数那说到。 2.优先级队列 底层被实现为容器适配器。
底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。 容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 pop_back()删除容器尾部元素 容器类vector和deque满足这些需求。如果容器类被省略不写那默认使用vector。 3.需要支持随机访问迭代器以便始终在内部保持堆结构。 priority_queue是用堆实现的因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。 注默认情况下priority_queue是大堆。 使用
使用时要包头文件queue。 注取顶端数据不是用front了是用top。 示例
#includeiostream
#includequeue
using namespace std;
int main() {priority_queueint q;q.push(4);q.push(12);q.push(3);
while (!q.empty()) {cout q.top() ;q.pop();}cout endl;return 0;
} 模拟实现
priority_queue具有队列的所有特性只是在此基础上又在内部加入了排序。它的底层原理是用堆实现的。
现在我们来模拟实现一下它的简易版这样能更好地理解它的底层原理。 ➡️复用代码
先把top、empty这种通过复用代码而实现的 函数给写了
#pragma once
#includeiostream
#includevector
using namespace std;
namespace jzy
{templateclass T,class Container vectorT //T是优先级队列中的 数据存储类型class priority_queue //Container是优先级队列中的数据结构{public:void push(const T val) {}void pop() {}T top() {return _con.front(); //直接复用容器的方法}bool empty() {return _con.empty();}size_t size() {return _con.size();}
private:T _val;Container _con;};
} ➡️push
push的实现大根堆先尾插再向上调整。
void AdjustUp(Container _con) {int child _con.size()-1;int parent (child - 1) / 2;
while (child 0){if (_con[child] _con[parent]) {swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}
}
void push(const T val) {_con.push_back(val);AdjustUp(_con);
} ➡️pop
pop的实现先把首尾交换让优先级最高的元素来到队尾以便尾删。再向下调整。
void AdjustDown(Container _con) {int parent 0;int child 2 * parent 1;
while (child _con.size()) {if (child 1 _con.size() _con[child 1] _con[child]) {child;}
if(_con[parent] _con[child]) {swap(_con[parent], _con[child]);parent child;child 2 * parent 1;}else {break;}}
}
void pop() {swap(_con.front(), _con[_con.size()-1]);_con.pop_back();AdjustDown(_con);
} ➡️如何排降序
目前排的是升序那要想排降序要怎么办呢
我倒是有个很朴素的办法每次插入元素向上调整时我把小的往上调不就行了吗
其实就只要改个符号
void AdjustUp(Container _con) {int child _con.size()-1;int parent (child - 1) / 2;
while (child 0){if (_con[child] _con[parent]) { //这里原本是现在给改成。越小越往上调swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}
}
但是这种方法并不好。我想排升序要把符号改成想排降序又要改回麻烦。
能不能用泛型解决呢 其实在STL库里就是用泛型解决的我们来学习一下。
STL里priority_queue有3个模板参数
template class T, class Container vectorT, class Compare lesstypename Container::value_type
第三个模板参数Compare定义了比较的方式。就是说我们通过定义Compare类来制定比较的规则。
不过要想理解参数Compare我们得先学习一个知识点仿函数。 仿函数
仿函数functor不是函数它描述的是对象只不过这个对象重载了operator()所以它使用起来像函数一样。 比方说你定义了一个A类用A实例化出对象a。此时a是一个普通的对象。
但当你在A里面重载了operator()即函数调用运算符那a就是仿函数就可以这样用
class A
{……int operator() (int x,int y){return xy;}
};
int mian(){A a;couta(1,2); //A实例化出的对象a就可以像函数一样使用a就叫仿函数return 0;
} 关于() 我一开始大为不解怎么圆括号()也能重载 没错()叫做”函数调用运算符“我们在调用函数时往往要传参此时就用到这个运算符。 所以说要想让对象成为仿函数只需要在它的类里面重载operator()。 用仿函数实现升降序
先实现两个类Greater、Less分别用于定义升序、降序这俩类实现为模板。
然后在priority_queue类中增加一个模板参数compare此参数用于接收 比较方式 的类型是升序还是降序。
compare默认为降序。当我们想要升序那就在传参时实例化出Greator类型的对象传过去即可。 //先实现Less和Greater两个类来定义比大小的规则
templateclass T
struct Less //less意为越来越小即降序
{bool operator() (const T x, const T y) {return x y;}
};
templateclass T
struct Greater //升序
{bool operator() (const T x, const T y) {return x y;}
};
templateclass T,class Container vectorT,class CompareLessT //增加模板参数默认为降序
class priority_queue
{Compare com;
public:void AdjustUp(Container _con) {int child _con.size()-1;int parent (child - 1) / 2;
while (child 0){if (com(_con[child],_con[parent])) {swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}}void AdjustDown(Container _con) {Compare com;int parent 0;int child 2 * parent 1;
while (child _con.size()) {if (child 1 _con.size() com(_con[child1],_con[child])) { child;}
if(com(_con[child], _con[parent])) {swap(_con[parent], _con[child]);parent child;child 2 * parent 1;}else {break;}}}void push(const T val) {_con.push_back(val);AdjustUp(_con);}void pop() {swap(_con.front(), _con[_con.size()-1]);_con.pop_back();AdjustDown(_con);}……
}; 注因为我们展开了STL库所以在命名Less/Greater时注意不要写成less/greater不然就和库里的重名了编译器就就晕了 不知道用哪个。 测试排升序
#includepriority_queue.h
using namespace jzy;
int main() {priority_queueint,vectorint,Greaterint pq;pq.push(7);pq.push(3);pq.push(8);pq.push(2);pq.push(12);pq.push(6);pq.push(3);
while (!pq.empty()) {cout pq.top() ;pq.pop();}return 0;
} 模拟实现的总代码
priority_queue.h
#pragma once
#includeiostream
#includevector
using namespace std;
namespace jzy
{templateclass Tstruct Less //less意为越来越小即降序{bool operator() (const T x, const T y) {return x y;}};
templateclass Tstruct Greater //升序{bool operator() (const T x, const T y) {return x y;}};
templateclass T,class Container vectorT,class CompareLessTclass priority_queue{Compare com;public:void AdjustUp(Container _con) {int child _con.size()-1;int parent (child - 1) / 2;
while (child 0){if (com(_con[child],_con[parent])) {swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}else {break;}}}void AdjustDown(Container _con) {Compare com;int parent 0;int child 2 * parent 1;
while (child _con.size()) {if (child 1 _con.size() com(_con[child1],_con[child])) { child;}
if(com(_con[child], _con[parent])) {swap(_con[parent], _con[child]);parent child;child 2 * parent 1;}else {break;}}}void push(const T val) {_con.push_back(val);AdjustUp(_con);}void pop() {swap(_con.front(), _con[_con.size()-1]);_con.pop_back();AdjustDown(_con);}T top() {return _con.front();}bool empty() {return _con.empty();}size_t size() {return _con.size();}
private:T _val;Container _con;};
} 四、deque双端队列
这个容器了解即可这个容器很少用
介绍
1.deque是“double-ended queue”的缩写。
虽然叫双端队列但它和队列没啥关系。deque是一种双开口的连续空间的数据结构。双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)。 deque支持随机访问也支持任意位置的插入、删除。似乎deque结合了vector和list的优点。
但deque真的是完美的吗
并不是deque随机访问的效率比较低。至于为什么那先让我们了解一下它的底层实现。 底层实现
和vector不同deque的底层并不是 真正意义上的连续的空间而是由一段段连续的小空间拼接而成的这些小空间不一定是连续的可能是位于内存的不同区域。如图 这里的map并不是STL里的map容器。而是数组数组的每个元素都是 指向另一块连续空间缓冲区buffer的 指针。我们插入的元素实际上是存进buffer里的。
可见deque对空间利用率很高几乎没什么空间的浪费。 ➡️如何进行扩容呢
当一个buffer存满了要尾插此时不会给当前buffer扩容因为它是大小固定的而是再开一个buffer空间尾插的内容存进新的buffer里。指针数组的下一个元素指向新的buffer。头插同理。下图可以帮助我们理解 可见头插、尾插不需要挪动数据效率自然高。
如果map满了那就再开一个更大的map如何把数据拷到新的map里。 ➡️关于deque的迭代器它的原理很复杂由四个指针组成。node指向中控区的指针数组first和node分别指向一段空间的开始和结束cur指向访问到的位置。如果访问的元素不在当前空间cur就等于下一个空间的first再继续访问。 ➡️当需要随机访问时deque得先完整复制到一个vector上如何vector排序后再复制deque。这就导致了deque的随机访问效率较vector更低。 关于deque的小结
优势1.相比vectordeque的头插、头删不需要挪动数据而是直接开新buffer插入效率很高
在扩容时也无需开新空间、拷数据而是直接开个新buffer效率高。 2.相比listdeque的底层是连续的存指针的map数组空间利用率比较高不需要存储额外字段。况且deque还支持随机访问虽然效率不高。 劣势1.不适合遍历。 因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下。 而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。 2.中间插入、删除的效率并不高。因为下标需要经过计算并且要挪动元素
