目录
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();
}
};本篇完，下篇见！如有问题，欢迎在评论区指导！
