stack
stack的使用
下面是stack库中的接口函数,有了前面的基础,我们可以根据函数名得知函数的作用
函数 | 说明 |
---|---|
stack() | 构造空栈 |
empty() | 判断栈是否为空 |
size() | 返回栈中元素个数 |
top | 返回栈顶元素 |
push() | 将值从栈顶压入栈内 |
pop() | 在栈顶出栈 |
stack模拟实现
栈其实就是一种特殊的vector
,因此可以使用vector
模拟实现stack
比较容易:
#include <iostream>
#include <vector>
using namespace std;
namespace my_stack
{
template<class T>
class stack
{
public:
void push(const T& val)
{
_v.push_back(val);
}
void pop()
{
_v.pop_back();
}
T& top()
{
return _v.back();
}
bool empty()
{
return _v.empty();
}
size_t size()
{
return _v.size();
}
private:
vector<T> _v;
};
}
queue
queue的使用
函数 | 说明 |
---|---|
queue() | 构造空队列 |
empty() | 判断队列是否为空 |
size() | 返回队列中元素个数 |
front() | 返回队头元素的引用 |
back() | 返回队尾元素的引用 |
push() | 在队尾入队 |
pop() | 在队头出队 |
queue模拟实现
queue
的接口中存在头删,用vector
实现起来效率太低,所以可以使用list
实现
#include <iostream>
#include <list>
using namespace std;
namespace my_queue
{
template<class T>
class queue
{
public:
void push(const T& val)
{
_lt.push_back(val);
}
void pop()
{
_lt.pop_front();
}
T& front()
{
return _lt.front();
}
T& back()
{
return _lt.back();
}
bool empty()
{
return _lt.empty();
}
size_t size()
{
return _lt.size();
}
private:
list<T> _lt;
};
}
适配器
适配器是一种设计模式,该模式是将一个类的接口转换成客户希望的另一个接口
对已有的东西,进行适配转换
在C语言中,我们习惯用顺序表去实现栈,因为使用顺序表实现栈比较方便
但是也可以用链表去实现,我们如果想去用链表实现栈,还需要再写一套,会比较麻烦
在C++中,有了适配器,不用再实现两遍了
我们可以使用适配器进行实现,这样我们就可以做到数组栈和链表栈秒切换了
在用适配器实现后,平时使用时感觉不到差异,但是两者的底层逻辑完全不同
下面我们用适配器设计出stack
首先我们添加一个模板参数template<class T,class Container>
,Container
就是适配器
在实例化的时候,我们需要指定适配器是哪一种容器
接下来,把成员变量改为适配器
template<class T,class Container>
class stack
{
public:
private:
Container _con;
};
接下来,我们按照前面模拟实现的stack把所有_v
改为_con
就可以了
namespace my_stack
{
template<class T,class Container>
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
接下来我们看一下 用适配器实现的数组栈和链表栈
int main()
{
my_stack::stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
st.push(6);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}//输出 6 5 4 3 2 1
cout << endl;
my_stack::stack<int, list<int>> st1;
st1.push(1);
st1.push(2);
st1.push(3);
st1.push(4);
st1.push(5);
st1.push(6);
while (!st1.empty())
{
cout << st1.top() << " ";
st1.pop();
}
//输出 6 5 4 3 2 1
cout << endl;
}
下面我们也可以使用适配器实现queue
namespace my_queue
{
template<class T, class Container>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
这里的适配器类型只能是list
,不能是vector
因为vector
中不支持pop_front
头删,无法支持queue
的pop
虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配
器,这是因为stack和队列只是对其他容器的接口进行了包装
deque
我们看STL中,stack
和queue
的实现
可以发现它们的适配器默认为deque<T>
这个deque
是什么容器,我们下面来看一看
deque
叫双端队列(但不是队列),是一种双开口的“连续空间”的数据结构
deque可以在头尾两端进行插入和删除操作,时间复杂度为O(1),效率高,并且支持[]
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维
数组
deque中有一段中控数组(本质是指针数组),其中每一个元素指针都指向一个固定大小的缓冲区
插入元素先从存入中控数组中间位置指针指向的缓冲区,因为要保证头插和尾插都有空间
如果一个Buff
满了,就在其下一个指针指向的Buff
中存储数据
如果中控数组满了,扩容即可,对于指针类型的拷贝消耗少
deque
相比于vector
:
极大缓解了扩容的问题,同时解决了头删和头插带来的效率低的问题
但是deque的[]
随机访问相对于vector
的随机访问还是有差距的,因为要计算随机访问的位置在哪个Buff
的哪个位置上
假设要访问位置
i
上的元素
1.先看i
在不在第一个Buff
中,如果在就直接找到位置访问
2.如果不在第一个Buff
,i-=第一个Buff
的size()
在第i/buffsize
个Buff
里
在这个Buff
中i%buffsize
位置上
而vector中的[]就是直接解引用指针,效率高
deque
相比于list
:deque
支持随机访问
cpu高速访问效率搞
但是deque
中间位置元素的插入和删除效率没有list
高
所以deque的最大价值就在于它的头插,头删,尾插,尾删的效率高
这也正是stack
和queue
中适配器最需要的特点,所以deque
作为stack
和queue
的默认适配器最合适文章来源:https://www.toymoban.com/news/detail-687874.html
用deque为默认适配器实现stack
和queue
文章来源地址https://www.toymoban.com/news/detail-687874.html
#include <deque>
#include <stack>
#include <list>
#include <iostream>
using namespace std;
namespace my_queue
{
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
namespace my_stack
{
template<class T, class Container = deque<T>>
class stack
{
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
T& top()
{
return _con.back();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}
到了这里,关于STL stack,queue,deque以及适配器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!