一、栈的基础概念
1、栈的定义
栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构
2、栈的常见基本操作
- InitStack(&S)：初始化一个空栈S。
- StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
- Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
- Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
- GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
- DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。
二、顺序栈的实现
1.构建操作对象
template<class T>
class SeqStack
{
public:
SeqStack(int size = 10);
~SeqStack();
public:
//入栈
void push(T val);
//出栈
void pop();
//获得栈顶元素
T getTop();
//栈空
bool empty();
//栈元素个数
int size();
private:
void expand(T size);
T* myStack;
int top; //栈顶位置
int cap; //栈空间大小
};为了使栈可以放不同数据类型的数据，在类的开头声明了一个模板，接下来就是实现类的各个接口
2.构造函数
SeqStack(int size = 10):
top(0),
cap (size)
{
this->myStack = new T[this->cap];
}初始化列表将栈顶元素赋值为0，将初始容量赋值为size(后面可以自动扩容)，并且在堆上new出存放该数组的空间大小
3.析构函数
~SeqStack() {
delete[] this->myStack;
this->myStack = nullptr;
}释放掉数组指向的内存地址。并将其置为空指针(防止操作野指针导致程序崩溃)
4.扩容操作
void expand(T size) {
T* p = new T[size];
memcpy(p, this->myStack, sizeof(T) * this->cap);
delete[] this->myStack;
this->myStack = p;
this->cap = size;
}考虑到数组可能会满，在适当时候需要对数组进行扩容
扩容步骤：
先在堆上创建一块内存空间更大的内存地址
将老数组的值拷贝到新数组
释放老数组的内存空间，并且将维护数组的指针重新指向新内存地址
数组容量更新
5.入栈
//入栈
void push(T val) {
//先判断栈有没有满，满了扩容
if (this->top == this->cap) {
expand(this->cap + 10);
}
this->myStack[this->top] = val;
this->top++;
}先判断栈有没有满，满了扩容
直接将栈顶赋值即可，栈顶位置++
6.出栈
//出栈
void pop() {
if (this->top == 0) {
throw "stack is empty";
}
this->top--;
}先判断栈是否为空，为空的话抛异常结束程序
否则直接让栈顶元素减减即可
7.获得栈顶元素
//获得栈顶元素
T getTop() const {
if (this->top == 0) {
throw "stack is empty";
}
return this->myStack[this->top - 1];
}该接口不会对栈内元素发生改变。因此加const设置为只读状态
同样还是先判断栈是不是为空，为空抛异常
否则直接返回数组的top-1位置即可
8.判断栈空
//栈空
bool empty() const {
return this->top == 0;
}栈顶位置等于零，栈为空
9.栈元素个数
//栈元素个数
int size() const {
return this->top;
}栈顶的位置大小即是栈元素个数
三、链式栈的实现
1.构建操作对象
template<class T>
class LinkStack
{
public:
LinkStack();
~LinkStack();
public:
//入栈 把链表头结点后面，第一个有效结点的位置，当作栈顶位置
void push(T val);
//出栈
void pop();
//获取栈顶元素
T Top();
//判空
bool empty();
//返回栈元素个数
int getSize();
friend int main();
private:
struct Node
{
Node(T val = 0):
data(val),
next(nullptr)
{}
T data;
Node* next;
};
Node* head;
int size;
};声明好了常见的接口，接下来就是一一实现了
2.构造函数与析构函数
LinkStack() :size(0){
this->head = new Node;
}
~LinkStack() {
Node* p = head;
while (p) {
this->head = this->head->next;
delete p;
p = this->head;
}
}构造函数时初始化元素个数为0，并且创建头结点
析构删除链表时，每次都是删除链表的头结点
3.入栈
//入栈 把链表头结点后面，第一个有效结点的位置，当作栈顶位置
void push(T val) {
Node* node = new Node(val);
node->next = this->head->next;
this->head->next = node;
this->size++;
}采用链表头插法进行入栈，入栈后别忘记将栈内元素++
4.出栈
//出栈
void pop() {
if (this->head->next == nullptr) {
throw "stack is empty";
}
Node* p = this->head->next;
this->head->next = p->next;
delete p;
this->size--;
}因为链表可以无限增长不需要判断栈内元素是否满了，但是出栈需要先判断链表是否为空，为空抛异常
删链表第一个结点即可以出栈
头删链表结点方法也很简单，要注意删完后要栈内元素减减
5.获得栈顶元素
//获取栈顶元素
T Top() const {
if (this->head->next == nullptr) {
throw "stack is empty";
}
return this->head->next->data;
}同样该接口对数据只读状态，加const修饰
链表为空抛异常
不为空返回第一个结点的数据域
6.判空
//判空
bool empty() const {
return this->head->next == nullptr;
}链表为空，则栈也为空
7.返回栈内元素个数
//返回栈元素个数
int getSize() const {
return this->size;
}将记录该栈的元素个数返回即可
四、链式栈和顺序栈的区别
顺序栈满了需要进行扩容操作，扩容的时间复杂度为O(N)，而链表无需考虑扩容
链式栈需要额外的空间来存放结点的内存地址
顺序栈与链栈的进栈出栈时间复杂度均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度可以灵活开辟。所以他们的区别如同顺序表与链表的区别。
如果栈的使用过程中元素的变化不可预料，有时很小，有时很大，那么最好用链栈；反之，如果它的变化在可控范围内，则可使用顺序栈
五、栈的相关算法
1.括号匹配问题
问题描述：
给定一个只包含"(",")"、"{","}"、"["、"]"的s，判断字符串是否有效
满足条件：
1.左括号必须用相同的右括号匹配
2.左括号必须以正确的顺序闭合
bool isValid(string s) {
stack<char> cs;
for(char ch : s) {
if (ch == '(' || ch == '[' || ch == '{') {
cs.push(ch);
}
else {
//遇到右括号了
if (cs.empty()) {
return false;
}
char cmp = cs.top();
cs.pop();
if (ch == ')' && cmp != '('
|| ch == ']' && cmp != '['
|| ch == '}' && cmp != '{') {
return false;
}
}
}
return cs.empty();
}遍历栈，遇到左括号则入栈，遇到右括号出栈一个括号，和遍历到的当前左括号匹配，匹配不成功直接返回false，匹配成功继续操作，遍历完后，直到栈内元素为空，则返回true
这里需要注意：防止上来就是右括号导致直接进入比较阶段，进行出栈元素，这时候栈内并没有元素
因此加
if (cs.empty()) {
return false;}
限制这种极端情况
2.逆波兰表达式求解
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
int evalRPN(vector<string>& tokens) {
stack<int> intStack;
for (string& str : tokens) {
if (str.size() == 1
&& (str[0] == '+'
|| str[0] == '-'
|| str[0] == '*'
|| str[0] == '/')) {
//遇到运算符进行运算
int r = intStack.top();
intStack.pop();
int l = intStack.top();
intStack.pop();
switch (str[0]) {
case '+':intStack.push(l + r); break;
case '-':intStack.push(l - r); break;
case '*':intStack.push(l * r); break;
case '/':intStack.push(l / r); break;
}
}
else {
//遇到数字直接入数字栈
intStack.push(stoi(str));
}
}
return intStack.top();
}遇到数字直接入栈
遇到符号，从栈里出栈两个数字，用两个变量先后记录他们
按照顺序运算两个数字，把结果再入栈，直到栈内只剩一个元素，这时候这个元素就是值了
3、用两个队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
class MyStack {
public:
MyStack() {
}
void push(int x) {
q1.push(x);
while(!q2.empty()) {
q1.push(q2.front());
q2.pop();
}
queue<int> tem = q1;
q1 = q2;
q2 = tem;
}
int pop() {
int val = q2.front();
q2.pop();
return val;
}
int top() {
return q2.front();
}
bool empty() {
return q2.empty();
}
private:
queue<int>q1, q2;
};s1队列用来放每次入栈的元素，之后再将s2的元素依次出栈放入到s1，此时s1放着所有元素，s2为空队列，交换s1，s2，s1变为空
每次添加元素添加到s1，删除元素在s2中进行