【C++】STL— stack的常见用法和模拟实现

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();
    }
};

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