stack
stack是一种容器适配器，专门用在设计用于在LIFO（后进先出）中操作，其中容器仅从容器的一端插入和提取。
stack被实现为容器适配器，这些类使用特定的容器类的封装对象作为其底层容器，提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”即为栈顶弹出。
底层：
template <class T, class Container = deque<T> > class stack;
模板参数含义：
T：
元素的类型；别名为成员类型 stack::value_type;
Container：
存储元素的内部底层容器对象的类型，它的value_type应该是T。别名是成员函数 stack::container_type。
常见成员函数
void test_stack()
{
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout << "stack size:" << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
stack的模拟实现
namespace yumo
{
//容器适配器，定义一个容器，可以是list或dequeue
template<class T, class Container = std::vector<T>>
class stack
{
public:
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()
{
return _c.size();
}
bool empty()
{
return _c.empty();
}
private:
Container _c;
};
}
queue
queue（队列）是一种容器适配器，专门用在FIFO（先进先出）中操作，其中从容器一端插入，另一端提取元素。
队列作为容器适配器实现，这些类使用特定容器类的封装对象作为其基础容器，提供一组特定的成员函数来访问其元素。元素被推入特定容器的“后面”，并从其“前面”弹出。
底层：
template <class T, class Container = deque<T> > class queue;
模板参数：
T：
元素的类型。别名为成员类型队列: : value _ Type。
Container：
存储元素的内部基础容器对象的类型。其值 value_type 应为 T。别名为成员类型 queue::container _ type。
常见成员函数
void test_queue2()
{
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
int len = q.size();
cout << "队列size：" << q.size() << endl;
cout <<"队列back："<< q.back() << endl;
while (len--)
{
int ans = q.front();
cout << ans << " ";
q.pop();
}
}
测试结果：
queue模拟实现
namespace yumo
{
//容器适配器，定义一个容器，可以是list或dequeue
template<class T, class Container = std::list<T>>
class queue
{
public:
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()
{
return _c.size();
}
bool empty()
{
return _c.empty();
}
private:
Container _c;
};
}
priority_queue
优先队列是一种容器适配器，经过专门设计，根据一些严格的弱排序标准，它的第一个元素始终是它包含的元素中最大的元素。
这个上下文类似于堆，可以随时插入元素，并且只能检索最大堆元素（优先级队列顶部的元素）。
优先队列被实现为容器适配器，这些类使用特定容器类的封装对象作为其底层容器，提供一组特定的成员函数来访问其元素。 元素从特定容器的“后面”弹出，称为优先级队列的顶部。
底层：
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
模板参数：
T:
元素类型；
别名为成员类型，priority_quque::value_type。
Container:
存储元素的内部底层容器对象的类型。
它的value_type应该为T；
别名为成员类型 priority_queue::container_type。
Compare:
定义的一个仿函数，后面介绍。
仿函数
仿函数就是使一个类看起来像一个函数一样。其实就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。
仿函数是模板函数，可以根据不同的类型代表不同的状态
仿函数是模板函数，可以有不同的类型。
仿函数是模板函数，其速度比一般函数要慢。
仿函数在一定程度上使代码更通用，本质上简化了代码。
下面给出仿函数和普通函数的对比：
常见成员函数
void test_priorityQueue1()
{
//默认是大堆，大的优先级高
//less 是大堆 greater 是小堆
std::priority_queue<int, vector<int>, std::less<int>> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
cout << "size: " << pq.size() << endl;
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
测试结果：
改成小堆后对比：
priority_queue的实现
根据数据结构中知识，这里分析push和pop操作，并理解堆中如何操作。
这里的例子只是堆向上调整算法和向下调整算法做分析：
此部分代码看不清楚可以参考下文中代码。
分析push和pop操作：
namespace yumo
{
template<class T>
struct less
{
bool operator() (const T& left, const T& right)
{
return left < right;
}
};
template<class T>
struct greater
{
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
/*template<class T,class Container = vector<T>,class Compare = yumo::less<T>>*/
template<class T, class Container = vector<T>, class Compare = yumo::less<T>>
class priority_queue
{
public:
void AdjustUp(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[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T&x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void AdjustDown(int 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[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
//交换第一个和最后一个
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
T top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
总结
本接学习了stack、queue、priority_queue等知识，学会了模拟实现他们，以后从题目中融汇这些知识。