目录

1、stack的介绍

2、stack的使用

构造一个空栈

stack的简单接口应用

3、stack的模拟实现

4、栈的相关题目

4.1 最小栈

4.1.2思路

4.1.3 实现代码

4.2 栈的压入、弹出序列

4.2.2 思路

4.2.3程序实现

---

1、stack的介绍

在C++中，stack是一种标准模板库（STL）中的容器适配器，它提供了后进先出（LIFO）的数据结构。这意味着最后添加到stack中的元素将是第一个被移除的元素，可以用来解决那些需要按照逆序处理元素的场景的问题。

2、stack的使用

函数说明	接口说明
stack()	构造空的站
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部元素弹出

构造一个空栈

stack<int> s;

stack的简单接口应用

void test_stack()
{stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;
}

3、stack的模拟实现

从栈的接口中可以看出, 栈实际上是一种特殊的vector, 因此使用vector完全可以模拟实现stack.

适配器模式 – 本质就是转换
stack<int, vector> st1;
stack<int, list> st2;
template<class T,class Container>
泛型编程，兼容多种类型的栈，满足链表list和顺序表vector…

#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、栈的相关题目

4.1 最小栈

4.1.2思路

搞两个栈，一个存放原始数据，一个存放当前最小值并不断更新栈顶元素

 首先, 先插入一个元素, 然后让出栈数与入栈的栈顶元素进行比较, 如果_minst为空或者栈顶元素小于或者等于_minst的栈顶元素, 则将数据push到最小栈, 出栈时, 如果_st的栈顶元素等于_minst的栈顶元素, 则_minst出栈, 即更改了当前最小元素.

4.1.3 实现代码

class MinStack {
public:MinStack() {}void push(int val) {    // 如果val小于_minst中栈顶的元素，将x再压入_minst中if(_minst.empty() || val <= _minst.top())_minst.push(val);_st.push(val);  // 只要是压栈，先将元素保存到_elem中}void pop() {    // 如果_minst栈顶的元素等于出栈的元素，_minst顶的元素要移除if(_minst.top() == _st.top())_minst.pop();_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;  // 保存栈中的元素stack<int> _minst;  // 保存栈的最小值
};

4.2 栈的压入、弹出序列

4.2.2 思路

创建一个栈, 对入栈序列进行遍历插入, 先插入一个元素, 然后与出栈序列进行对比, 遍历出栈序列, 如果与出栈序列相等, 则说明该出栈了，但这时还不能插入新的元素, 继续将st的栈顶元素与出栈序列对比, 如果不想等了, 我们再插入, 然后再进行下一轮的对比，或者此时栈已经为空了, 则跳出循环, 也进行下一轮的插入对比, 如果插入序列全部遍历完, 而出栈序列没有遍历完, 则说明此出栈序列不为栈的弹出序列, 反之亦然.也可以判断此时栈是否为空即可。

1.先把入栈序列入栈
2.栈顶元素和出栈序列是否匹配
a、如果匹配就持续出数据，直到栈为空为止
b、如果不匹配，继续入栈
3.结束标志：a、入栈序列走完了 b、栈走完了，也不匹配，不合法的序列

4.2.3程序实现

class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {int popi = 0;stack<int> st;for(auto &e : pushV){st.push(e);while(!st.empty() && st.top()== popV[popi]){st.pop();popi++;}}return st.empty();}
};

---

本篇完，下篇见！如有问题，欢迎在评论区指导！