Lesson11---stack

Lesson11—stack

c++stack的介绍使用以及模拟实现

前言

1. stack的介绍和使用
2. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行
   元素的插入与提取操作。
3. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定
   的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
4. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下
   操作：
   empty：判空操作
   back：获取尾部元素操作
   push_back：尾部插入元素操作
   pop_back：尾部删除元素操作
5. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，
   默认情况下使用deque。
   

stack的成员函数和前几期很像就简单的使用一下

一、stack成员函数

1.stack

构造一个栈这里无需初始化这里以及写好了构造函数

2.empty

判断这个栈是不是空
空返回true
非空返回false
通常用来遍历这个栈
栈没有提供范围for

oid test1()
{
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    while (!s.empty())
    {
        cout << s.top() << ' ';
        s.pop();
    }
}

3.size

有了前几章的基础这些都是秒懂

4. top

返回栈顶的元素

5.push

栈是先进后出

void test1()
{
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);
    while (!s.empty())
    {
        cout << s.top() << ' ';
        s.pop();
    }
}

6.pop

出栈其实和尾删差不多

二、stack相关题目

1. 最小栈

https://leetcode.cn/problems/min-stack/description/

这道题的要求就是返回栈的最小值但是这里时间复杂度要求比较高，这里采用俩个栈来实现

class MinStack {
public:
    MinStack() {
        
    }
    
    void push(int val) {
        
    }
    
    void pop() {
        
    }
    
    int top() {
        
    }
    
    int getMin() {
        
    }
};

/**
 * 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();
 */

这是题目给的初始代码，这里构造不自己写了，直接删掉走默认构造

class MinStack {
public:
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val<= _minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        if(_minst.top() == _st.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();
 */

2.栈的压入、弹出序列

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) 
    {
        stack<int> st;
        size_t index=0;
        for(auto e:pushV)
        {
            st.push(e);
            while (!st.empty() && popV[index] == st.top()) {
                index++;
                st.pop();
            }
        }
        return st.empty();
    }
};

三、模拟实现

#pragma once
template<class T>
class my_stack
{
private:
	T* _a;
	int _top;
	int _capacity;
};

上面是原始人写法，现代人可以这样写

#pragma once
#include<bits/stdc++.h>
using namespace std;
template<class T,class container>
class my_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()
	{
		_con.size();
	}
private:
	container _con;
};

#define _CRT_SECURE_NO_WARNINGS 
#include"mystack.h"
using namespace std;
int main()
{
    my_stack<int, vector<int>> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    return 0;
}

这里用俩个模板参数，栈可以用vector也可以用list，这里可以指定，甚至这里可以用list来弄

但是这里每次都要指定又太麻烦了，模板和函数参数一样都可以直接给缺省参数

总结

模板可以给缺省参数，有了模板这些实现就变得特别的灵活，函数给的是值，模板给的是类型