函数说明 | 接口说明 |
---|---|
stack() | 构造空的栈 |
empty() | 检测stack是否为空 |
size() | 返回stack中元素的个数 |
top() | 返回栈顶元素的引用 |
push() | 将元素val压入stack中 |
pop() | 将stack中尾部的元素弹出 |
在开始之前,我们需要知道什么是设计模式:设计模式概念 目前有23种。
我们现在接触的模式有两种:适配器模式、迭代器模式
对于迭代器模式,使我们所熟知的,因为对于vector和list的模拟实现,都涉及到迭代器模式,迭代器模式将内部复杂的数据结构进行了封装,从而在上层使用中更为便捷,即不暴露底层细节,封装后提供统一的方式访问容器;而对于适配器模式:现实生活中,被称为适配器的有电源等待,因此适配器本质是已有的东西,封装转换出你想要的东西。
对于stack的模拟实现,下面将用适配器转换,vector、list
stack.h
#pragma once
#include<vector>
#include<list>
//stack的模拟实现
namespace cfy
{
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
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"Stack.h"
int main()
{
cfy::stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
return 0;
}
当然,也可以用list替换vector,同时里面的函数也要改成list类的。
函数声明 | 接口说明 |
---|---|
queue() | 构造空的队列 |
empty() | 检测队列是否为空,是返回true,否则返回false |
size() | 返回队列中有效元素的个数 |
front() | 返回队头元素的引用 |
back() | 返回队尾元素的引用 |
push() | 在队尾将元素val入队列 |
pop() | 将队头元素出队列 |
同stack,模拟实现也是采用适配器的方式,因为stack和queue都不存在迭代器。由于queue经常头删,用vector代价高,因此这里使用list的适配器。
queue.h
#pragma once
#include<vector>
#include<list>
//queue的模拟实现
namespace cfy
{
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& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"queue.h"
int main()
{
cfy::queue<int, list<int>> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
return 0;
}
当然,用vector也是可以的,同时需要将对应的函数改成vector类的。
我们查文档发现,虽然stack用了适配器模式,但是其适配器并不是vector,而是deque作为缺省值,这也正对应了stack介绍的第四条,如果不传指定的适配器,stack就采用deque
那么deque是什么呢?——双端队列
我们在C++上一篇list的结尾叙述了vector、list的优缺点:vector的头部中部插入效率低以及扩容消耗,list不支持随机访问,CPU高速缓存命中率低,而deque恰恰会与其互补。即deque双端队列兼具vector、list的优点,可以支持下标访问,头部尾部效率高。
deque支持头插尾插,头删尾删,下面就直接使用deque:
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<deque>
using namespace std;
int main()
{
deque<int> d;
d.push_back(1);//支持尾插
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_front(10);//支持头插
d.push_front(20);
for (size_t i = 0; i < d.size(); i++)//支持下标随机访问
{
cout << d[i] << " ";
}
cout << endl;
return 0;
}
deque并没有想象的那么好,否则vector和list也不会存在,deque的使用效率不高,因为效率不如指定场景的vector和list。这一点可以用排序测试。
对于deque的原理,在STL源码剖析的143页:STL源码剖析电子版