网站设计与网页设计的区别,宁波网络推广制作,九洲建设集团网站,wordpress博客主题制作视频教程目录
前言
数据结构
deque
vector和list的优缺点
push
pop
top
size
empty
完整代码 前言
stack类就是数据结构中的栈
C数据结构#xff1a;栈-CSDN博客
stack类所拥有的函数相比与string、vector和list类都少很多#xff0c;这是因为栈这个数据结构是后进先出的…目录
前言
数据结构
deque
vector和list的优缺点
push
pop
top
size
empty
完整代码 前言
stack类就是数据结构中的栈
C数据结构栈-CSDN博客
stack类所拥有的函数相比与string、vector和list类都少很多这是因为栈这个数据结构是后进先出的它必须被有所限制所以所能用的函数只需要那几个足矣
栈可以用顺序表来实现也可以用链表来实现我们只需要控制它先进先出的特性即可用什么容器实现取决于个人
因为我们前面实现了vector和list类所以再实现stack类就容易很多了只需要复用vector和list容器内的函数即可
数据结构
templateclass T, class Container std::dequeT
class stack
{
public:private:Container _con;
};
这里的模板有两个T是栈的类型Container表示的是所需要使用哪个容器来实现这个栈
我们需要用这个Container里面的成员函数来复用从而轻松的实现这个栈
这里的Container默认是deque
deque
deque双端队列也是STL中的一个容器它是vector和list的结合 vector和list的优缺点 vector优点 1. 随机访问效率高 2. 在内存中连续存储缓存命中率高 vector缺点 1. 插入和删除效率低 2. 空间分配不灵活利用率低 list优点 1. 插入和删除效率高 2. 空间利用率高 list缺点 1. 访问数据速度慢 2. 缓存利用率低空间不连续缓存命中率低 为什么说deque是vector和list的结合
下面是deque的数据结构图片 deque有n个buffer缓冲区个数取决于数据个数
这个缓冲区比list的空间大像是一个小型数组这个数组由中控器控制
而中控器可以通过一个数组来存储一个个的指针这些指针又指向一个个缓冲区所以它能够控制每一个缓冲区
iterator迭代器的cur、first和last来控制缓冲区的数据node则表示是哪一个缓冲区
deque总结
1. deque的头尾插入效率高
2. 下标的随机访问效率也还可以
3. 中间插入删除的效率很低O(N)
push
void push(const T x)
{_con.push_back(x);
}
栈的push就是插入到最后的位置所以只需要复用容器中的push_back函数即可 deque、vector和list都有这些函数所以这三个容器都可以用来实现stack类 pop
void pop()
{_con.pop_back();
}
栈的pop就是尾删所以只需要复用pop_back函数即可
top
const T top() const
{return _con.back();
}
栈的top就是取尾部数据返回back函数即可
size
size_t size() const
{return _con.size();
}
栈的size就是取得栈的数据个数返回容器的size函数即可
empty
bool empty() const
{return _con.empty();
}
栈的empty就是判断栈是否为空返回empty函数即可
只要上述的函数名哪个类中有并且功能相同就可以使用那个类来完成stack的实现
完整代码
#pragma once#includeiostream
#includedequenamespace lyw
{templateclass T, class Container std::dequeTclass 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;};
} 完
