徐家汇网站建,wordpress首页调用指定分类,十大图片素材网站,网站管理助手创建数据库前言
stack 和 queue使用起来都非常简单#xff0c;现在来模拟实现一下#xff0c;理解其底层的原理。 在实现之前#xff0c;应该知道#xff0c;stack 和 queue 都是容器适配器#xff0c;通过看官网文件也可以看出来#xff1b;其默认的容器都是deque#xff…前言
stack 和 queue使用起来都非常简单现在来模拟实现一下理解其底层的原理。 在实现之前应该知道stack 和 queue 都是容器适配器通过看官网文件也可以看出来其默认的容器都是deque双端队列。
stack 和 queue 都是在容器的基础上进行了封装实现了各自的操作。
在下面的实现中stack默认容器用vectorqueue默认容器用list
栈和队列的使用
栈的使用
首先STL中的栈是基于容器适配器实现的默认容器是deque。
使用栈需要包含头文件:
#includestack1.1 栈的基本操作
先看一下栈提供的接口函数 常用方法
push(): 将元素 val 压入栈顶。pop(): 移除栈顶元素。top(): 返回栈顶元素但不移除。empty(): 判断栈是否为空。size(): 返回栈的元素数量。
1.2 栈的使用
现在简单使用一下stack
void test_stack() {//创建一个栈——存储整形stackint s; //入栈s.push(1);s.push(2);s.push(3);//栈中元素cout 元素个数: s.size() endl;//栈顶元素cout 栈顶元素: s.top() endl;//出栈s.pop();//依次输出栈中的数据while (!s.empty()) {cout s.top() ;s.pop();}cout endl;return 0;
}输出结果
元素个数: 3
栈顶元素: 3
2 11.3 应用实例点击消除
栈可以用来解决括号匹配这一类的问题。
括号匹配之前已经做过了这里来用栈做这样的一道题点击消除_牛客题霸_牛客网
题目描述 这题思路比较简单就是遍历字符串时不断入栈出栈字符串中字符与栈顶元素相等最后输出即可。
需要注意的是这里使用数组来模拟栈方便输出
当然也可以使用栈不过输出时顺序是反的需要进行处理。
#include iostream
using namespace std;int main() {string str;cinstr;string ret;for(auto ch: str){if(ret.size()0||ret[ret.size()-1]!ch){ret.push_back(ch);}else {ret.pop_back();}}if(ret.empty()){cout0;return 0;}coutret;return 0;
}队列的使用
2.1 队列的基本操作
STL 中的队列queue也是一种容器适配器默认底层容器也是 deque。
使用栈需要包含头文件:
#includequeue常用方法
push(): 将元素 val 插入队尾。pop(): 移除队头元素。front(): 返回队头元素不移除。back(): 返回队尾元素不移除。empty(): 判断队列是否为空。size(): 返回队列的元素数量。
2.2 队列的使用
简单使用一下队列
void test_queue()
{//创建一个队列——存储整型queueint q;//入队列q.push(10);q.push(20);q.push(30);cout 数据个数: q.size() endl;cout 队头元素: q.front() endl;cout 队尾元素: q.back() endl;//出队列q.pop();cout 队列中数据: ;while (!q.empty()) {cout q.front() ;q.pop();}cout endl;
}输出结果
数据个数: 3
队头元素: 10
队尾元素: 30
队列中数据: 20 30栈和队列的模拟实现
stack 模拟
学习过初阶数据结构的栈大概知道栈是怎么实现的使用过STL里的stack也知道具体哪些操作这里就直接开始实现。
1.默认成员函数
对于默认成员函数因为这里stack是对容器的封装所以那些构造函数、析构函数、赋值运算符重载等都不需要我们自己去实现编译器默认生成的会去调用vector容器的默认成员函数。 templateclass T, class Container vectorTclass stack{stack() {}private:Container _con;};2.基本操作
栈的基本操作无疑就是入栈、出栈、取栈顶元素、判断栈是否为空。
入栈
直接调用容器vector的尾插即可。 void push(const T x){_con.push_back(x);}出栈
直接调用容器vector的尾删 void pop(){_con.pop_back();}取栈顶元素
直接返回容器vector的最后一个元素即可即调用back()函数 T top(){return _con.back();}const T top()const {return _con.back();}判断是否为空
调用容器的empty函数即可 bool empty() const{return _con.empty();}返回栈中元素个数 size_t size() const {return _con.size();}swap
直接调用容器的swap函数即可。 void swap(stack st){_con.swap(st._con);} 到这里 就简单实现了我们的stack 结构了是不是感觉很简单呢 templateclass T, class Container vectorTclass stack{public:stack() {}void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}T top(){return _con.back();}const T top()const {return _con.back();}bool empty() const{return _con.empty();}size_t size() const {return _con.size();}void swap(Container st){_con.swap(st._con);}private:Container _con;};queue 模拟
默认成员函数
和stack一样我们不需要去实现它的默认成员函数编辑器默认生成的就已经可以满足我们的需求了。
基本操作
push
入队列在队尾插入 void push(const T x){_con.push_back(x);}pop
出队列从头部删除 void pop(){_con.pop_front();}front和back
返回队头数据 / 队尾数据
T back()
{return _con.back();
}
const T back() const
{return _con.back();
}
T front()
{return _con.front();
}
const T front()const
{return _con.front();
}empty bool empty() const{return _con.empty();}size size_t size() const{return _con.size();}swap void swap(Container con){_con.swap(con);} 到这里stack和queue的模拟实现就完成了感觉是不是很容易呢。
三、双端队列deque的栈和队列操作
deque双端队列既可以当作栈也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作从而更灵活地实现栈和队列的功能。
对于双端队列简单来说就是可以像vector那样随机访问也可以像链表那样随机位置插入但是效率很低个人感觉就是为了给stack和queue作默认容器适配器来用的。
这里就不过多描述双端队列了感兴趣可以去看一下源码学习学习。
继续加油
_con.size(); } **swap**~~~cppvoid swap(Container con){_con.swap(con);} 到这里stack和queue的模拟实现就完成了感觉是不是很容易呢。
三、双端队列deque的栈和队列操作
deque双端队列既可以当作栈也可以当作队列使用。我们可以在双端队列的两端进行插入和删除操作从而更灵活地实现栈和队列的功能。
对于双端队列简单来说就是可以像vector那样随机访问也可以像链表那样随机位置插入但是效率很低个人感觉就是为了给stack和queue作默认容器适配器来用的。
这里就不过多描述双端队列了感兴趣可以去看一下源码学习学习。
继续加油
