一、栈的概念
栈是⼀种只允许在⼀端进⾏数据插⼊和删除操作的线性表。
- 进⾏数据插⼊或删除的⼀端称为栈顶，另⼀端称为栈底。不含元素的栈称为空栈。
- 进栈就是往栈中放⼊元素，出栈就是将元素弹出栈顶。
二、栈的模拟实现
1. 创建
- 本质还是线性表，因此可以创建⼀个⾜够⼤的数组，充当栈结构
- 再定义⼀个变量 n ，⽤来记录栈中元素的个数，同时还可以标记栈顶的位置。
const int N = 1e6 + 10;int n;int stk[N];2. 进栈
时间复杂度：
显然是 O(1) 。
这⾥依旧舍弃下标为 0 的位置，有效元素从 1 开始记录。
进栈操作，那就把元素放在栈顶位置即可。
// 进栈
void push(int x){stk[++n] = x;}3. 出栈
时间复杂度：
显然是 O(1) 。
不⽤真的删除元素，只⽤将元素个数减 1 ，就相当于删除栈顶元素。
// 出栈
void pop(){n--;}4. 栈顶元素
时间复杂度：
显然是 O(1) 。
查询栈顶元素。
这⾥要注意，因为栈特殊的规定，不⽀持遍历整个栈中的元素。因此，需要查找栈中元素的时候，只能查找到栈顶元素。
// 栈顶元素
int top(){return stk[n];}5. 判空
时间复杂度：
显然是 O(1) 。
判断栈是否为空
// 判空
bool empty(){return n == 0;}6. 有效元素的个数
时间复杂度：
显然是 O(1) 。
// 栈中元素个数
int size(){return n;}7. 所有测试代码
#include <iostream>using namespace std;const int N = 1e5 + 10;// 创建栈
int stk[N], n;// 进栈 - 本质就是顺序表里面的尾插
void push(int x)
{stk[++n] = x;
}// 出栈 - 顺序表的尾删操作
void pop()
{n--;
}// 查询栈顶元素
int top()
{return stk[n];
}// 判断是否为空
bool empty()
{return n == 0;
}// 查询有效元素的个数
int size()
{return n;
}int main()
{for(int i = 1; i <= 10; i++){push(i);}// 当栈不为空的时候while(size()) // while(!empty()) {cout << top() << endl;pop();}return 0;
}二、stack
有了之前 vector 和 list 的铺垫，栈的使⽤应该会⽐较得⼼应⼿。
1. 如何创建？
2. 关⼼⾥⾯有什么函数？
3. 函数的功能以及时间复杂度
1. 创建
- stack<T> st;
- T 可以是任意类型的数据。
2. size / empty
时间复杂度： O(1)
- size ：返回栈⾥实际元素的个数；
- empty ：返回栈是否为空。
3. push/pop
时间复杂度： O(1)
- push ：进栈；
- pop ：出栈。
4. top
时间复杂度： O(1)
top ：返回栈顶元素，但是不会删除栈顶元素。
5. 所有测试代码
#include <iostream>
#include <stack>using namespace std;int main()
{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();}return 0;
}
