栈（stac）详解及应用
一.栈
1.栈的详解
A.栈的定义
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
其中，我们需要记住，栈的最大特征：先进后出
进栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈顶（Top）：线性表允许进行插入删除的那一端。 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。 空栈：不含任何元素的空表。
B.栈的常见操作
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占用的存储空间（“&”表示引用调用）。
C.栈的底层实现（顺序存储结构）
栈的底层是由什么实现的呢？？
这个问题我们需要思考一下，使用链表实现的？还是用数组呢？
我想说：在这里，用链表和数组都是可以的，只不过是用什么更方便的问题，我认为用数组显得更方便一些，用链表还要解决指针关系，就显得有点复杂。所以，我们采用数组的方式来实现栈
1>:栈的定义
typedef struct my_stack
{
int _arry[Num];
int _top; //用于栈顶指针,栈为空时，_top=-1;
int _size; //用于记录栈中数据个数
}mystack;2>栈的初始化
void InitStack(mystack* q1)
{
q1 = (mystack*)malloc(sizeof(mystack));
q1->_top = -1;
q1->_size = 0;
}3>判断栈为空
bool StackEmpty(mystack* q1)
{
assert(q1);
return q1->_size == 0 ? true : false;
}4>判断栈满
bool StackFull(mystack* q1)
{
assert(q1);
return q1->_size == Num ? true : false;
}5>入栈
bool StackPush(mystack* q1, Emeltype e)
{
assert(q1);
if (!StackFull(q1)) return false;
q1->_arry[q1->_size] = e;
q1->_size++;
q1->_top++;
return true;
}6>出栈
bool StackPop(mystack* q1, Emeltype* e)
{
assert(q1);
if (StackEmpty(q1)) return false;
*e = q1->_arry[q1->_size - 1];
q1->_size--;
q1->_top--;
return true;
}7>读取栈顶元素
bool StackTop(mystack* q1, Emeltype* e)
{
assert(q1);
if (StackEmpty(q1)) return false;
*e = q1->_arry[q1->_size - 1];
q1->_size;
q1->_top;
return true;
}D.完整代码
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define Num 100
typedef int Emeltype;
typedef struct my_stack
{
int _arry[Num];
int _top; //用于栈顶指针,栈为空时，_top=-1;
int _size; //用于记录栈中数据个数
}mystack;
void InitStack(mystack* q1)
{
q1 = (mystack*)malloc(sizeof(mystack));
q1->_top = -1;
q1->_size = 0;
}
bool StackEmpty(mystack* q1)
{
assert(q1);
return q1->_size == 0 ? true : false;
}
bool StackFull(mystack* q1)
{
assert(q1);
return q1->_size == Num ? true : false;
}
bool StackPush(mystack* q1, Emeltype e)
{
assert(q1);
if (!StackFull(q1)) return false;
q1->_arry[q1->_size] = e;
q1->_size++;
q1->_top++;
return true;
}
bool StackPop(mystack* q1, Emeltype* e)
{
assert(q1);
if (StackEmpty(q1)) return false;
*e = q1->_arry[q1->_size - 1];
q1->_size--;
q1->_top--;
return true;
}
bool StackTop(mystack* q1, Emeltype* e)
{
assert(q1);
if (StackEmpty(q1)) return false;
*e = q1->_arry[q1->_size - 1];
q1->_size;
q1->_top;
return true;
}2.栈的应用
其实，如果我们刷了很多题的话，我们会知道栈和其他数据结构是不一样的，栈是工具性数据结构，接下来，我们找一道题来练习一下： 题目链接
1.题目解析
当开始接触这道题目时，我就有一个疑问，是不是每一个左括号都有一个与之对应的右括号是不是就是有序的括号了？答案是不是的，不仅仅左右括号要在数量上和类型上对应，还要有一定的顺序。
假如输入是 [{]}，每种括号的左右数量分别相等，但不是有效的括号。这是因为结果还与括号的位置有关。
仔细分析我们发现，对于有效的括号，它的部分子表达式仍然是有效的括号，比如 {()[()]} 是一个有效的括号，()[{}] 是有效的括号，[()] 也是有效的括号。并且当我们每次删除一个最小的括号对时，我们会逐渐将括号删除完。比如下面的例子。
这个思考的过程其实就是栈的实现过程。因此我们考虑使用栈，当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。
2.代码实现
class Solution {
public:
bool isValid(string s) {
int n=s.size();
if(n%2==1) return false;
stack<char> st;
for(auto ch:s)
{
if(ch=='{'||ch=='('||ch=='[')
{
st.push(ch);
}
else
{
if((ch==')'&&stack.top=='('))
{
stack.pop();
}
else if((ch==']'&&stack.top=='['))
{
stack.pop();
}
else if((ch=='}'&&stack.top=='{'))
{
stack.pop();
}
else
{
return false;
}
}
}
return st.empty();
}
};