文章目录

一、stack1.1 stack的使用1.2 stack的模拟实现

二、queue2.1 queue的使用2.2 queue的模拟实现

三、优先级队列1.优先级队列的介绍2. priority_queue的使用的使用3.模拟实现优先级队列

四、 容器适配器1.STL标准库中stack和queue的底层结构2.deque（双端对列）了解2.1deque的概念2.2deque的缺陷2.3为什么选择deque作为stack和queue的底层默认容器

五、STL标准库中对于stack和queue的模拟实现stack的模拟实现queue的模拟实现

一、stack

栈的特点是先进后出，stack不提供迭代器。

1.1 stack的使用

1.2 stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

<code>#include<vector>

namespace fx

{ -- -->

template<class T>

class stack

{

public:

stack() { }

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

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

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

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

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

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

private:

std::vector<T> _c;

};

}

二、queue

队列的特点是先进先出，queue不提供迭代器

2.1 queue的使用

2.2 queue的模拟实现

queue的底层可以是list等支持尾插头删的线性容器，但并不支持vector，因为数组头插头删效率不行。

<code>#include <list>

namespace fx

{ -- -->

template<class T>

class queue

{

public:

queue() { }

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

void pop() { _c.pop_front();}

T& back() { return _c.back();}

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

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

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

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

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

private:

std::list<T> _c;

};

}

三、优先级队列

1.优先级队列的介绍

在有了前面容器使用的基础之下，我们对于优先级队列priority_queue的使用成本不是很大，值得注意的是头文件为 < queue>

普通的队列是先进先出，优先级队列默认是优先级高的先出

Container: 优先级队列默认使用vector作为其底层存储数据的容器，支持[]的使用，支持随机访问，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

Compare:注意：默认情况下priority_queue是大堆，仿函数为less。

2. priority_queue的使用的使用

3.模拟实现优先级队列

<code>#pragma once

namespace fx

{ -- -->

template <class T>

class less

{

public:

bool operator()(const T& x, const T& y) const

{

return x < y;

}

};

template <class T>

class greater

{

public:

bool operator()(const T& x, const T& y) const

{

return x > y;

}

};

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

class priority_queue

{

public:

priority_queue()

{ }

template <class InputIterator>

priority_queue(InputIterator first, InputIterator last)

:_con(first, last)

{

for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)

{

adjust_down(i);

}

}

void adjust_up(size_t child)

{

Compare com;

size_t parent = (child - 1) / 2;

while (child > 0)

{

//if ( _con[parent]<_con[child])

if (com(_con[parent], _con[child]))

{

swap(_con[child], _con[parent]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

void adjust_down(size_t parent)

{

Compare com;

size_t child = parent * 2 + 1;

while (child < _con.size())

{

//if (child + 1 < _con.size() && _con[child] < _con[child + 1])

if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))

{

child++;

}

//if (_con[parent]<_con[child])

if (com(_con[parent], _con[child]))

{

swap(_con[child], _con[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

void push(const T& x)

{

_con.push_back(x);

adjust_up(_con.size() - 1);

}

void pop()

{

swap(_con[0], _con[_con.size() - 1]);

_con.pop_back();

adjust_down(0);

}

const T& top() const

{

return _con[0];

}

bool empty() const

{

return _con.empty();

}

size_t size() const

{

return _con.size();

}

private:

Container _con;

};

}

仿函数和C语言的函数指针的作用有点类似，函数指针是传入目标函数的地址，通过函数回调来执行目标函数的功能。而仿函数是一个类，对于模板函数，根据传入函数的类对象调用类中的operator()来控制不同的结果;对于模板类，通过在类中构造仿函数对象，在需要功能“分叉”的地方调用仿函数类中的operator()来达到不同的效果。（白话：泛型中的仿函数影响逻辑，通过仿函数来控制一个“水龙头”出冷水还是出热水······）

还有一种情况：优先级队列存的是某个类的地址，但是需要比较指针指向值的优先级。那这个时候就不能用中的less和greater控制建堆，需要自己写仿函数。（仿函数也可以加上模板特化）

四、 容器适配器

1.STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为

容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认

使用deque，比如：

2.deque（双端对列）了解

2.1deque的概念

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端

进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与

list比较，空间利用率比较高.

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个

动态的二维数组，其底层结构如下图所示：

2.2deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其

是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实

际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看

到的一个应用就是，STL用其作为stack和queue的底层数据结构。

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

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性

结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据

结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如

list。

但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进

行操作。在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的

元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

五、STL标准库中对于stack和queue的模拟实现

stack的模拟实现

<code>#include<deque>

namespace fx

{ -- -->

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

//template<class T, class Con = vector<T>>

//template<class T, class Con = list<T>>

class stack

{

public:

stack() { }

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

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

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

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

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

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

private:

Con _c;

};

}

queue的模拟实现

include<deque>

#include <list>

namespace fx

{

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

//template<class T, class Con = list<T>>

class queue

{

public:

queue() { }

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

void pop() { _c.pop_front();}

T& back() { return _c.back();}

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

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

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

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

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

private:

Con _c;

};

}