C++系列-Stackqueue
🌈个人主页：羽晨同学
💫个人格言:“成为自己未来的主人~”
Stack
在之前的例子中，我们用C语言实现过stack，大家有兴趣的可以翻一下我之前的文章。
大概意思如下：
class stack
{
public:
//.......
private:
int* _a;
int _top;
int _capacity;
};而在C++中，相较于C语言而言，我们多了一个新的概念，叫做容器的适配器
什么是适配器
适配器是一种设计模式，这种模式将一个类的接口转换成另外一个类的接口。
而在STL库中，不管是stack，还是queue，其中都用到了适配器的概念。
在STL库中，stack和queue默认使用的是deque
在了解deque之前，我们先实现一下用vector来充当容器，先体会一下适配器对于代码的作用。
用vector实现stack
//stack.h
#pragma once
#include<vector>
#include<list>
namespace bit
{
//class stack
//{
//public:
// //.......
//private:
// int* _a;
// int _top;
// int _capacity;
//};
template<class T,class Container=vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}//Test.cpp
#include<stack>
#include<queue>
#include"stack.h"
void test_stack()
{
bit::stack<int>a;
a.push(1);
a.push(2);
a.push(3);
a.push(4);
while (!a.empty())
{
cout << a.top() << " ";
a.pop();
}
cout << endl;
}
int main()
{
test_stack();
return 0;
}其实可以很明显的看到，适配器对代码的优化功能是极其强大的
deque
deque(双端队列)：是一种双开口的“连续”空间的数据结构。双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度是O（1），与vector相比较，头插效率高，不需要搬移元素，与list相比，空间利用率比较高。
deque并不是真正的连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器上面。
deque的缺陷：
与vector相比，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率比vector是必定高的。
与list相比，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷，不适合遍历，因为当遍历的时候，deque的迭代器需要频繁的去检测是否移动到了某个小空间的边界，导致效率低下，而在序列场景中，需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用场景并不多，而目前能看到的一个应用场景，STL用其作为stack和queue的底层数据结构。
而因为stack和queue是不用遍历，你看deque简直是为他们量身定做的。
stack和queue的模拟实现
//queue.h
#pragma once
#include<vector>
#include<list>
#include<deque>
namespace bit
{
template<class T,class Container=deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
// 这样就可以支持vector了，但是效率就很低了
//_con.erase(_con.begin());
}
const T& back()
{
return _con.back();
}
const T& front()
{
return _con.front();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
_con.size();
}
private:
Container _con;
};
}
//stack.h
#pragma once
#include<vector>
#include<list>
#include<deque>
namespace bit
{
/*template<class T>
class stack
{
private:
T* _a;
int _top;
int _capacity;
};*/
// 可维护性
// 设计模式
// 适配器模式 -- 封装转换
// 迭代器模式 -- 封装统一访问方式（数据结构访问都可以用）
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_back();
}
const T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
_con.size();
}
private:
Container _con;
};
}//Priority_Queue.h
#pragma once
#include<vector>
namespace bit
{
template<class T>
class myless
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class mygreater
{
public:
bool operator(const T& x, const T& y)
{
return x > y;
}
};
template<class T,class Constainer=vector<T>,class Comapre=myless<T>>
class priority_queue
{
public:
priority_queue() = default;
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--)
{
adjust_down(i);
}
}
void adjust_up(int child)
{
Comapre comfunc;
int parent = (child - 1) / 2;
while (child > 0)
{
if (comfunc(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void adjust_down(int parent)
{
Comapre comfunc;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1]))
{
++child;
}
if (comfunc[_con[parent], _con[child])
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Constainer _con;
};
}
好了，本次的文章就到这里，我们下次再见
