逻辑结构：
栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合 （受限的线性表）。这种数据结构只允许在栈顶进行添加（push）或删除（pop）元素的操作。栈是一种非常基础且重要的数据结构，广泛应用于计算机科学和软件开发中。
栈顶：插入和删除
栈底：固定的 不允许插入和删除
空栈：不含任何元素
栈的基本操作
- push(element): 向栈顶添加一个元素。如果栈已满，则可能无法进行此操作。
- pop(): 移除栈顶的元素，并返回该元素。如果栈为空，则可能无法进行此操作，并可能返回一个错误或特殊值（如
null或undefined）。 - peek() 或 top(): 返回栈顶元素的值，但不从栈中移除它。如果栈为空，则可能返回一个错误或特殊值。
- isEmpty(): 检查栈是否为空。
- size(): 返回栈中元素的数量。
栈的存储结构：
栈可以通过多种方式实现，包括使用数组（或列表）和链表。
顺序存储：
-
基于数组的栈（顺序栈）：在这种实现中，数组的一端被用作栈顶。添加元素时，新元素被添加到数组的末尾；移除元素时，数组的最后一个元素被移除。这种实现方式在大多数编程语言中都非常高效，因为数组的末尾操作通常很快。
初始化：
# define MaxSize 50
typedef struct
{Elemtype data[MaxSize];int top;//栈顶指针}SqStack;//iniiallize
void initStack(SqStack &s){
s.top=-1;
}判断非空：
//empty
bool StackEmpty(SqStack s){if(s.top==-1)return true;elsereturn false;
}进栈：
//in
bool Push(SqStack &s,Elemtype e){if(s.top==MaxSize-1)return false;else{s.top++;s.data[s.top]=e;}return true;}进栈和出栈的操作 根据s.top的初始值不同而不同：
s.top=-1先指针+1再进栈，先出栈再指针-1；
s.top=0先进栈再指针+1，先指针-1再出栈；
出栈：
bool Pop(SqStack &s,Elemtype &e){if(s.top==-1)return false;e=s.data[s.top];s.top--;return true;
}读取栈顶元素：
//read
bool GetTop(SqStack s,Elemtype &x){if(s.top==-1)return false;x=s.data[s.top];
return true;
}链式存储：
-
基于链表的栈：下列代码规定没有头结点，LHead指向栈顶元素，链表的头部被用作栈顶。添加元素时，新元素被添加到链表的头部；移除元素时，链表的第一个元素（即头部元素）被移除。虽然链表在随机访问方面不如数组高效，但在某些情况下（如动态内存分配），链表可能更灵活。
//
typedef struct LinkNode
{Elemtype data;struct LinkNode *next;}LiStack;栈的应用
栈的应用非常广泛，包括但不限于：
-
函数调用：
在大多数编程语言中，函数调用是通过栈来实现的。当函数被调用时，其返回地址和局部变量被推入栈中；当函数返回时，这些信息从栈中弹出。
-
表达式求值：
在编译器和解释器中，栈用于计算表达式的值。例如，在解析算术表达式时，可以使用栈来跟踪操作符和操作数。
中缀转后缀：
1）加括号：(( A +③( B *②( C -① D )))-©( E /④ F ))。
2）运算符后移：(( A ( B ( CD )-①)*②)+③( EF )/④)-⑤。
3）去除括号后，得到后缀表达式： ABCD -①*②+③ EF /④-⑤.
在计算机中，中缀表达式转后缀表达式时需要借助一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右依次扫描中缀表达式中的每一项，具体转化过程如下：
1）遇到操作数。直接加入后缀表达式。
2）遇到界限符。若为"("，则直接入栈；若为")"，则依次弹出栈中的运算符，并加入后缀表达式，直到弹出"("为止。注意，"("直接删除，不加入后缀表达式。
3）遇到运算符。若其优先级高于除"("外的栈顶运算符，则直接入栈。否则，从栈顶开始，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，直到遇到一个优先级低于它的运算符或遇到"("时为止，之后将当前运算符入栈。按上述方法扫描所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
转后缀图解（例子）：
后缀表达式求值：
通过后缀表示计算表达式值的过程：从左往右依次扫描表达式的每一项，若该项是操作数，则将其压入栈中；若该项是操作符＜ op >，则从栈中退出两个操作数 Y 和 x ，形成运算指令 X < op > y ,并将计算结果压入栈中。当所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。
后缀求值图解：
-
括号匹配：
栈可以用来检查括号（如圆括号、方括号和花括号）是否正确匹配。
-
回溯算法：
在解决某些问题时（如迷宫问题、八皇后问题等），栈可以用来保存中间状态，以便在需要时回溯到之前的状态。
-
页面访问历史：
在Web浏览器中，栈可以用来保存用户访问的页面历史，以便用户可以通过“后退”按钮返回到之前的页面。
总之，栈是一种简单但功能强大的数据结构，其独特的后进先出原则使得它在许多应用场景中都非常有用。
