目录
1. deque 容器介绍
????????C++最初设想是设计deque这个容器，使之能满足vector和list的功能之和，既能实现头尾的插入删除，又支持随机访问。
?可遗憾的是，虽然deque容器满足了这些优势，但也存在了一些设计缺陷：
1. operater[ ] 设计稍显复杂，大量使用，性能下降
2. 中间插入删除效率不高
3. 底层迭代器会很复杂
?????????因此，我们平时不这么使用这个容器，而是让它作为一个容器的缺省值，这样会好很多。下面栈和队列就用deque作为缺省容器。
?
2. stack 模拟实现
我们只需要内嵌其他容器，如vector，list，就能调用相关接口实现栈的功能
?
#include <deque>
namespace zj
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
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();
}
private:
//vector<T> _con;
Container _con;
};
}3. queue 模拟实现
与栈实现方法类似
#include <deque>
namespace zj
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T& back()
{
return _con.back();
}
T& front()
{
return _con.front();
}
const T& back() const
{
return _con.back();
}
const T& front() const
{
return _con.front();
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}4. priority_queue 模拟实现
????????优先级队列：即队列元素是有序的。这里实现方法与栈和队列相似，知识增加了C++库的仿函数less作为默认仿函数使之按大堆构造队列，若想建小堆，只需定义时给greater仿函数就行。
namespace zj
{
// 大堆
// Compare进行比较的仿函数 less->大堆
// Compare进行比较的仿函数 greater->小堆
template<class T, class Container = vector<T>, class Compare = std::less<T>>
class priority_queue
{
public:
priority_queue()
{}
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);
}
}
// logN
void adjust_up(size_t child)
{
Compare com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_con[child] > _con[parent])
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
// logN
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+1] > _con[child])
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//if (_con[child] > _con[parent])
//if (_con[parent] < _con[child])
if (com(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
const T& top()
{
return _con[0];
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
private:
Container _con;
};
}?
5. 测试代码
void test_stack()
{
//zj::stack<int, vector<int>> st;
//zj::stack<int, list<int>> st;
zj::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top() << endl;
st.pop();
}
}
void test_queue()
{
//zj::queue<int> q;
zj::queue<int, list<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << endl;
q.pop();
}
}
void test_priority_queue()
{
// 默认大的优先级高
zj::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
pq.push(5);
pq.push(0);
pq.push(1);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
int a[] = { 3, 2, 7, 6, 0, 4, 1, 9, 8, 5 };
//zj::priority_queue<int> heap(a, a+sizeof(a)/sizeof(int));
zj::priority_queue<int, vector<int>, greater<int>> heap(a, a + sizeof(a) / sizeof(int));
while (!heap.empty())
{
cout << heap.top() << " ";
heap.pop();
}
cout << endl;
}