目录
- 1.容器适配器
- 2. stack模拟实现
- 2.1 准备工作
- 2.2 栈的接口实现
- 3.queue模拟实现
- 3.1 准备工作
- 3.2 队列的接口实现
- 3.3 按需实例化
- 4.deque
- 4.1 STL标准库中stack和queue的底层结构
- 4.2 deque的简单介绍
- 4.2.1 vector和list各自的优缺点
- 4.2.2 deque的优缺点
- 4.2.3 选deque做栈和队列的底层默认容器的原因
- 5. STL标准库中对于stack和queue的模拟实现
- 5.1 stack
- 5.2 queue
1.容器适配器
适配器是一种设计模式 ( 设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结) ， 该种模式是将一个类的接口 转换 成客户希望的另外一个接口 。
比如说我们日常生活中用的充电器，就是一种电源适配器，本质就是对电流电压 转换成我们需要的大小。
2. stack模拟实现
stack满足只能在一端插入和删除就行，我们的底层用vector的话可以满足这个条件，底层用list同样也可以满足这个条件。
既然如此，我们就不需要原生实现栈，直接用vector或者list封装转换一下不就好了。
如果是用vector实现栈，就是数组栈，用list实现栈，就是链式栈。
2.1 准备工作
我们把栈的所有实现都放在stack.h里，在test.cpp里测试。
在stack.h里，包含会用到的头文件，用命名空间namespace与库里面的stack分隔开。
#pragma once
#include <IOStream>
#include <list>
#include <vector>
using namespace std;
namespace lyj
{
}
在namespace里用模板。
namespace lyj
{
template<class T, class Container>
class stack
{
private:
Container _con;
};
}
第一个模板参数T是栈要存的数据类型，第二个模板参数Container是底层实现的类型，用Container适配转换出stack，传vector就封装vector实现，传list就封装list实现。
2.2 栈的接口实现
构造函数我们不用写，因为_con肯定是自定义结构，所以会调用自己的构造函数。
我们把尾当作栈顶。
namespace lyj
{
template<class T, class Container>
class stack
{
public:
void push(const T& x) //插入
{
_con.push_back(x);
}
void pop() //删除
{
_con.pop_back();
}
const T& top() const //获取栈顶元素
{
return _con.back();
}
size_t size() const //获取有效个数
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}
就非常方便简洁。
在testpython.cpp中使用一下我们写的这个stack。记得包含头文件#include "stack"
#include "stack.h"
void test1()
{
lyj::stack<int, vector<int>> st;//注意参数
st.push(1);
st.push(2);
st.push(3);
}
int main()
{
test1();
return 0;
}
上面显示就是底层是vector的栈，数组栈，然后我们插入了一些数据。
我们再演示一下底层是list的栈，链式栈，只需要把第二个参数换成list<int>就行。
void test2()
{
lyj::stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
}
此时，栈的底层发生了巨大的变化，我们可以把数据存在vector实现的栈里面，也可以存在list实现的栈里面。
我们也可以给第二个参数Container给缺省值。
template<class T, class Container = vector<T>>
3.queue模拟实现
queue要满足在一端插入，在另一端删除，我们的底层用list的话可以满足这个条件，但是此时vector就不满足这个条件了。那我们先用list封装转换一下。
3.1 准备工作
我们把队列的所有实现都放在queue.h里，在原来的test.cpp里测试。
在queue.h里用命名空间namespace与库里面的queue分隔开，这个命名空间名字和栈取一样的。
namespace lyj
{
template<class T, class Container = list<T>>
class queue
{
public:
private:
Container _con;
};
}
第一个模板参数T是栈要存的数据类型，第二个模板参数Container是底层实现的类型，这里Container缺省值给list<T>。
3.2 队列的接口实现
构造函数我们还是不用写，因为_con肯定是自定义结构，所以会调用自己的构造函数。
queue的代码和stack大差不差，只是把pop部分变成_con里的头删。
template<class T, class Container = list<T>>
class queue
{
public:
void push(const T& x) //队尾插入
{
_con.push_back(x);
}
void pop() //队头删除
{
_con.pop_front();
}
const T& top() const //获取队尾元素
{
return _con.back();
}
const T& front() const //获取队头元素
{
return _con.front();
}
size_t size() const //获取有效个数
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
在test.cpp中使用一下我们写的这个queue。记得包含头文件#include "squeue"
void test3()
{
lyj::queue<int, list<int>> q;
q.push(1);
q.push(2);
q.push(3);
}
看着没啥问题。
但是我们给Container传vector类型时，这个测试代码居然也可以。
void test3(){lyj::queue<int, vector<int>> q;q.push(1);q.push(2);q.push(3);}vector按理来说不能实现queue，在实现queue的pop部分，vector也没有pop_front（头删）这个接口。代码为什么没报错？
这里就要补充一个知识，按需实例化。
3.3 按需实例化
我们前面的测试代码并没有调用pop这个接口，当我们调用pop这个接口时，就会立马报错。
void test3()
{
lyj::queue<int, vector<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.pop(); //调用pop
}
这是因为，类在实例化的时候，不会实例化所有的成员函数，我们用哪些函数，就实例化哪些。
前面没报错，因为我们根本没有调用pop这个成员函数，可以理解为没有触发到这个错误。
编译器对模板检查的时候epkGdNuz，只会检查一个大概，明显的语法错误能检查出来，但是不会检查细节，比如说我们在这里调错了函数，用到这个接口时，才会报错。
所以，在类模板实例化时，只会实例化用到的函数，这就是按需实例化。
4.deque
4.1 STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为 容器适配器，这是因为stack和queue只是 对其他容器的接口进行了包装，STL中stack和queue默认 使用deque。
4.2 deque的简单介绍
文档介绍：deque - C++ Reference
我们看d编程客栈eque的成员函数，会发现deque有点像vector和list的结合。
vector支持[]，但是vector不直接支持头删尾删。
list支持各种位置插入删除，但是不支持[]。
既然说到这里了，我们也顺便说一下vector和list各自的优缺点
4.2.1 vector和list各自的优缺点
vector：
优点：1.尾插尾删的效率还不错，并且支持高效的下标随机访问。
2.物理空间连续，所以高速缓存利用率高。
缺点：1.空间需要扩容，扩容会带来效率问题和空间的浪费。
2.头部和中间部分的插入删除操作效率低。
lis编程客栈t：
优点：1.按需申请释放空间，不需要扩容。
2.可以在任意位置插入删除。
缺点：不支持下标随机访问。
4.2.2 deque的优缺点
deque的具体底层原理在这里就不详细说明了，有兴趣的可以去查阅资料。我们直接来说一下deque的优缺点。
deque：
优点：
1.可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)。
2.与vector比较，头插效率高，不需要搬移元素。
3.与list比较，空间利用率比较高。
缺点：
不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看 到的一个应用就是，STL用其作为stack和queue的底层数据结构。
4.2.3 选deque做栈和队列的底www.devze.com层默认容器的原因
1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在 stack 中元素增长时， deque 比 vector 的效率高 ( 扩容时不需要搬移大量数据 ) ； queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。
结合了 deque 的优点，而完美的避开了其缺陷。
5. STL标准库中对于stack和queue的模拟实现
使用deque时要包含头文件#include <deque>
5.1 stack
代码和原来一样，只是缺省参数换成deque<T>。
#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
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() const //获取栈顶元素
{
return _con.back();
}
size_t size() const //获取有效个数
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}
在test.cpp里测试一下。
void test4()
{
lyj::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
5.2 queue
代码和原来一样，也是缺省参数换成deque<T>。
#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;
namespace lyj
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x) //队尾插入
{
_con.push_back(x);
}
void pop() //队头删除
{
_con.pop_front();
}
const T& top() const //获取队尾元素
{
return _con.back();
}
const T& front() const //获取队头元素
{
return _con.front();
}
size_t size() const //获取有效个数
{
return _con.size();
}
bool empty() const //判空
{
return _con.empty();
}
private:
Container _con;
};
}
在test.cpp里测试一下。
void test5()
{
lyj::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
以上就是C++使用适配器模式模拟实现栈和队列的详细内容，更多关于C++实现栈和队列的资料请关注编程客栈(www.devze.com)其它相关文章！
加载中,请稍侯......
精彩评论