深圳ui设计培训机构,站长查询seo是什么意思,wordpress中国风主题下载,荣耀手机商城官方网站登录入口前言
前面我们对string、vector、list做了介绍并对底层进行了实现#xff01;本期我们继续来介绍STL容器#xff0c;stack和queue#xff01;
本期内容介绍 stack 常用接口的介绍 queue 常用接口的介绍 什么是stack? 这里的栈和我们C语言实现的数据结构的那个栈功能是一样…前言
前面我们对string、vector、list做了介绍并对底层进行了实现本期我们继续来介绍STL容器stack和queue
本期内容介绍 stack 常用接口的介绍 queue 常用接口的介绍 什么是stack? 这里的栈和我们C语言实现的数据结构的那个栈功能是一样的栈是一种支持在一端进行插入和删除的顺序容器遵循 后进先出LIFO的原则库里面也说了它是一种容器适配器什么是容器适配器这里先不做介绍等下一期模拟实现的时候再来详细介绍本期只介绍如何使用 常用接口介绍
empty 判断栈是否为空 size 获取栈里面的元素个数 top 获取栈顶元素的引用 push 在栈顶插入一个元素 pop 删除栈顶元素 OK这就是栈的常用接口很简单我下面来演试一下
void stack_test1()
{stackint st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);bool emp st.empty();cout empty : emp endl;size_t sz st.size();cout size : sz endl;int top st.top();cout top : top endl;st.pop();top st.top();cout top : top endl;
} OK我们来做一道OJ来用一下stack吧
最小栈 这道题让你实现一个最小元素的栈每次可以用常量级别的时间复杂度获取当前栈中的最小元素 这里用一个栈肯定是不行的一个栈遍历的话不符合人家的常量级别的时间复杂度既然一个栈不可以那我们搞两个栈一个存当前栈的数据域一个存当前栈里面的的最小元素 如果普通栈为空或当前元素比普通栈的栈顶元素小得话插入到最小栈 OK我先画个图走一遍刚刚的思路 OK我们实现一下
class MinStack
{
public:MinStack() {}void push(int val) {_elem.push(val);if(_min.empty() || val _min.top())//普通栈为空或当前元素比普通栈顶元素小入最小栈_min.push(val);}void pop() {if(_min.top() _elem.top())//如果普通栈的栈顶元素和最小栈相同也要删最小栈的元素_min.pop();_elem.pop();}int top() {return _elem.top();//返回普通栈的栈顶元素}int getMin() {return _min.top();//获取最小栈的栈顶元素}private:stackint _elem;//普通栈stackint _min;//最小栈
}; OK栈就介绍到这里下面我们来看看队列
什么是queue? 和栈一样这里的队列和我们数据结构那里的一样队列是一种支持在尾部插入和在头部删除的线性容器遵循先进先出FIFO的原则不过这个的底层是带头双向循环链表 这里他还是适配器暂时不介绍下一期模拟实现在介绍 常用接口介绍
empty 判断队列是否为空 size 获取队列中的元素个数 front 获取队头元素的引用 back 获取队尾元素的引用 push 在队尾插入一个元素 pop 删除队头的数据 OK队列的接口就这么多也是很简单的下面还是举个例子
void queue_test1()
{queueint q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);bool emp q.empty();cout empty : emp endl;size_t sz q.size();cout size : sz endl;int front q.front();cout front : front endl;int back q.back();cout back : back endl;q.pop();sz q.size();cout size : sz endl;
} OK这里对列这了有纯队列的题他一般是作为算法的辅助工具的经典的就是BFS后面遇到了在介绍 结束语 路在自己脚下没有人可以决定我的方向。
