文章索引
前言1. stack的介绍2. stack的使用3. stack的模拟实现4. stackOJ题目4.1 最小栈4.2 栈的压入弹出序列4.3 用栈实现队列 总结
前言
在现代C++编程中，STL（标准模板库）是一个不可或缺的工具。它提供了一套通用的模板类和算法，使得开发者能够更加高效地处理数据。本文将重点介绍STL中的stack容器，作为一种重要的顺序容器，stack遵循后进先出（LIFO，Last In First Out）的特性，广泛应用于函数调用、表达式求值等场景。通过深入了解stack的特性、基本操作及应用实例，读者将能够更好地掌握和应用这一重要的数据结构。
博客主页: 酷酷学!!!
感谢关注!!!
正文开始
1. stack的介绍
2. stack的使用
重点:
代码演示:
#include<stack>#include<iostream>using namespace std;int main(){stack<int> st;st.push(1);st.push(2);cout << st.top() << endl;st.pop();cout << st.size() << endl;st.pop();cout << st.empty() << endl;return 0;}
3. stack的模拟实现
从栈的接口中可以看出, 栈实际上是一种特殊的vector, 因此使用vector完全可以模拟实现stack.
#pragma once#include<iostream>#include<vector>#include<list>using namespace std;namespace my{//传统写法//template<class T>//class stack//{//private://T* _a;//int _top;//int _capacity;//};//直接复用容器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;};}4. stackOJ题目
4.1 最小栈
题目链接:最小栈
题目描述:
题目思路:
题目要求在常数时间内求出栈中最小元素, 如果我们遍历栈, 时间复杂度就为N, 不符合题目要求, 我们可以创建两个栈, 一个用来模拟入栈出栈, 一个用来记录最小数据, 定义两个栈为成员函数, 首先, 先插入一个元素, 然后让出栈序列与入栈的栈顶元素进行比较, 如果_minst为空或者栈顶元素小于或者等于_minst的栈顶元素, 则将数据push到最小栈, 出栈时, 如果_st的栈顶元素等于_minst的栈顶元素, 则_minst出栈, 即更改了当前最小元素.
代码演示:
class MinStack {public: MinStack() { } void push(int val) { if(_minst.empty() || val <= _minst.top()) { _minst.push(val); } _st.push(val); } void pop() { if(_st.top() == _minst.top()) { _minst.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } stack<int> _st; stack<int> _minst;};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */4.2 栈的压入弹出序列
题目链接:栈的压入弹出序列
题目描述:
题目思路
对于栈的压入弹出序列, 我们如果直接上手对比, 很容易出错, 而且比较麻烦, 我们可以对入栈与出栈进行栈的模拟, 创建一个栈st, 对入栈序列进行遍历插入, 先插入一个元素, 然后与出栈序列进行对比, 遍历出栈序列, 如果与出栈序列相等, 则说明该出栈了, 就pop出此时的栈, 这时还不能插入新的元素, 继续将st的栈顶元素与出栈序列对比, 如果不想等了, 我们再插入, 然后再进行下一轮的对比, 或者此时st已经为空了, 则跳出循环, 也进行下一轮的插入对比, 如果插入序列全部遍历完, 而出栈序列没有遍历完, 则说明此出栈序列不为栈的弹出序列, 反之亦然.也可以判断此时栈是否为空即可.
代码演示:
class Solution {public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型 */ bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // write code here stack<int> st; int pos = 0; for(auto e : pushV) { st.push(e); while( !st.empty() && st.top() == popV[pos]) { pos++; st.pop(); } } return st.empty(); }};4.3 用栈实现队列
题目链接:
用栈实现队列
题目描述:
题目思路
对于本题我们再栈的那一篇已经使用c语言完成过了, 本次我们采用C++进行完成, 避免了我们自己造轮子, 还是一样, 用两个栈实现一个队列, 一个栈进行插入, 如果需要出栈, 则就把所有的插入栈所有数据导一下,出栈直接出popst中的元素.
代码演示
class MyQueue {public: MyQueue() { } void push(int x) { pushst.push(x); } int pop() { if(popst.empty()) { while(!pushst.empty()) { int x = pushst.top(); popst.push(x); pushst.pop(); } } int ret = popst.top(); popst.pop(); return ret; } int peek() { if(popst.empty()) { while(!pushst.empty()) { int x = pushst.top(); popst.push(x); pushst.pop(); } } int ret = popst.top(); return ret; } bool empty() { return pushst.empty()&&popst.empty(); } stack<int> pushst; stack<int> popst;};/** * Your MyQueue object will be instantiated and called as such: * MyQueue* obj = new MyQueue(); * obj->push(x); * int param_2 = obj->pop(); * int param_3 = obj->peek(); * bool param_4 = obj->empty(); */总结
通过对STL中stack的探讨，我们认识到它在解决特定问题时的便利性和高效性。stack类提供了简单易用的接口，使得数据的插入和删除操作更加直接。同时，我们也了解了其在实际应用中的价值，例如在算法中用于管理临时状态或数据。此外，结合实际示例和代码实现，读者可以看到如何灵活地将stack应用于自己的项目中。掌握stack的使用，将为解决更复杂的问题奠定坚实的基础。希望本文能帮助大家更深入地了解STL之stack，并在日常编程中熟练运用
完