当前位置 博文首页 > stack和queue容器适配器_lhn的博客：C++
1、stack
stack使用
#include<iostream>
#include<stack>
using namespace std;
int main()
{
stack<int> s;
for(size_t i = 0; i < 10; ++i)
{
s.push(i);
}
size_t len = s.size();
while(len--)
{
cout<<s.top()<<endl;
s.pop();
}
return 0;
}
2、queue
queue使用
#include<iostream>
#include<queue>
using namespace std;
int main()
{
queue<int> q;
for(size_t i = 0; i < 10; ++i)
{
q.push(i);
}
size_t len = q.size();
while(len--)
{
cout<<q.front()<<endl;
//cout<<q.back()<<endl;
q.pop();
}
return 0;
}
3、priority_queue
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
注：默认情况下priority_queue是大堆
priority_queue使用
#include<iostream>
#include<queue>
using namespace std;
int main()
{
priority_queue<int> pq;
pq.push(23);
pq.push(98);
pq.push(56);
pq.push(14);
pq.push(33);
cout<<pq.top()<<endl;
pq.pop();
cout<<pq.top()<<endl;
return 0;
}
4、容器适配器
适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该中模式是将一个类的接口转换成客户希望的另外一个接口。
容器适配器stack、queue、priority_queue
虽然stack、queue、priority_queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为每个容器在底层都有自己的实现方式，而stack、queue、priority_queue只是在底层将其他容器进行了封装。
std::stack
template<class T, class Container = deque<T>>
class stack;
std::queue
template<class T, class Container = deque<T>>
class queue;
std::priority_queue
template<class T, class Container = vector<T>,
class Compare = less<typename Container::value_type>>
class priority_queue;
为什么选择deque作为stack和queue的底层默认容器？
stack是后进先出的特殊线性数据结构，只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；
queue是先进先出的特殊线性数据结构，只要具有push_back()和pop_front()操作的线性结构，都可以作为queue的底层容器，比如list。
但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：
5、模拟实现
#include<iostream>
#include<deque>
using namespace std;
namespace mystd
{
template<class T, class Con = deque<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;
};
}
int main()
{
mystd::stack<int> s;
for(size_t i = 0; i < 10; ++i)
{
s.push(i);
}
cout<<s.size()<<endl;
cout<<s.empty()<<endl;
cout<<s.top()<<endl;
s.pop();
s.pop();
cout<<s.size()<<endl;
cout<<s.empty()<<endl;
cout<<s.top()<<endl;
return 0;
}
#include<iostream>
#include<deque>
using namespace std;
namespace mystd
{
template<class T, class Con = deque<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;
};
}
int main()
{
mystd::queue<int> q;
for(size_t i = 0; i < 10; ++i)
{
q.push(i);
}
cout<<q.back()<<endl;
cout<<q.front()<<endl;
cout<<q.size()<<endl;
cout<<q.empty()<<endl;
q.pop();
q.pop();
cout<<q.back()<<endl;
cout<<q.front(
