【算法通关指南：数据结构和算法篇】栈的实现不用愁！数组 + 变量 n，新手也能 拿捏栈实现
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南 》
✨ 永远相信美好的事情即将发生
文章目录
前言
本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力
ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长
一、栈的概念
栈是⼀种只允许在⼀端进行数据插入和删除操作的线性表。
（1）进行数据插入或删除的一端称为 栈顶，另⼀端称为栈底。不含元素的栈称为空栈。
（2） 进栈就是往栈中放入元素，出栈就是将元素弹出栈顶。
ps: 栈其实是⼀个比较简单的数据结构。学习的重点在于用栈去解决问题，这也是难点。
【注意】
如果定义了⼀个栈结构，那么添加和删除元素只能在栈顶进行。不能随意位置添加和删除元素，这是栈这个数据结构的特性，也是规定。
二、栈的模拟实现
2.1创建
（1）本质还是线性表，因此可以创建⼀个足够大的数组，充当栈结构
（2）再定义⼀个变量n，用来记录栈中元素的个数，同时还可以标记栈顶的位置。
constint N =1e6+10;int stk[N];int n;2.2进栈
这里依旧舍弃下标为0 的位置，有效元素从 1开始记录。
进栈操作，那就把元素放在栈顶位置即可。
不必
//进栈voidpush(int x){ stk[++n]= x;}时间复杂度：O(1)
2.3出栈
ps：不用真的删除元素，只用将元素个数减1，就相当于删除栈顶元素。
//出栈voidpop(){ n--;}时间复杂度：O(1)
2.4栈顶元素
注意：因为栈特殊的规定，不⽀持遍历整个栈中的元素。因此，需要查找栈中元素的时候，只能查找到栈顶元素。
// 栈顶元素inttop(){return stk[n];}时间复杂度：O(1)
2.5判空
// 判空 bool empty(){return n ==0;}时间复杂度：O(1)
2.6有效元素个数
// 栈中元素个数 intsize(){return n;}时间复杂度：O(1)
2.7 所有测试代码
#include<iostream> using namespace std;constint N =1e6+10;int stk[N];int n;//进栈voidpush(int x){ stk[++n]= x;}//出栈voidpop(){ n--;}// 栈顶元素inttop(){return stk[n];}// 判空 bool empty(){return n ==0;}// 栈中元素个数 intsize(){return n;}intmain(){for(int i =1; i <=10; i++)push(i);while(!empty())// while(size()) { cout <<top()<<" ";pop();}return0;}运行结果：
三、stack
3.1 如何创建
stack<T> st;//T 可以是任意类型的数据。3.2容器相关接口
3.2.1 size / empty
（1）size ：返回栈里实际元素的个数；
（2）empty ：返回栈是否为空。
时间复杂度：O(1)
3.2.2 push/pop
（1） push ：进栈；
（2） pop：出栈。
时间复杂度：O(1)
3.2.3 top
（1） top：返回栈顶元素，但是不会删除栈顶元素。
时间复杂度： O(1)
3.3测试所有接口
#include<iostream>#include<stack> using namespace std;intmain(){ stack<int> st;// 先讲1~10进栈for(int i =1; i <=10; i++){ st.push(i);}while(st.size())// !st.empty(){ cout << st.top()<< endl; st.pop();}return0;}运行结果：
总结 — 每日励志时刻
✨ 本文介绍了栈(stack)这一数据结构的概念、模拟实现及C++ STL中的stack容器。文章首先阐述了栈作为"后进先出"(LIFO)线性表的特点，包括栈顶、栈底操作规则。随后详细讲解了使用数组模拟栈的实现方法，包括进栈(push)、出栈(pop)、获取栈顶元素(top)、判空(empty)等基本操作，并提供了完整的测试代码。最后介绍了C++ STL中的stack容器及其接口使用，通过示例代码展示了如何利用STL stack进行基本操作。全文强调栈在算法竞赛中的应用价值，并指出其操作的时
